Pertanyaan wawancara dengan perincian jawaban — Halaman 51 dari 52
Buka halaman 51 dari pembahasan pertanyaan dan jawaban wawancara Offer.cc lengkap dengan penalaran, detail implementasi, pertanyaan lanjutan, dan sumber publik.
Wawancara Koding: Menemukan Elemen Terbesar ke-K dalam Sebuah Array
Turunkan jawaban elemen terbesar ke-k dari pengurutan dan bounded heap hingga randomized three-way quickselect, dengan invarian partisi yang presisi, penanganan duplikat, trade-off kompleksitas, serta pengujian yang dapat dieksekusi.
Wawancara Koding: Menyalin Linked List dengan Pointer Acak
Pelajari cara melakukan deep-copy pada linked list dengan pointer acak menggunakan identity map, lalu turunkan optimasi penyisipan (interleaving), buktikan invarian-invariannya, dan pulihkan list asli dengan aman.
Wawancara Koding: Temukan Semua Critical Connection dalam Jaringan
Temukan setiap bridge dalam graf tak berarah menggunakan discovery time dan nilai low-link, lalu buktikan kondisi bridge yang ketat dan implementasikan DFS iteratif yang aman terhadap stack.
Wawancara Koding: Membalik Node dalam k-Group (Reverse Nodes in k-Group)
Selesaikan pembalikan node dalam k-group dengan dummy node, complete-group lookahead, dan pembalikan pointer terbatas, lalu buktikan mengapa bagian akhir (tail) yang tidak lengkap tetap tidak berubah.
Wawancara Coding: Bagaimana Cara Menemukan Persegi Panjang Terbesar dalam Histogram?
Dapatkan algoritma persegi panjang terbesar dalam histogram dari batas elemen lebih kecil terdekat, terapkan monotonic stack satu kali jalan (one-pass), dan buktikan kebenaran serta kompleksitas linearnya.
Wawancara Koding: Bagaimana Cara Menghitung Edit Distance dengan Pemrograman Dinamis?
Turunkan rekurensi edit-distance pada prefiks string, buktikan ketiga transisinya, dan implementasikan solusi TypeScript rolling-row dengan waktu O(mn) dan ruang O(min(m, n)).
Wawancara Koding: Bagaimana Cara Menemukan Longest Increasing Subsequence?
Turunkan invarian minimum-tail dari pemrograman dinamis kuadratik, lalu gunakan binary search, indeks pendahulu (predecessor), dan pengujian properti untuk mengimplementasikan serta membuktikan algoritma longest increasing subsequence dengan kompleksitas O(n log n).
Wawancara Coding: Bagaimana Cara Menyelesaikan Word Ladder dengan BFS Dua Arah?
Memodelkan Word Ladder sebagai graf tanpa bobot implisit, menurunkan BFS dari kontrak urutan terpendek, dan mengimplementasikan pencarian dua arah dengan frontier yang lebih kecil disertai bukti yang presisi, model biaya, dan pengujian adversarial.
Wawancara Koding: Bagaimana Cara Mengimplementasikan Cache LFU O(1)?
Implementasikan cache LFU dengan indeks kunci, bucket frekuensi, doubly linked list per bucket, dan penunjuk frekuensi minimum, lalu buktikan get dan put yang berkinerja O(1) yang diharapkan.
Wawancara Koding: Bagaimana Cara Menyelesaikan Minimum Window Substring?
Turunkan sliding window dengan panjang variabel dari baseline kuadratik, lacak frekuensi yang dibutuhkan dan kelas karakter yang terpenuhi, serta verifikasi solusi TypeScript yang dapat dieksekusi terhadap duplikat, input yang tidak memungkinkan, dan brute-force oracle.
Wawancara Koding: Bagaimana Cara Menyelesaikan Trapping Rain Water dengan Two Pointers?
Turunkan array prefix dan solusi two-pointer dari rumus air per kolom, buktikan mengapa batas terkecil yang diketahui aman untuk dimajukan, serta implementasikan dan verifikasi waktu O(n) dengan ruang bantu O(1).
Wawancara Koding: Bagaimana Cara Menggabungkan K Sorted Linked List?
Turunkan penggabungan O(N log k) dari invarian frontier, implementasikan dengan min-heap berukuran k, buktikan kebenarannya, dan bandingkan dengan pemindaian, penggabungan sekuensial, pengurutan, serta divide-and-conquer.
Wawancara Koding: Mengimplementasikan Algoritma Jalur Terpendek Dijkstra
Implementasikan Dijkstra dengan adjacency list, lazy heap deletion, dan rekonstruksi jalur; buktikan greedy invariant-nya serta jelaskan early exit, kompleksitas, dan batasan edge negatif.
Wawancara Koding: Bagaimana Cara Mengimplementasikan Union-Find dan Melacak Komponen Terhubung?
Turunkan Union-Find dari kueri konektivitas dinamis, implementasikan union, connected, dan penghitungan komponen dengan union by size dan path halving, serta jelaskan kebenaran, kompleksitas teramortisasi, pengujian, dan batasan penghapusan.
Wawancara Koding: Bagaimana Cara Menyelesaikan Sliding Window Maximum dengan Monotonic Deque?
Turunkan monotonic deque dari pendekatan brute-force dan heap, buktikan waktu O(n) dengan dominasi, invarian, dan analisis teramortisasi, serta implementasikan circular deque TypeScript yang benar-benar menggunakan ruang O(k).
Wawancara Coding: Menemukan Lowest Common Ancestor dari Binary Tree
Turunkan solusi postorder satu kali lintasan (one-pass) dari baseline jalur, buktikan dengan invarian subtree-return, dan tangani nilai duplikat, target yang hilang, pohon yang dalam, serta kueri berulang.
Wawancara Coding: Serialisasi dan Deserialisasi Pohon Biner
Rancang pengkodean preorder yang dapat dibalik dengan penanda null eksplisit, buktikan mengapa dekoder mengonsumsi tepat satu subpohon, dan tangani masukan yang tidak valid, pohon yang sangat dalam, serta format alternatif.
Wawancara Koding: Menemukan Median dari Aliran Data (Data Stream)
Pertahankan paruh bawah dalam max-heap dan paruh atas dalam min-heap, turunkan kompleksitas penyisipan O(log n) dan kueri O(1) dari invarian eksplisit, serta tangani kebenaran logika, edge case, dan pertanyaan lanjutan seputar sliding window.
Wawancara Koding: Menemukan Posisi Pertama dan Terakhir dengan Binary Search
Gunakan batas bawah (lower bound) dan batas atas (upper bound) untuk menangani duplikat, array kosong, dan target yang tidak ditemukan secara seragam, lalu buktikan solusi O(log n) dengan invarian interval setengah terbuka (half-open interval).
Wawancara Koding: Bagaimana Cara Menggabungkan Interval yang Tumpang Tindih?
Gabungkan interval tertutup yang saling tumpang tindih menggunakan pengurutan dan pemindaian rakus (greedy scan), lalu berikan justifikasi atas aturan titik akhir, invarian kebenaran, kompleksitas, dan kontrak non-mutasi sambil menangani skenario lanjutan bersarang, berantai, dan streaming.
Bagaimana Cara Menyelesaikan Course Schedule II dengan Topological Sort?
Turunkan topological sort Kahn dari prasyarat mata kuliah, buktikan invarian zero-indegree dan pemeriksaan siklusnya, serta tangani pertanyaan lanjutan mengenai beberapa kemungkinan urutan, tepi duplikat, dan semester paralel.
Mengimplementasikan Trie dengan Insert, Search, Prefix, dan Delete
Menurunkan Trie dari kebutuhan pencocokan eksak dan prefiks, mengimplementasikan penghapusan yang aman tanpa merusak jalur bersama, serta memverifikasi invarian penanda terminal, kompleksitas, dan kasus-kasus adversarial.
Mendesain Struktur Data untuk Item Frekuensi Top-K Dinamis
Turunkan struktur data top-k dinamis eksak dari rasio baca-tulis, lengkap dengan kode frequency-bucket yang dapat dijalankan, invarian, dan kompleksitas, lalu tentukan kapan memori terbatas memerlukan Space-Saving atau Count-Min Sketch.
Mengimplementasikan Bounded Blocking Queue yang Thread-Safe
Implementasikan bounded blocking queue dengan ring buffer, satu lock, dan dua condition, kemudian buktikan kebenarannya melalui state invariant, linearization point, spurious wakeup, dan semantik interupsi.