Wawancara Coding: Bagaimana cara mengimplementasikan penjadwal tugas prioritas yang dapat dibatalkan?

Konsep dan cakupan

Implementasikan Scheduler simpul tunggal dengan schedule(taskId, runAt, priority, fn), cancel(taskId), dan next(). Pilih runAt paling awal, kemudian priority tertinggi, lalu urutan pengiriman (submission sequence). Hanya satu versi taskId yang valid. Tugas yang dibatalkan tidak boleh dimulai; saat tidak ada tugas yang jatuh tempo, next() mengembalikan petunjuk tunggu atau hasil kosong. Jelaskan lazy deletion, konkurensi worker, pemilihan clock, dan race condition saat shutdown.

Materi wawancara publik menyajikan penjadwalan tugas sebagai masalah gabungan yang melibatkan antrean prioritas, worker pool, pembatalan, dan penanganan kegagalan. Ini menguji kontrak siklus hidup dan konkurensi selain struktur data heap itu sendiri.

Apa yang sedang diuji oleh pewawancara

State machine untuk pending, running, cancelled, dan completed tanpa transisi ilegal.
Kunci deterministik (runAt, -priority, sequence) yang tidak pernah membandingkan objek tugas.
Pemeriksaan versi atau lazy deletion sehingga penggantian dan pembatalan tidak membocorkan pekerjaan yang basi (stale).
Perbedaan yang tepat antara membatalkan pekerjaan dalam antrean dan menghentikan fungsi yang sedang berjalan.
Bukti bahwa batas worker, urutan shutdown, dan pemilihan clock menjaga kontrak sistem.

Klarifikasi yang perlu ditanyakan terlebih dahulu

Apakah runAt merupakan tenggat waktu relatif monotonik atau waktu jam dinding (wall-clock)? Asumsikan clock monotonik untuk waktu tunggu.
Apakah fn menerima pembatalan? Asumsikan AbortSignal, hanya dengan penghentian kooperatif.
Apakah taskId duplikat menggantikan atau gagal? Versi ini menggantikan versi lama.
Apakah cancel langsung menghentikan fungsi yang sedang berjalan? Tidak; ini mencegah eksekusi yang belum dimulai dan memberi sinyal pada eksekusi yang sedang berjalan.
Apakah close menunggu pekerjaan yang sedang berjalan selesai? Asumsikan ini menolak pekerjaan baru dan menunggu worker selesai.

Jawaban 30 detik

Saya akan menyimpan (runAt, -priority, sequence, taskId, version) dalam min-heap dan menyimpan versi saat ini untuk setiap ID tugas dalam sebuah map. Menjadwalkan atau membatalkan akan memperbarui map dan membatalkan entri heap yang lama; next() berulang kali memvalidasi versi dan status sebelum memindahkan tugas yang jatuh tempo ke running. Sebuah dispatcher menggunakan clock monotonik untuk menunggu elemen teratas heap, lalu menyerahkan pekerjaan ke worker pool berukuran tetap. Pembatalan dalam antrean adalah jaminan yang kuat; pembatalan kode yang sedang berjalan bersifat kooperatif. Shutdown menolak pengiriman baru, membangunkan dispatcher, dan menunggu pembersihan selesai.

Pembahasan mendalam langkah demi langkah

Langkah 1: Tentukan kunci dan invarian

Gunakan (runAt, -priority, sequence) sebagai kunci heap. Urutan monotonik membuat stempel waktu dan prioritas yang sama menjadi deterministik. current[taskId] hanya menyimpan versi terbaru. Versi yang basi mungkin tetap berada di heap untuk sementara waktu, tetapi tidak akan pernah bisa bertransisi dari pending ke running.

Langkah 2: Tentukan penggantian dalam schedule

Setiap schedule membuat versi baru, menyimpannya di map, dan memasukkan entri heap baru. Tidak ada pencarian linier melalui array. Ketika sebuah entri di-pop, versinya dibandingkan dengan map. Penyisipan adalah O(log n) dan ID duplikat tidak dapat menghasilkan dua eksekusi yang valid.

text

schedule(id, runAt, priority, fn):
    version = nextVersion(id)
    current[id] = {version, state: pending, fn, runAt, priority}
    heappush(heap, (runAt, -priority, nextSequence(), id, version))

Langkah 3: Implementasikan cancel dan pembersihan head

Pembatalan menandai tugas tertunda saat ini sebagai cancelled dan membangunkan waiter. Ketika next() melakukan pop pada head, ia memeriksa apakah map masih menunjuk ke versi yang sama dan statusnya adalah pending. Entri yang basi, dibatalkan, dan digantikan akan dibuang. Lazy deletion menghindari pemindaian O(n), tetapi rasio entri basi harus dipantau dan dibangun kembali secara berkala.

Langkah 4: Batasi pekerjaan jatuh tempo dengan batas worker

Dispatcher tidak boleh menyerahkan pekerjaan masa depan kepada worker. Dispatcher menghitung penundaan ke head heap dengan clock monotonik. Setelah jatuh tempo, ia secara atomik mengubah pending menjadi running dan memasukkan tugas ke antrean worker berukuran tetap. Jumlah worker atau semaphore memaksakan batas konkurensi.

Langkah 5: Pisahkan pembatalan dari penghentian fungsi

