Temu duga pengekodan: Bagaimana anda melaksanakan kalendar yang menolak pertindihan?

Gesaan dan konteks

Laksanakan kalendar di mana book(start, end) mengembalikan true dan menyimpan selang hanya apabila ia tidak bertindih dengan selang sedia ada. Selang adalah separuh terbuka dan memerlukan start < end; [10, 20) dan [20, 30) adalah bersebelahan. Masalah ini menguji struktur tertib, sempadan, masa pemasukan, dan kekompleksan.

Perkara yang diuji oleh penemu duga

Kuncinya ialah syarat pertindihan yang boleh dibuktikan: dengan nilai mula (starts) yang diisih, hanya pendahulu dan pengganti terdekat perlu diperiksa. Jawapan yang mantap membandingkan imbasan (scan), pokok seimbang, dan tatasusunan terisih, kemudian menyatakan bahawa perkhidmatan berbilang bebenang atau berterusan (persistent) menambah keperluan keatoman (atomicity) dan penguncian.

Soalan untuk penjelasan

Adakah masa dalam bentuk integer atau cap masa, dan bolehkah ia bernilai negatif?
Adakah start < end mesti disahkan, dan apakah yang berlaku pada input yang tidak sah?
Adakah selang benar-benar separuh terbuka, membenarkan titik akhir yang sama bersentuhan?
Berapakah bilangan tempahan dan apakah julatnya; adakah pembatalan atau pertanyaan diperlukan?
Adakah ini bebenang tunggal dalam ingatan atau perkhidmatan berbilang proses yang berterusan?

Jawapan 30 saat

Saya akan menggunakan peta yang disusun mengikut nilai mula. Untuk [s, e), cari pengganti pertama dengan nilai mula sekurang-kurangnya s; jika nilainya di bawah e, selang-selang tersebut bertindih. Kemudian periksa pendahulu; jika nilai tamatnya melebihi s, ia bertindih. Masukkan hanya apabila kedua-dua pemeriksaan lulus. Semantik separuh terbuka membenarkan tamat pendahulu sama dengan s dan mula pengganti sama dengan e. Pokok seimbang memberikan carian dan pemasukan O(log n) dengan ruang O(n).

Jawapan mendalam langkah demi langkah

Langkah 1: Tentukan pertindihan

Selang separuh terbuka [a, b) dan [c, d) bertindih tepat apabila a < d && c < b. Sebaik sahaja nilai mula diisih, pendahulu dan pengganti langsung adalah mencukupi kerana selang yang lebih jauh berakhir lebih awal atau bermula kemudian.

Langkah 2: Pilih struktur tertib

Pokok seimbang atau TreeMap dalam Java menyediakan carian pendahulu dan pengganti. Tatasusunan terisih mempunyai carian O(log n) tetapi pemasukan O(n); imbasan adalah O(n). Sesuaikan pilihan dengan volum tempahan dan gabungan operasi.

Langkah 3: Periksa sebelum memasukkan

Periksa pengganti, kemudian pendahulu, dan tulis hanya selepas kedua-duanya lulus. Memasukkan dahulu dan membuat pembalikan (rollback) kemudian boleh mendedahkan keadaan perantaraan yang tidak sah.

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: Buktikan tingkah laku sempadan

next.start == end dan prev.end == start tidak bertindih. Nilai mula yang sama tidak boleh menggantikan selang lama yang bersilang kerana pemeriksaan pengganti akan menolaknya. Gunakan jenis numerik yang selamat jika cap masa boleh melimpah (overflow).

Langkah 5: Nyatakan kekompleksan

Carian pendahulu, pengganti, dan pemasukan bagi pokok seimbang adalah O(log n), dengan ruang O(n). Tatasusunan terisih mencari dalam O(log n) tetapi memasukkan dalam O(n); imbasan adalah mudah tetapi berskala lemah. Sertakan panggilan yang ditolak dalam perbincangan kekompleksan.

Langkah 6: Lanjutkan kepada kekongruenan dan ketahanan

Pada satu mesin, kunci pemeriksaan dan pemasukan bersama-sama. Merentasi proses, gunakan transaksi, kekangan unik (unique constraint), atau kunci julat (range lock); cache tidak boleh menjadi penentu konflik yang muktamad.

Pertukaran dan sempadan

Selang separuh terbuka berbanding tertutup

Selang separuh terbuka menyatakan slot bersebelahan secara semula jadi, mempunyai panjang end - start, dan mengelakkan pertindihan sempadan. Perniagaan yang menggunakan selang tertutup mesti mentakrifkan semula keketulan (granularity) secara konsisten.

TreeMap berbanding pokok selang (interval tree)

Pendahulu dan pengganti sudah memadai apabila setiap pertindihan ditolak. Pertanyaan pertindihan, pembatalan, atau statistik julat mungkin mewajarkan penggunaan pokok selang atau indeks julat pangkalan data.

Pelan pelancaran dan bukti

Matriks ujian

Rangkumi selang pertama, pembendungan (containment), pertindihan separa, titik akhir bersentuhan, nilai mula yang sama, input kosong, nilai besar, dan permintaan pendua. Selepas setiap tempahan yang diterima, sahkan tak varian yang diisih.

Sempadan pengeluaran

Bagi berbilang tika (instances), takrifkan pengasingan transaksi, ralat konflik, kunci keidempotanan cuba semula, dan peraturan zon masa. Lakukan ujian beban terhadap kekangan berterusan di bawah tempahan serentak.

Kesilapan lazim dan tindakan susulan

Kesilapan: hanya memeriksa pengganti

Selang baharu boleh bertindih dengan bahagian ekor pendahulu, jadi nilai tamat pendahulu juga mesti diperiksa.

Kesilapan: menganggap titik akhir yang sama sebagai pertindihan

Semantik separuh terbuka membenarkan [10, 20) dan [20, 30) bersentuhan; kekalkan perbandingan yang ketat.

Kesilapan: memasukkan sebelum mengesan konflik

Pemeriksaan dan penulisan mestilah satu langkah atomik yang logik untuk mengekalkan tak varian.

Tindakan susulan: membenarkan dua pertindihan

Kekalkan kiraan selang aktif atau garis sapuan (sweep line); kekangan ini menjadi masalah pertindihan maksimum.

Tindakan susulan: tempahan serentak

Kunci pada satu mesin; gunakan transaksi, kunci julat, atau penulisan boleh siri (serializable) merentasi tika dan bukannya memori setempat proses.