Coding Interview. Penjelasan 'find pair that sums up to k' Menggunakan Hash Map

Ada berbagai macam coding interview ketika kita ingin melamar pekerjaan sebagai software engineer. Selain SE harus bisa menyelesaikan pertanyaan tersebut, mereka juga harus bisa menjelaskan dengan rinci dan runut bagaimana cara penyelesaiannya

Postingan ini akan membahas sebuah pertanyaan interview yang biasa disebut, "find pair that sums up to k". 

Soal

Kalian adalah seorang programmer yang ingin melamar pada sebuah start-up dan mendapatkan soal berikut:

Cari dua angka dari barisan array (arr) ini yang apabila dijumlahkan akan menghasilkan nilai yang sama dengan k.  Jika ternyata ada maka function mengembalikan True, jika tidak ada mengembalikan nilai False

Ada dua cara untuk menyelesaikan soal diatas. Bisa menggunakan looping seperti biasa, bisa juga menggunakan Hash Map

Kali ini saya akan menggunakan metode Hash Map untuk menyelesaikannya. Mengapa? Karena Hash Map tidak banyak memakan memori. 

Konsep Penyelesaiannya

Kita harus mencari nilai a dari array satu persatu lalu kurangi k dengan nilai a sambil memasukkan nilai a ke dalam dict visited dengan value True, mengapa karena ini untuk menunjukan apakah terdapat sisa pengurangan k dengan a yang juga merupakan element dari array. Jika kita berhasil menemukan hasil pengurangan k dengan nilai a terdapat pada visited yaitu nilai b. Maka kita berhasil menemukan nilai a dengan b di dalam array yang apabila dijumlah menghasilkan nilai k. Setelah itu function kita return True jika terdapat dua element dalam array yang apabila dijumlah menghasilkan nilai k, jika tidak ada maka mengembalikan False

Code:

Jika kita coba akan menampilkan hasil berikut:

 

 

Kesimpulan

Untuk mencari dua element yang bisa dijumlahkan lalu memiliki hasil yang sama dengan nilai k, bisa dengan mencari jawaban, "apakah dengan mengurangi nilai k dengan element a pada array, memiliki hasil berupa b yang juga terdapat pada array?"