Wawancara coding: Bagaimana cara menemukan bilangan positif ke-k yang hilang dengan binary search?

Apa yang dievaluasi oleh pewawancara

Masalah di permukaan adalah menghitung dalam sebuah larik; intinya adalah mengubah "berapa banyak nilai yang hilang hingga indeks i" menjadi predikat monoton lalu mencari batasnya. LeetCode 1539 menyediakan pernyataan masalah publik dan entri set soal Amazon. Panduan SDE Amazon menekankan kode yang dapat dijalankan, tangguh, teruji, dan pemeriksaan edge-case. Sumber-sumber ini mendukung nilai persiapan, bukan klaim frekuensi wawancara tetap untuk perusahaan mana pun.

• Apakah Anda menulis missing(i) = arr[i] - i - 1.
• Apakah Anda membuktikan bahwa hitungan yang hilang tidak menurun (non-decreasing).
• Apakah Anda menangani jawaban yang berada di luar elemen larik terakhir.
• Apakah Anda membandingkan pemindaian, binary search, dan pembuatan langsung berdasarkan kontrak.

Kerangka jawaban 30 detik

Nyatakan bahwa larik menggunakan indeks berbasis nol. Hingga arr[i], ada arr[i] bilangan bulat positif dalam rentang nilai tetapi hanya i + 1 elemen yang teramati, sehingga jumlah yang hilang adalah arr[i] - i - 1. Lakukan binary search untuk indeks pertama dengan missing(i) >= k. Jika itu adalah i, jawabannya adalah k + i; jika tidak ada indeks yang memenuhinya, jawabannya berada setelah larik dan bernilai k + n. Pemindaian membutuhkan waktu O(n), binary search O(log n), dan keduanya menggunakan ruang ekstra O(1).

Pertanyaan klarifikasi sebelum menjawab

1. Apakah larik dijamin strictly increasing dan positif? Jika tidak, pengurutan atau deduplikasi akan mengubah kontrak.
2. Apakah k bernilai positif, dan dapatkah nilai-nilainya melebihi rentang bilangan bulat aman bahasa pemrograman?
3. Apakah hanya satu nilai yang dibutuhkan, atau semua nilai yang hilang? Mengembalikan semua nilai memiliki biaya output.
4. Bisakah input berupa streaming tanpa akses acak? Hal itu mungkin lebih menguntungkan pemindaian.
5. Apakah larik asli harus tetap tidak berubah? Solusi binary search tidak memutasinya.

Pembahasan mendalam langkah demi langkah

Langkah 1: Bangun rumus hitungan yang hilang

Jika larik kontinu, arr[i] akan sama dengan i + 1. Perbedaannya adalah jumlah bilangan bulat positif yang hilang dari [1, arr[i]]:

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

Untuk arr = [2, 3, 4, 7, 11] dan i=3, missing(3) = 7 - 3 - 1 = 3; nilai yang hilang adalah 1, 5, dan 6.

Langkah 2: Gunakan monotonisitas untuk mencari batas

Kenaikan ketat menghasilkan arr[i+1] >= arr[i] + 1. Oleh karena itu missing(i+1) >= missing(i), sehingga hitungannya tidak pernah berkurang. Cari indeks pertama dengan missing(i) >= k: semua yang ada sebelumnya memiliki nilai hilang yang terlalu sedikit, sedangkan indeks tersebut dan semua setelahnya memiliki setidaknya k.

Langkah 3: Pulihkan jawaban dari batas

Misalkan batasnya adalah i. Terdapat i elemen larik yang teramati sebelumnya, dan kurang dari k nilai yang hilang sebelum batas tersebut. Oleh karena itu, nilai hilang ke-k adalah k + i. Jika tidak ada batas yang ada, jumlah hilang akhir masih di bawah k; semua n elemen yang teramati berada sebelum jawaban, sehingga hasilnya adalah k + n.

Langkah 4: Terapkan binary search

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

Menggunakan right = n memungkinkan batas berada tepat setelah larik. Saat terminasi, left adalah posisi pertama yang hitungan hilangnya mencapai k, sehingga rumus k + left yang sama menangani kedua kasus tersebut.

