Soalan temu duga dengan huraian jawapan — Halaman 51 daripada 52
Layari halaman 51 pecahan soalan dan jawapan temu duga Offer.cc dengan hujah, butiran pelaksanaan, soalan susulan dan sumber awam.
Temuduga Pengekodan: Mencari Elemen Ke-K Terbesar dalam Suatu Tatasusunan
Terbitkan jawapan elemen ke-k terbesar daripada pengisihan dan bound heap kepada randomized three-way quickselect, dengan varian pemetakan yang tepat, pengendalian duplikasi, kompromi kekompleksan, dan ujian yang boleh dilaksanakan.
Temu Duga Pengekodan: Menyalin Pautan Senarai dengan Penunjuk Rawak
Ketahui cara melakukan deep-copy pada linked list dengan penunjuk rawak menggunakan peta identiti, kemudian terbitkan pengoptimuman penyisipan (interleaving), buktikan invariannya, dan pulihkan senarai asal dengan selamat.
Temuduga Pengekodan: Cari Semua Critical Connection dalam Rangkaian
Cari setiap bridge dalam graf tidak berarah dengan masa penemuan dan nilai low-link, kemudian buktikan syarat bridge yang ketat dan laksanakan DFS lelaran yang selamat daripada limpahan tindanan (stack-safe).
Temu Duga Pengekodan: Songsangkan Nod dalam Kumpulan-k (Reverse Nodes in k-Group)
Selesaikan penyongsangan nod dalam kumpulan-k dengan nod dummy, tinjauan hadapan kumpulan lengkap (complete-group lookahead), dan penyongsangan penunjuk berbatas, kemudian buktikan sebab bahagian ekor yang tidak lengkap kekal tidak berubah.
Temuduga Kod: Bagaimana Anda Mencari Segi Empat Terbesar dalam Histogram?
Terbitkan algoritma segi-empat-terbesar-dalam-histogram daripada sempadan-lebih-kecil-terdekat, laksanakan timbunan monoton satu-laluan, dan buktikan ketepatan serta kerumitan linearnya.
Temu Duga Pengekodan: Bagaimana Anda Mengira Edit Distance dengan Pengaturcaraan Dinamik?
Terbitkan rekurens edit-distance ke atas awalan rentetan, buktikan tiga peralihannya, dan laksanakan penyelesaian TypeScript rolling-row dengan masa O(mn) dan ruang O(min(m, n)).
Temu Duga Pengekodan: Bagaimana Anda Mencari Subjujukan Meningkat Terpanjang (Longest Increasing Subsequence)?
Terbitkan invariant minimum-tail daripada pengaturcaraan dinamik kuadratik, kemudian gunakan carian binari, indeks pendahulu, dan ujian sifat untuk melaksana serta membuktikan algoritma longest increasing subsequence O(n log n).
Temu Duga Pengekodan: Bagaimanakah Anda Menyelesaikan Word Ladder dengan BFS Dwi-arah?
Modelkan Word Ladder sebagai graf tanpa wajaran tersirat, terbitkan BFS daripada kontrak jujukan terpendek, dan laksanakan carian dwi-arah sempadan (frontier) lebih kecil dengan bukti yang tepat, model kos, dan ujian adversarial.
Temu Duga Pengekodan: Bagaimana Anda Melaksanakan Cache LFU O(1)?
Laksanakan cache LFU dengan indeks kunci, baldi kekerapan, senarai pautan berganda per baldi, dan penuding kekerapan minimum, kemudian buktikan get dan put dengan jangkaan O(1).
Temu Duga Pengekodan: Bagaimana Anda Menyelesaikan Minimum Window Substring?
Terbitkan tetingkap gelongsor (sliding window) bersaiz pemboleh ubah daripada garis dasar kuadratik, jejak kekerapan yang diperlukan serta kelas aksara yang dipenuhi, dan sahkan penyelesaian TypeScript yang boleh dilaksanakan terhadap pendua, input yang mustahil, dan orakel tenaga kasar (brute-force).
Temu Duga Pengekodan: Bagaimana Anda Menyelesaikan Trapping Rain Water dengan Two Pointers?
Terbitkan tatasusunan awalan dan penyelesaian two-pointer daripada formula air bagi setiap lajur, buktikan mengapa sempadan terkecil yang diketahui selamat untuk dimajukan, serta laksanakan dan sahkan masa O(n) dengan ruang bantuan O(1).
Temuduga Pengekodan: Bagaimana Anda Menggabungkan K Sorted Linked List?
Terbitkan penggabungan O(N log k) daripada invariant frontier, laksanakannya dengan min-heap bersaiz k, buktikan ketepatan, dan bandingkannya dengan pengimbasan, penggabungan berjujukan, pengisihan, serta divide-and-conquer.
Temu Duga Pengekodan: Melaksanakan Algoritma Laluan Terpendek Dijkstra
Laksanakan Dijkstra dengan adjacency list, lazy heap deletion, dan pembinaan semula laluan; buktikan greedy invariant-nya serta jelaskan early exit, kekompleksan, dan sempadan edge negatif.
Temuduga Pengekodan: Bagaimana Anda Melaksanakan Union-Find dan Menjejaki Komponen Bersambung?
Terbitkan Union-Find daripada pertanyaan ketersambungan dinamik, laksanakan union, connected, dan pengiraan komponen dengan union by size dan path halving, serta terangkan ketepatan, kekompleksan terpelunas, ujian, dan had pemadaman.
Temu Duga Pengekodan: Bagaimana Anda Menyelesaikan Sliding Window Maximum dengan Monotonic Deque?
Terbitkan monotonic deque daripada pendekatan brute-force dan heap, buktikan masa O(n) dengan dominasi, invarian, dan analisis terpelunasan, serta laksanakan circular deque TypeScript yang benar-benar menggunakan ruang O(k).
Temu Duga Pengekodan: Mencari Lowest Common Ancestor bagi Binary Tree
Terbitkan penyelesaian postorder satu laluan (one-pass) daripada garis dasar laluan, buktikannya dengan varian tak berubah (invariant) pulangan subpokok, dan kendalikan nilai pendua, sasaran yang hilang, pokok yang amat dalam, serta pertanyaan berulang.
Temuduga Pengekodan: Bersiri dan Nyahsiri Pokok Perduaan
Reka bentuk pengekodan preorder boleh balik dengan penanda null eksplisit, buktikan sebab penyahsiri menggunakan tepat satu subpokok, dan kendalikan input tidak sah, pokok mendalam, serta format alternatif.
Temuduga Pengekodan: Cari Median daripada Aliran Data
Kekalkan separuh bawah dalam max-heap dan separuh atas dalam min-heap, terbitkan kemasukan O(log n) dan pertanyaan O(1) daripada invarian yang jelas, serta tangani ketepatan, kes tepi, dan susulan tetingkap gelongsor.
Temu Duga Pengekodan: Cari Kedudukan Pertama dan Terakhir dengan Carian Perduaan
Gunakan batas bawah dan batas atas untuk mengendalikan duplikasi, tatasusunan kosong, dan sasaran yang tiada secara seragam, kemudian buktikan penyelesaian O(log n) dengan invarian selang separuh terbuka.
Temu Duga Pengekodan: Bagaimanakah Anda Menggabungkan Selang yang Bertindih?
Gabungkan selang tertutup yang bertindih dengan pengisihan dan imbasan tamak (greedy scan), kemudian berikan justifikasi untuk peraturan titik akhir, tak varian ketepatan, kekompleksan, dan kontrak tanpa mutasi sambil mengendalikan soalan susulan bersarang, berantai, dan penstriman.
Bagaimanakah Anda Menyelesaikan Course Schedule II dengan Topological Sort?
Terbitkan topological sort Kahn daripada prasyarat kursus, buktikan invariant zero-indegree dan semakan kitarannya, serta kendalikan soalan susulan tentang pelbagai susunan, sisi pendua, dan semester selari.
Melaksanakan Trie dengan Insert, Search, Prefix, dan Delete
Menerbitkan Trie daripada keperluan padanan tepat dan awalan, melaksanakan pemadaman selamat tanpa merosakkan laluan yang dikongsi, serta mengesahkan penanda terminal invarians, kekompleksan, dan kes-kes bertentangan (adversarial).
Reka Bentuk Struktur Data untuk Item Kerap Top-K Dinamik
Terbitkan struktur data top-k dinamik yang tepat berdasarkan nisbah baca-tulis, lengkap dengan kod baldi kekerapan (frequency bucket) yang boleh dijalankan, invarian, dan kerumitan, kemudian takrifkan bila memori terhad memerlukan Space-Saving atau Count-Min Sketch.
Melaksanakan Bounded Blocking Queue yang Selamat daripada Thread
Laksanakan bounded blocking queue menggunakan penimbal gelang, satu kunci (lock), dan dua syarat (conditions), kemudian buktikan ketepatannya melalui varian keadaan (state invariants), titik linearisasi (linearization points), spurious wakeups, dan semantik gangguan (interruption semantics).