Wawancara coding: Bagaimana cara mengimplementasikan kalender yang menolak tumpang tindih?

Petunjuk dan konteks

Implementasikan kalender di mana book(start, end) mengembalikan true dan menyimpan interval hanya jika tidak tumpang tindih dengan interval yang ada. Interval bersifat setengah terbuka dan memerlukan start < end; [10, 20) dan [20, 30) saling bersebelahan. Masalah ini menguji struktur berurutan, batas interval, waktu penyisipan, dan kompleksitas.

Hal yang diuji oleh pewawancara

Kuncinya adalah kondisi tumpang tindih yang dapat dibuktikan: dengan nilai start yang terurut, hanya predecessor dan successor terdekat yang perlu diperiksa. Jawaban yang kuat membandingkan pemindaian (scan), balanced tree, dan sorted array, lalu mencatat bahwa layanan multi-threaded atau persisten menambahkan persyaratan atomisitas dan penguncian (locking).

Pertanyaan untuk klarifikasi

Apakah waktu berupa bilangan bulat atau timestamp, dan apakah nilainya bisa negatif?
Apakah start < end harus divalidasi, dan apa yang terjadi pada input yang tidak valid?
Apakah interval benar-benar setengah terbuka, sehingga memperbolehkan titik akhir yang sama saling bersentuhan?
Berapa banyak pemesanan dan berapa rentangnya; apakah pembatalan atau kueri diperlukan?
Apakah ini single-threaded di memori atau layanan multi-proses yang persisten?

Jawaban 30 detik

Saya akan menggunakan map yang diurutkan berdasarkan start. Untuk [s, e), cari successor pertama dengan start minimal s; jika start-nya di bawah e, interval tersebut tumpang tindih. Kemudian periksa predecessor; jika end-nya di atas s, keduanya tumpang tindih. Sisipkan hanya jika kedua pemeriksaan lolos. Semantik setengah terbuka memungkinkan end predecessor sama dengan s dan start successor sama dengan e. Balanced tree memberikan pencarian dan penyisipan O(log n) dengan ruang O(n).

Jawaban mendalam langkah demi langkah

Langkah 1: Mendefinisikan tumpang tindih

Interval setengah terbuka [a, b) dan [c, d) tumpang tindih tepat saat a < d && c < b. Setelah nilai start terurut, predecessor dan successor langsung sudah cukup karena interval yang lebih jauh berakhir lebih awal atau dimulai lebih lambat.

Langkah 2: Memilih struktur berurutan

Balanced tree atau TreeMap di Java menyediakan pencarian predecessor dan successor. Sorted array memiliki pencarian O(log n) tetapi penyisipan O(n); pemindaian bernilai O(n). Sesuaikan pilihan dengan volume pemesanan dan kombinasi operasi.

Langkah 3: Periksa sebelum menyisipkan

Periksa successor, lalu predecessor, dan tulis hanya setelah keduanya lolos. Menyisipkan lalu melakukan rollback kemudian dapat mengekspos status perantara yang tidak valid.

java

boolean book(int start, int end) {
  if (start >= end) return false;
  var next = events.ceilingEntry(start);
  if (next != null && next.getKey() < end) return false;
  var prev = events.floorEntry(start);
  if (prev != null && prev.getValue() > start) return false;
  events.put(start, end);
  return true;
}

Langkah 4: Membuktikan perilaku batas

next.start == end dan prev.end == start tidak tumpang tindih. Start yang sama tidak dapat menggantikan interval lama yang berpotongan karena pemeriksaan successor akan menolaknya. Gunakan tipe numerik yang aman jika timestamp dapat meluap (overflow).

Langkah 5: Menentukan kompleksitas

Pencarian predecessor, successor, dan penyisipan pada balanced tree bernilai O(log n), dengan ruang O(n). Sorted array mencari dalam O(log n) tetapi menyisipkan dalam O(n); pemindaian sederhana tetapi skalabilitasnya buruk. Sertakan pemanggilan yang ditolak dalam diskusi kompleksitas.

Langkah 6: Memperluas ke konkurensi dan persistensi

Pada satu mesin, kunci pemeriksaan dan penyisipan secara bersamaan. Di seluruh proses, gunakan transaksi, batasan unik (unique constraint), atau range lock; cache tidak boleh menjadi otoritas konflik akhir.

Pertimbangan kompromi dan batasan

Interval setengah terbuka versus tertutup

Interval setengah terbuka mengekspresikan slot yang bersebelahan secara alami, memiliki panjang end - start, dan menghindari duplikasi batas. Bisnis dengan interval tertutup harus mendefinisikan ulang granularitas secara konsisten.

TreeMap versus interval tree

Predecessor dan successor sudah cukup ketika setiap tumpang tindih ditolak. Kueri tumpang tindih, pembatalan, atau statistik rentang dapat menjustifikasi penggunaan interval tree atau indeks rentang basis data.

Rencana peluncuran dan bukti

Matriks pengujian

Cakup interval pertama, penahanan (containment), tumpang tindih parsial, titik akhir yang bersentuhan, start yang sama, input kosong, nilai besar, dan permintaan duplikat. Setelah setiap pemesanan yang diterima, pastikan invarian terurut tetap terpenuhi.

Batasan produksi

Untuk beberapa instans, tentukan isolasi transaksi, kesalahan konflik, kunci idempotensi percobaan ulang, dan aturan zona waktu. Lakukan uji beban pada batasan persisten di bawah pemesanan bersamaan.

Kesalahan umum dan tindak lanjut

Kesalahan: hanya memeriksa successor

Interval baru dapat tumpang tindih dengan bagian akhir predecessor, jadi nilai end pada predecessor juga harus diperiksa.

Kesalahan: memperlakukan titik akhir yang sama sebagai tumpang tindih

Semantik setengah terbuka memungkinkan [10, 20) dan [20, 30) bersentuhan; pertahankan perbandingan yang ketat.

Kesalahan: menyisipkan sebelum mendeteksi konflik

Pemeriksaan dan penulisan harus berupa satu langkah atomik yang logis untuk menjaga invarian.

Tindak lanjut: mengizinkan dua tumpang tindih

Pertahankan hitungan interval aktif atau gunakan sweep line; batasan tersebut berubah menjadi masalah tumpang tindih maksimum.

Tindak lanjut: pemesanan bersamaan

Kunci pada satu mesin; gunakan transaksi, range lock, atau penulisan serializable di seluruh instans daripada memori lokal proses.