Temuduga Pengekodan: Bagaimanakah Anda Mencari Persilangan Dua Senarai Selang yang Diisih?

Masalah dan konteks yang berkenaan

Anda menerima tatasusunan A dan B. Setiap item ialah selang tertutup [start, end]; kedua-dua tatasusunan diisih mengikut start yang tidak menurun, dan selang di dalam satu tatasusunan tidak bertindih. Kembalikan setiap selang yang diliputi oleh kedua-dua senarai, juga disusun mengikut masa mula.

Untuk A = [[1,5],[10,14]] dan B = [[2,3],[4,12]], persilangannya ialah [[2,3],[4,5],[10,12]]. Titik akhir yang sama dikira, jadi [1,2] dan [2,4] bersilang pada [2,2].

Perkara yang diuji oleh penemu duga

Penemu duga ingin melihat sama ada anda mengubah dua jujukan yang diisih menjadi imbasan dua penunjuk monotonik dan bukannya membandingkan setiap pasangan. Jawapan yang kukuh mentakrifkan semantik selang tertutup, mengira max(start) dan min(end), serta membuktikan sebab hanya selang dengan penghujung yang lebih awal boleh dibuang.

Penjelasan sebelum mengekod

1. Adakah selang tertutup atau separuh terbuka? Ini mengubah sama ada titik akhir yang sama menghasilkan output.
2. Adakah kedua-dua senarai diisih dan tidak bertindih secara dalaman? Jika tidak, isih atau gabungkan setiap senarai terlebih dahulu.
3. Bolehkah input kosong, mengandungi selang titik, atau mengandungi start > end? Ini menentukan pengesahan.
4. Patutkah persilangan panjang sifar dikekalkan? Masalah ini mengekalkannya kerana selang adalah tertutup.

Rangka kerja jawapan 30 saat

"Saya mengekalkan penunjuk i dan j. Persilangan semasa bermula pada mula yang lebih besar dan berakhir pada tamat yang lebih kecil; saya mengeluarkannya apabila titik akhir kiri tidak lebih besar daripada titik akhir kanan. Kemudian saya memajukan selang dengan tamat yang lebih kecil, kerana mula yang terkemudian tidak boleh bertindih dengan selang yang telah berakhir. Jika tamat adalah sama, saya memajukan kedua-duanya. Setiap penunjuk bergerak melalui senarainya sekali, jadi imbasan adalah O(m+n) dengan ruang kerja O(1) selain daripada output."

Analisis mendalam langkah demi langkah

Langkah 1: Tetapkan semantik selang

Anggap setiap selang sebagai [start,end]. Biarkan left = max(A[i].start, B[j].start) dan right = min(A[i].end, B[j].end). Persilangan wujud apabila titik akhir kiri tidak lebih besar daripada titik akhir kanan; titik akhir yang sama membentuk titik yang sah.

Langkah 2: Terbitkan pergerakan penunjuk

Jika A[i].end adalah kurang daripada B[j].end, A[i] tamat dahulu. Setiap selang terkemudian dalam B bermula tidak lebih awal daripada B[j], jadi A[i] tidak boleh bersilang dengan B[j+1] atau apa-apa selepasnya. Majukan i. Kes di mana B[j] tamat dahulu adalah simetri.

Langkah 3: Kendalikan penghujung yang sama

Apabila penghujung adalah sama, kedua-dua selang semasa tidak mempunyai masa berbaki yang boleh bertindih dengan selang terkemudian. Majukan kedua-dua penunjuk. Memajukan sebelah sahaja akan memeriksa semula selang yang telah selesai dan boleh menghasilkan perbandingan yang tidak perlu atau mengaburkan bukti.

Langkah 4: Tulis rangka kod yang boleh dilaksanakan

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 ketepatan

Pada permulaan setiap gelung, i dan j mengenal pasti pasangan terawal yang belum dibuktikan tidak boleh bersilang. [left,right] ialah satu-satunya persilangan yang mungkin bagi pasangan itu, jadi mengeluarkannya adalah lengkap untuk pasangan tersebut. Selepas membuang selang yang berakhir lebih awal, setiap pasangan yang dilangkau mempunyai mula yang lebih lewat daripada selang yang telah berakhir, jadi tiada persilangan yang hilang.