Jika tugas dalam antrean dibatalkan sebelum transisi status, fn tidak pernah dipanggil. Tugas yang sedang berjalan hanya dapat menerima AbortSignal; fungsi harus memeriksanya atau meneruskannya ke I/O yang dapat dibatalkan. Catat cancelRequested, dan jangan laporkan penyelesaian sampai fungsi benar-benar selesai (returned).

Langkah 6: Urutkan close terhadap race condition

close pertama-tama memasuki closing dan menolak jadwal baru, kemudian membatalkan timer dan membangunkan dispatcher. Dispatcher berhenti mengambil tugas baru sementara worker menyelesaikan pekerjaan yang sudah diambil; baru setelah itu penjadwal menjadi closed. Jika pekerjaan dalam antrean harus segera dibuang, tandai entri map sebagai dibatalkan alih-alih hanya mengosongkan heap.

Langkah 7: Buktikan batas kompleksitas dan ruang

schedule normal adalah O(log n), cancel adalah pembaruan status O(1), dan next melakukan pekerjaan heap O(log n). Setiap entri basi di-pop paling banyak satu kali, sehingga pembersihan diamortisasi atas pembaruan atau pembatalan yang membuatnya. Bangun kembali dari entri map saat ini ketika ukuran heap melebihi kelipatan tetap dari tugas aktif.

Langkah 8: Uji interleaving penting

Uji pengurutan stabil untuk kunci yang sama, penggantian sebelum entri lama mencapai head, pembatalan tepat sebelum dan sesudah klaim tugas, tugas lebih awal yang menyela waktu tunggu, batas worker, kegagalan fungsi, pengiriman saat proses close, dan lompatan clock monotonik. Lakukan differential-test pada next() terhadap model referensi yang diurutkan dan catat puncak worker yang aktif.

Contoh jawaban berkualitas tinggi

Saya akan memisahkan state dari heap: sebuah map menyimpan versi terbaru untuk setiap taskId, sementara min-heap menyimpan (runAt, -priority, sequence, taskId, version). Penggantian menulis versi baru dan pembatalan menandai state; keduanya tidak memutasi array heap. Dispatcher hanya mengklaim tugas yang jatuh tempo dan memasukkannya ke antrean worker berukuran tetap. Validasi versi mencegah entri yang dibatalkan dan basi agar tidak berjalan, sementara AbortSignal memberikan pembatalan kooperatif untuk fungsi yang sedang berjalan. Shutdown menolak pekerjaan baru, berhenti mengklaim tugas, membangunkan waiter, dan menunggu pekerjaan yang diklaim selesai. Metrik melacak entri aktif versus ukuran heap sehingga lazy deletion tidak tumbuh tanpa batas.

Kesalahan umum

Mengurutkan hanya berdasarkan prioritas dan mengabaikan fakta bahwa runAt masih berada di masa depan.
Memutasi entri heap di tempat dan merusak invarian heap.
Hanya menghapus dari map, lalu mengeksekusi entri heap lama.
Memperlakukan panggilan cancel() yang berhasil sebagai bukti bahwa kode yang sedang berjalan telah berhenti.
Menggunakan waktu jam dinding untuk menunggu dan mengalami masalah koreksi clock.
Mengosongkan antrean pada close sambil membiarkan timer, dispatcher, atau worker tetap hidup.
Menjalankan worker tanpa batas dan mengubah penjadwal menjadi launcher tak terbatas.

Pertanyaan lanjutan dan jawaban

Bagaimana cara mencegah starvation pada pekerjaan berprioritas rendah?

Nyatakan bahwa prioritas ketat adalah perilaku default dan dapat menyebabkan kelaparan (starvation) pada tugas berprioritas rendah. Jika keadilan (fairness) diperlukan, tingkatkan prioritas efektif seiring waktu tunggu atau gunakan kuota berbobot (weighted quotas). Kedua pilihan tersebut mengubah kunci pengurutan dan bukti latensi, jadi tambahkan metrik dan pengujian.

Bagaimana cara mencegah eksekusi tumpang tindih untuk tugas berulang?

Tambahkan running lock atau generasi ke state tugas. Jika pemicu berikutnya tiba saat sedang berjalan, pilih secara eksplisit untuk melewati (skip), menggabungkan (coalesce) satu eksekusi yang tertunda, atau mengantrekan versi baru. Jangan pernah mengirimkan tanpa syarat jika tumpang tindih dilarang.

Bagaimana cara memulihkan sistem setelah proses crash?

Heap dalam memori hanya mencakup masa pakai proses. Persistensikan versi, state, dan waktu eksekusi berikutnya, bangun kembali heap saat startup, dan klaim dengan pembaruan bersyarat atau lease. Pemulihan biasanya menyediakan eksekusi setidaknya sekali (at-least-once), sehingga fungsi tugas harus idempoten.

Bagaimana cara memperluasnya ke beberapa node?

Ganti heap lokal dengan antrean persisten terindeks waktu dan gunakan lease atau penulisan bersyarat untuk kepemilikan. Biarkan lease yang kedaluwarsa dapat dicoba kembali setelah kegagalan node. Sertakan versi melalui pembatalan dan penggantian sehingga konsumen menolak pekerjaan basi, dan gunakan waktu penyimpanan atau jendela toleransi eksplisit antar-node.