Langkah 5: Buktikan kompleksitas dan uji batas

Setiap iterasi membagi dua interval pencarian, menghasilkan waktu O(log n) dan variabel ekstra konstan. Uji arr = [1,2,3,4], k = 2 untuk 6, arr = [2,3,4,7,11], k = 5 untuk 9, urutan yang hilang dari 1, bagian akhir yang kontinu, k=1, dan larik dengan satu elemen. Periksa juga batas bilangan bulat dalam bahasa yang dipilih.

Model jawaban berkualitas tinggi

Saya akan mendefinisikan jumlah bilangan bulat positif yang hilang hingga indeks i sebagai arr[i] - i - 1. Karena larik strictly increasing, hitungan tersebut monoton, jadi saya melakukan binary search untuk indeks pertama yang hitungannya minimal k. Jika batasnya adalah i, nilai hilang ke-k adalah k + i; menetapkan batas kanan ke n secara alami menangani jawaban setelah nilai maksimum larik.

Saya menggunakan interval setengah terbuka [left, right). Ketika missing(mid) kurang dari k, batas berada di sebelah kanan; jika tidak, saya mempertahankan mid. Hasilnya adalah k + left, dalam waktu O(log n) dan ruang O(1). Saya menguji celah di awal, celah di akhir, larik kontinu, satu elemen, dan beberapa nilai k, serta membandingkannya dengan oracle berbasis pemindaian.

Kesalahan umum

• Menulis arr[i] - i dan melewatkan suku pengurangan satu.
• Mencari posisi false terakhir tetapi menggunakan rumus jawaban true pertama.
• Menyetel right ke n - 1 dan salah menangani jawaban setelah larik.
• Menerapkan rumus ketika input tidak terurut atau berisi duplikat.
• Hanya menguji contoh dan melewatkan [1,2,3], [2], atau bagian akhir yang kontinu.
• Mengklaim binary search selalu lebih cepat tanpa membahas input yang terurut dan konstanta n kecil.

Trade-off implementasi

Pilih pemindaian linear atau binary search berdasarkan ukuran data dan kontrak batas, lalu verifikasi invarian dengan pengujian.

Pertanyaan lanjutan dan jawaban

Mengapa hitungan yang hilang bersifat monoton?

Kenaikan ketat berarti nilai berikutnya bertambah setidaknya satu. Ketika indeks bertambah satu, nilainya juga bertambah setidaknya satu, sehingga arr[i] - i - 1 tidak dapat berkurang.

Bagaimana jika larik tidak terurut atau memiliki duplikat?

Ubah kontraknya terlebih dahulu: urutkan, hapus duplikat, dan pertahankan nilai positif. Pengurutan memakan biaya setidaknya O(n log n); barulah setelah itu rumus hitungan hilang asli berlaku. Jangan mengklaim O(log n) untuk input yang tidak terurut.

Kapan pemindaian linear lebih disukai?

Untuk larik pendek, satu kueri, atau aliran data tanpa akses acak, pemindaian lebih sederhana. Binary search mengasumsikan input terurut dengan akses acak serta memiliki biaya penyiapan dan konstanta.

Bagaimana Anda mengembalikan k nilai hilang pertama?

Temukan batas nilai, lalu buat nilai dengan pointer larik dalam waktu output O(k). Pekerjaan output tidak dapat disembunyikan di dalam klaim O(log n).

Bagaimana Anda mencegah overflow untuk k atau nilai yang besar?

Gunakan tipe integer aman atau 64-bit dan periksa k + left serta arr[i] - i - 1. Jika presisi arbitrer diizinkan, tentukan BigInt atau representasi yang setara di antarmuka dan pengujian.

Rubrik penilaian

Kandidat yang kuat menurunkan predikat monoton, mengimplementasikan pencarian setengah terbuka, dan menjelaskan rumus jawaban. Kandidat yang hanya mengingat kode dan tidak dapat membuktikan batas memerlukan penelusuran lebih lanjut.