Langkah 6: Analisis kekompleksan dan pertahanan input

Penunjuk hanya bergerak ke hadapan, paling banyak m+n kali, jadi masa adalah O(m+n). Ruang kerja ialah O(1) tidak termasuk output, atau O(k) termasuk k selang yang dikeluarkan. Jika pengisihan dan titik akhir yang sah tidak dijamin, sahkan atau normalkan terlebih dahulu; bukti linear tidak terpakai kepada input sewenang-wenangnya.

Contoh jawapan berkualiti tinggi

Saya mula-mula akan mengesahkan selang tertutup, mula yang diisih, dan tiada pertindihan dalam mana-mana senarai. Untuk A[i] dan B[j], persilangan menggunakan mula yang lebih besar dan tamat yang lebih kecil; dengan titik akhir tertutup, titik akhir yang tidak lebih besar daripada titik akhir yang satu lagi masih mengeluarkan titik. Saya kemudian memajukan penunjuk yang selangnya tamat dahulu, kerana mula yang terkemudian tidak boleh bertindih dengan selang yang sudah selesai; tamat yang sama memajukan kedua-duanya. Setiap selang diproses sekali, memberikan masa O(m+n). Saya akan menguji input kosong, tiada pertindihan, titik akhir yang sama, selang titik, pembendungan (containment), dan beberapa persilangan berturut-turut.

Kesilapan lazim

• Kesilapan → keluarkan hanya apabila titik akhir kiri secara ketat lebih kecil → Mengapa ia gagal: persilangan satu titik bagi selang tertutup hilang → Pembetulan: sahkan kontrak dan kekalkan titik akhir yang sama.
• Kesilapan → mengimbas setiap selang B untuk setiap selang A → Mengapa ia gagal: pengisihan diabaikan dan masa menjadi O(mn) → Pembetulan: kekalkan penunjuk monotonik.
• Kesilapan → sentiasa menambah i → Mengapa ia gagal: B[j] mungkin tamat dahulu, menyebabkan perbandingan berulang atau output terlepas → Pembetulan: bandingkan tamat dan majukan yang lebih kecil, atau kedua-duanya jika sama.
• Kesilapan → mendakwa masa linear tanpa input yang diisih → Mengapa ia gagal: bukti penunjuk tidak lagi sah → Pembetulan: isih atau gabungkan setiap senarai terlebih dahulu.

Soalan susulan dan jawapan

Apakah yang berubah untuk selang separuh terbuka [start,end)?

Perlukan titik akhir kiri menjadi lebih kecil secara ketat; [1,2) dan [2,4) tidak mempunyai persilangan titik. Perbandingan tamat untuk pergerakan penunjuk boleh kekal sama, tetapi nyatakan kontrak titik akhir secara eksplisit.

Bolehkah anda mengekalkan O(m+n) jika setiap senarai tidak diisih dan bertindih?

Bukan secara langsung. Isih dan gabungkan setiap senarai terlebih dahulu, yang menelan kos sekurang-kurangnya O(m log m+n log n), kemudian jalankan imbasan dua penunjuk linear.

Bagaimana jika output sepatutnya merupakan jumlah panjang persilangan?

Kekalkan imbasan dan kumpulkan setiap right-left, diselaraskan mengikut konvensyen titik akhir. Bagi selang tertutup integer, jelaskan sama ada panjang bermaksud rentang geometri atau bilangan titik yang disertakan sebelum menulis formula.

Bagaimana jika kedua-dua senarai ialah strim yang tidak boleh diputar semula (rewind)?

Selagi setiap strim kekal diisih mengikut mula, simpan selang semasa dan kedudukan bacaan seterusnya sebagai keadaan penunjuk. Selepas mengeluarkan persilangan, buang selang yang telah berakhir; data yang tidak mengikut susunan memerlukan penimbalan (buffering) dan reka bentuk yang berbeza.