Temu duga pengekodan: mereka bentuk modul tempahan meja restoran

Gesaan dan konteks yang sesuai

Ini ialah soalan reka bentuk peringkat rendah (LLD) dan pengekodan. Matlamatnya adalah untuk menukar tempahan, meja, selang masa dan senarai menunggu kepada objek dengan tanggungjawab yang jelas. Laporan temu duga awam pernah merangkumi reka bentuk tempahan restoran, manakala panduan OOD menekankan penjelasan skop, penyenaraian keperluan, kemudian memilih objek dan antara muka. Andaikan satu restoran, waktu operasi tetap dan modul dalam ingatan (in-memory); tambahkan ketahanan data (persistence) dan kawalan konkurensi jika penemu duga memintanya.

Perkara yang dinilai oleh penemu duga

• Sama ada anda mengasingkan Restaurant, Table, Reservation, Waitlist dan dasar peruntukan.
• Sama ada anda mengendalikan selang separuh terbuka (half-open), kapasiti, gabungan meja dan pelepasan selepas pembatalan dengan betul.
• Sama ada anda mereka bentuk mesin keadaan (state machine), permintaan idempoten dan tiada peruntukan berganda di bawah konkurensi.
• Sama ada ujian meliputi sempadan dan anda boleh menerangkan kerumitan serta titik lanjutan.

Penjelasan yang perlu ditanya terlebih dahulu

Tanya sama ada tetamu memilih meja tertentu atau hanya saiz kumpulan, dan sama ada meja boleh digabungkan. Jelaskan tempoh tempahan dan penimbal pembersihan, pengubahsuaian, ketibaan lewat, tidak hadir (no-show), pelanggan walk-in, susunan senarai menunggu dan percubaan semula permintaan. Sahkan ketepatan masa, zon masa, satu berbanding banyak restoran, dan sama ada ketahanan data merentas proses diperlukan.

Rangka kerja jawapan 30 saat

Saya akan mentakrifkan TimeRange yang tidak boleh diubah (immutable) dan mesin keadaan tempahan terlebih dahulu. AvailabilityService mengendalikan pertanyaan konflik, TableAllocator memilih mengikut kapasiti dan dasar, ReservationService mengatur cipta, batal dan pemberitahuan, manakala Waitlist mengurus calon secara berasingan. Penciptaan menggunakan kunci keidempotenan dan menyemak ketersediaan sekali lagi di dalam bahagian kritikal yang sama sebelum menduduki meja. Pembatalan hanya membenarkan peralihan yang sah dan melepaskan kapasiti. Ujian meliputi selang bersebelahan, permintaan serentak, pembatalan berulang dan kenaikan daripada senarai menunggu.

Jawapan mendalam langkah demi langkah

1. Modelkan masa, meja dan keadaan tempahan

Wakilkan tempahan dengan selang separuh terbuka [start, end), yang memerlukan start < end. Dua selang bertindih apabila a.start < b.end && b.start < a.end. Table menyimpan kapasiti, pengecam dan ketersediaan; Reservation menyimpan tetamu, saiz kumpulan, selang, meja dan keadaan. Keadaan boleh menjadi HELD, CONFIRMED, SEATED, CANCELLED dan NO_SHOW; tolak peralihan yang tidak sah.

2. Jadikan peruntukan boleh diganti

TableAllocator menerima meja calon dan permintaan. Pilihan lalai memilih meja terkecil yang muat, mengelakkan pembaziran; dasar lain boleh mengutamakan meja bersebelahan atau kebolehcapaian. Pengagih (allocator) tidak menulis tempahan, mengekalkan carian, keputusan dan ketahanan data secara berasingan dan bukannya mencipta satu kelas gergasi.

3. Laksanakan semakan konflik dan penciptaan

Tapis mengikut restoran, selang dan indeks meja, kemudian biarkan pengagih memilih. Penciptaan mengesahkan input, menggunakan penimbal pembersihan, mencipta kunci keidempotenan dan membaca semula ketersediaan di dalam satu kunci (lock) atau transaksi sebelum menulis. Ia tidak boleh mempercayai hasil carian yang lapuk. Invarian adalah jelas: satu meja mempunyai sifar tempahan CONFIRMED yang bertindih.

create(request, key):
  if idempotency.exists(key): return idempotency.result(key)
  range = TimeRange(request.start, request.end + cleanupBuffer)
  lock(restaurantId, range):
    table = allocator.choose(availableTables(range), request.partySize)
    if table is null: return WAITLISTED
    reservation = Reservation.confirm(request, table, range)
    store(reservation)
    idempotency.save(key, reservation.id)
    return reservation

4. Kendalikan pembatalan, kelewatan dan kenaikan daripada senarai menunggu

Pembatalan hanya membenarkan HELD atau CONFIRMED menjadi CANCELLED; mengulanginya mengembalikan hasil yang sama dan tidak menduplikasi pemberitahuan. Ketibaan mengubah keadaan kepada SEATED; masa tamat dasar boleh menjadikannya NO_SHOW dan melepaskan meja. WaitlistMatcher menggunakan peristiwa pelepasan, memadankan mengikut masa menunggu, saiz kumpulan dan keutamaan, kemudian menggunakan semula bahagian kritikal penciptaan yang sama supaya tempahan baharu tidak memperuntukkan meja secara berganda.

5. Uji dan terangkan kerumitan

Uji bahawa selang bersebelahan [19:00,20:00) dan [20:00,21:00) tidak berkonflik, input songsang ditolak, pembersihan meluaskan konflik, kunci keidempotenan berulang tidak mencipta tempahan tambahan, pembatalan menaikkan senarai menunggu paling banyak sekali, dan penciptaan serentak hanya mempunyai satu pemenang. Jika setiap meja menyimpan tempahan yang diisih, carian konflik satu meja adalah O(log n + k); dengan m meja calon, pemilihan dan penulisan adalah kira-kira O(m log n). Baldi kapasiti atau indeks selang boleh memperbaikinya.

Contoh jawapan berkualiti tinggi

Saya akan memodelkan TimeRange separuh terbuka yang tidak boleh diubah, mesin keadaan tempahan yang eksplisit dan dasar peruntukan yang boleh diganti. AvailabilityService menapis mengikut restoran, masa dan meja; TableAllocator memilih meja terkecil yang mencukupi; ReservationService membaca semula dan menulis di dalam satu kunci atau transaksi menggunakan kunci keidempotenan. Pembatalan, kelewatan dan ketidakhadiran melepaskan kapasiti melalui peralihan yang sah, dan pemadanan senarai menunggu menggunakan semula bahagian kritikal yang sama. Ujian meliputi selang bersebelahan, penimbal pembersihan, pembatalan berulang, penciptaan serentak dan perlumbaan senarai menunggu, dengan kerumitan terindeks dinyatakan.

Kesilapan biasa

• Meletakkan semua logik dalam Restaurant dengan tanggungjawab yang tidak jelas dan tanpa penggantian dasar.
• Menggunakan selang tertutup dan tersilap menandakan tempahan bersebelahan sebagai konflik.
• Mencari ketersediaan dan menulis kemudian tanpa menyemak semula pada sempadan penulisan.
• Menjadikan pembatalan tidak idempoten sehingga percubaan semula melepaskan meja atau memberitahu dua kali.
• Hanya melaksanakan tempahan tetamu sambil mengabaikan walk-in, kelewatan, ketidakhadiran dan senarai menunggu.
• Hanya menunjukkan rajah kelas tanpa invarian, ujian sempadan atau kerumitan.

Soalan susulan dan jawapan

Bagaimanakah anda akan menyokong gabungan meja?

Kembalikan set meja yang tersusun dan bukannya satu tableId, menambah kekangan untuk jumlah kapasiti, kebolehsambungan dan konflik merentas set tersebut. Kekalkan antara muka pengagih dan tambahkan pelaksanaan ComposableTableAllocator.

Bagaimanakah anda menghalang tempahan berganda merentas proses?

Pindahkan invarian konflik ke lapisan ketahanan data dengan kunci yang boleh disahkan atau kekangan transaksi pada meja dan masa. Kunci aplikasi boleh mengurangkan perebutan (contention) tetapi tidak boleh menjadi satu-satunya jaminan ketepatan.

Bagaimana jika pengguna mengklik cipta berulang kali?

Wajibkan kunci keidempotenan klien dan simpan hasilnya mengikut skop restoran dan pengguna. Kunci yang sama mengembalikan tempahan asal; kunci yang berbeza masih melalui semakan konflik yang dikongsi. Pengehadan kadar (rate limiting) bukan pengganti kepada keidempotenan perniagaan.

Bagaimanakah anda mengoptimumkan slot makan malam yang popular?

Lakukan pembahagian data (shard) mengikut restoran dan masa. Gunakan cache hanya untuk pembayang carian; penciptaan akhir kekal dalam bahagian kritikal yang konsisten secara ketat. Baldi kapasiti pra-kira dan calon senarai menunggu masih memerlukan semakan versi sebelum menulis.

Bagaimana jika pemberitahuan gagal selepas pembatalan?

Lakukan komit perubahan keadaan dan peristiwa outbox dalam satu transaksi; jadikan pengguna pemberitahuan idempoten dan boleh dicuba semula. Pelepasan meja tidak boleh menunggu kejayaan SMS; kegagalan dihantar ke percubaan semula dan baris gilir surat mati (dead-letter queue) yang boleh dilihat oleh pengendali.