Yasya Indra Blog

Kalo kalian ingin melamar sebagai programmer di suatu perusahaan biasanya ada sesi interview. Jenis interviewnya pun ada beberapa macam. Mulai dari wawancara, review CV hingga yang bikin deg degan adalah coding interview. Dimana calon programmer diperintahkan untuk memecahkan masalah dari seuatu problem pemograman

Salah satu problem yang populer adalah binary tree.

Binary Tree merupakan sebuah susunan angka yang diurut seperti pohon. Biasanya ini menjadi soal atau contoh case yang ada dalam pemecaham masalah dalam pemograman

Tak jarang juga persoalan seperti ini menjadi sebuah test soal untuk mengetahui seberapa dalam kemampuan seorang programmer. Apakah programmer tersebut siap jikalau ada permasalahan yang muncul dalam aplikasi yang mirip dengan soal binary tree ini?

Ketika kalian pertama kali belajar mungkin kebingungan. "Ini tipe data masukkannya apa sih?, kok tiba tiba dikasih codingan untuk mesolve masalahnya?". Kira kira saya sendiri juga mengalami hal yang serupa

Setelah mencari tahu, ternyata memang ada library khusus di python yang memberikan kita kemudahan untuk membuat data binary tree lengkap dengan visualisasi pohonnya

Tak hanya itu, kita juga bisa mencoba memecahkan masalah dengan kode kode tertentu lewat struktur binary tree ini

Bagaimana langkah awal untuk mencobanya?

Install Library/Package

from binarytree import Node

binary tree ini bisa kalian lihat lebih lengkap ke dalamnya di repo Githubnya (jangan lupa juga untuk memberikan bintang). Saya tidak akan menjelaskannya lebih jauh, kalau mau kalian bisa baca baca sendiri hehehe

Jika sudah kalian bisa import Node dari package tersebut dengan perintah

from binarytree import Node

Membuat Susunannya

Misal kita ingin bikin binary tree seperti ini

Maka kita bisa menuliskan kode seperti berikut

Gambar 1

Kalian bisa mengira ngira bagaimana kode tersebut bekerja? Begini saya jelaskan

Node(6) merupakan data utama yang terletak paling atas binary tree. Kita bisa mendapatkan nilai 6 ini dengan mengetikan root.value. Mengapa? Karena kalo kalian sudah baca baca dokumentasinya. Kalian bisa menemukan bahwa binarytree ini memiliki struktur class seperti ini

Gambar 2

Sedangkan untuk untuk mengisi child kiri dan kanan kalian bisa memberikannya nilai satu persatu seperti pada Gambar 1

Setelah itu kalian bisa print variable root dan akan muncul hasil seperti ini

Gambar 3

Contoh Soal

Coba buat kode menggunakan python yang membalik struktur binary diatas menjadi gambar berikut

Jawaban

Kita bisa menulis function seperti berikut

Fungsi diatas menggunakan recursive. Kita menuliskan pngkondisian jika tree bernilai None maka fungsi akan berhenti jika tidak maka program akan mengalami infinite loop yang akan mengakibatkan laptop kita menjadi hang

Sebetulnya kita hanya membalik saja posisi yang semula left menjadi right dan right menjadi left. Jika proses ini dilakukan secara rekursif makan hasil binary tree yang kita inginkan bisa terlihat pada soal (Gambar 3)

Jalankan fungsi dan print variable root

Kesimpulan

Permasalahan reversed binary tree bisa dipecahkan dengan fungsi yang memanggilnya diri sendiri yaitu rekursif. Akan tetapi kita harus tentukan dan buat dulu struktur binary tree sebagai inputan kita

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: