Wawancara Koding: Bagaimana Cara Menemukan Irisan Dua Daftar Interval yang Terurut?

Masalah dan konteks yang berlaku

Anda menerima larik A dan B. Setiap item adalah interval tertutup [start, end]; kedua larik diurutkan berdasarkan start yang tidak menurun, dan interval di dalam satu larik tidak tumpang tindih. Kembalikan setiap interval yang dicakup oleh kedua daftar, yang juga diurutkan berdasarkan waktu mulai.

Untuk A = [[1,5],[10,14]] dan B = [[2,3],[4,12]], irisannya adalah [[2,3],[4,5],[10,12]]. Titik akhir yang sama tetap dihitung, sehingga [1,2] dan [2,4] beririsan di [2,2].

Apa yang sedang diuji oleh pewawancara

Pewawancara ingin melihat apakah Anda dapat mengubah dua urutan terurut menjadi pemindaian two-pointer monotonik daripada membandingkan setiap pasangan. Jawaban yang kuat mendefinisikan semantik interval tertutup, menghitung max(start) dan min(end), serta membuktikan mengapa hanya interval dengan titik akhir yang lebih awal yang dapat dibuang.

Klarifikasi sebelum menulis kode

1. Apakah interval bersifat tertutup atau setengah terbuka? Hal ini menentukan apakah titik akhir yang sama menghasilkan keluaran.
2. Apakah kedua daftar terurut dan tidak tumpang tindih secara internal? Jika tidak, urutkan atau gabungkan masing-masing daftar terlebih dahulu.
3. Bisakah masukan kosong, berisi interval titik, atau berisi start > end? Ini menentukan validasi.
4. Haruskah irisan dengan panjang nol dipertahankan? Masalah ini menyimpannya karena interval bersifat tertutup.

Kerangka jawaban 30 detik

"Saya mempertahankan pointer i dan j. Irisan saat ini dimulai dari nilai mulai yang lebih besar dan berakhir di nilai akhir yang lebih kecil; saya mengeluarkannya ketika titik akhir kiri tidak lebih besar dari titik akhir kanan. Kemudian saya memajukan interval dengan nilai akhir yang lebih kecil, karena nilai mulai setelahnya tidak dapat tumpang tindih dengan interval yang sudah berakhir. Jika nilai akhirnya sama, saya memajukan keduanya. Setiap pointer bergerak melintasi daftarnya satu kali, sehingga pemindaian berlangsung dalam waktu O(m+n) dengan ruang kerja O(1) di luar ruang keluaran."

Pembahasan mendalam langkah demi langkah

Langkah 1: Tetapkan semantik interval

Perlakukan setiap interval sebagai [start,end]. Misalkan left = max(A[i].start, B[j].start) dan right = min(A[i].end, B[j].end). Suatu irisan ada ketika titik akhir kiri tidak lebih besar dari titik akhir kanan; titik akhir yang sama membentuk titik yang valid.

Langkah 2: Turunkan pergerakan pointer

Jika A[i].end lebih kecil dari B[j].end, A[i] berakhir lebih dulu. Setiap interval berikutnya dalam B dimulai tidak lebih awal dari B[j], sehingga A[i] tidak dapat beririsan dengan B[j+1] atau interval apa pun setelahnya. Majukan i. Kasus di mana B[j] berakhir lebih dulu bersifat simetris.

Langkah 3: Tangani titik akhir yang sama

Ketika titik akhirnya sama, tidak ada interval saat ini yang memiliki sisa waktu untuk dapat tumpang tindih dengan interval berikutnya. Majukan kedua pointer. Memajukan hanya satu sisi akan memeriksa ulang interval yang sudah habis dan dapat menimbulkan perbandingan yang tidak perlu atau mengaburkan pembuktian.

Langkah 4: Tulis kerangka kode yang dapat dieksekusi

function intersect(A: number[][], B: number[][]): number[][] {
  const out: number[][] = [];
  let i = 0;
  let j = 0;

  while (i < A.length && j < B.length) {
    const left = Math.max(A[i][0], B[j][0]);
    const right = Math.min(A[i][1], B[j][1]);
    if (left <= right) out.push([left, right]);

    if (A[i][1] < B[j][1]) i++;
    else if (B[j][1] < A[i][1]) j++;
    else { i++; j++; }
  }
  return out;
}

Langkah 5: Nyatakan invarian untuk kebenaran

Pada awal setiap iterasi loop, i dan j mengidentifikasi pasangan paling awal yang belum terbukti tidak dapat beririsan. [left,right] adalah satu-satunya irisan yang mungkin dari pasangan tersebut, sehingga mengeluarkannya sudah lengkap untuk pasangan tersebut. Setelah membuang interval yang berakhir lebih awal, setiap pasangan yang dilewati memiliki awal yang lebih lambat daripada interval yang sudah berakhir, sehingga tidak ada irisan yang terlewat.

Langkah 6: Analisis kompleksitas dan pertahanan masukan

Pointer hanya bergerak maju, paling banyak m+n kali, sehingga waktu yang dibutuhkan adalah O(m+n). Ruang kerja adalah O(1) di luar keluaran, atau O(k) termasuk k interval yang dikeluarkan. Jika keterurutan dan titik akhir yang valid tidak dijamin, validasi atau normalisasi terlebih dahulu; pembuktian linier tidak berlaku untuk masukan sembarang.

Contoh jawaban berkualitas tinggi

Pertama, saya akan mengonfirmasi interval tertutup, urutan waktu mulai, dan tidak adanya tumpang tindih di dalam masing-masing daftar. Untuk A[i] dan B[j], irisannya menggunakan awal yang lebih besar dan akhir yang lebih kecil; dengan titik akhir tertutup, titik akhir yang tidak lebih besar dari titik akhir lainnya tetap menghasilkan sebuah titik. Kemudian saya memajukan pointer yang intervalnya berakhir lebih dulu, karena nilai awal setelahnya tidak dapat tumpang tindih dengan interval yang sudah selesai; nilai akhir yang sama memajukan keduanya. Setiap interval diproses satu kali, menghasilkan waktu O(m+n). Saya akan menguji masukan kosong, tidak ada tumpang tindih, titik akhir yang sama, interval titik, pembendungan (containment), dan beberapa irisan berturut-turut.

Kesalahan umum

• Kesalahan → mengeluarkan hasil hanya ketika titik akhir kiri secara ketat lebih kecil → Mengapa gagal: irisan titik tunggal pada interval tertutup akan hilang → Perbaikan: konfirmasikan kontrak dan pertahankan titik akhir yang sama.
• Kesalahan → memindai setiap interval B untuk setiap interval A → Mengapa gagal: keterurutan diabaikan dan waktu menjadi O(mn) → Perbaikan: pertahankan pointer yang monotonik.
• Kesalahan → selalu menambah i → Mengapa gagal: B[j] mungkin berakhir lebih dulu, menyebabkan perbandingan berulang atau keluaran terlewat → Perbaikan: bandingkan titik akhir dan majukan yang lebih kecil, atau keduanya jika sama.
• Kesalahan → mengklaim waktu linier tanpa masukan yang terurut → Mengapa gagal: bukti pointer tidak berlaku lagi → Perbaikan: urutkan atau gabungkan setiap daftar terlebih dahulu.

Pertanyaan lanjutan dan jawabannya

Apa yang berubah untuk interval setengah terbuka [start,end)?

Haruskan titik akhir kiri secara ketat lebih kecil; [1,2) dan [2,4) tidak memiliki irisan titik. Perbandingan akhir untuk pergerakan pointer tetap sama, tetapi nyatakan kontrak titik akhir secara eksplisit.

Bisakah Anda mempertahankan O(m+n) jika setiap daftar tidak terurut dan tumpang tindih?

Tidak secara langsung. Urutkan dan gabungkan setiap daftar terlebih dahulu, yang memerlukan biaya setidaknya O(m log m+n log n), lalu jalankan pemindaian two-pointer linier.

Bagaimana jika keluarannya harus berupa total panjang irisan?

Pertahankan pemindaian dan akumulasikan setiap right-left, disesuaikan dengan konvensi titik akhir. Untuk interval tertutup bilangan bulat, perjelas apakah panjang berarti rentang geometris atau jumlah titik yang disertakan sebelum menulis rumusnya.

Bagaimana jika kedua daftar berupa stream yang tidak dapat diulang kembali (rewind)?

Selama setiap stream tetap terurut berdasarkan waktu mulai, simpan interval saat ini dan posisi pembacaan berikutnya sebagai status pointer. Setelah mengeluarkan irisan, buang interval yang telah berakhir; data yang tidak berurutan memerlukan penyanggaan (buffering) dan desain yang berbeda.