Wawancara Coding: Bagaimana Anda Membangun Task Scheduler yang Memperhatikan Dependensi?

Petunjuk dan ruang lingkup

Implementasikan TaskScheduler in-memory. Pemanggil mengirimkan ID tugas, ID dependensi, dan sebuah fungsi. Scheduler hanya boleh mengambil (claim) tugas setelah setiap dependensi berhasil. Sediakan operasi seperti submit, ready, complete, fail, dan cancel, serta laporkan siklus dependensi yang tidak akan pernah bisa dijalankan. Jelaskan penanganan pengiriman duplikat, propagasi kegagalan, batas konkurensi, shutdown, dan batasan restart.

Masalah ini menggabungkan penelusuran graf (graph traversal) dengan live state machine. Jawaban yang kuat memperjelas semantik status dan kegagalan sebelum memilih struktur data, kemudian memelihara derajat-masuk (indegree), edge terbalik (reverse edge), dan antrean siap jalan (ready queue). TopologicalSorter pada Python memperlakukan node tanpa pendahulu yang belum selesai sebagai node yang dapat diproses dan mengekspos siklus yang terdeteksi sebagai data diagnostik. Semantik tersebut membantu mendefinisikan kontrak, tetapi pengurutan topologis statis saja tidak cukup karena tugas selesai, gagal, dan dibatalkan seiring berjalannya waktu.

Hal yang diuji oleh pewawancara

Membedakan antara pending, ready, running, succeeded, failed, blocked, dan cancelled.
Memelihara invarian indegree dan ketetanggaan terbalik daripada memindai ulang setiap tugas.
Hanya melepaskan tugas dependen yang terpengaruh ketika suatu dependensi selesai.
Mendefinisikan propagasi siklus, kegagalan, dan pembatalan sebelum memilih API.
Membatasi worker, menjamin satu klaim per versi tugas, dan menangani pengiriman duplikat.
Memberikan batas kompleksitas dan pengujian untuk interleaving yang merugikan.

Pertanyaan klarifikasi

Apakah graf bersifat statis atau tugas dapat ditambahkan secara dinamis? Asumsikan semua tugas yang direferensikan telah dikirim sebelum penjadwalan dimulai; hanya versi baru yang boleh dikirim saat sedang berjalan.
Apa yang terjadi pada keturunan (descendants) setelah sebuah dependensi gagal? Jawaban ini menandainya sebagai blocked; percobaan ulang memerlukan generasi baru yang eksplisit.
Apakah pembatalan merambat ke setiap keturunan? Asumsikan pembatalan hanya membatalkan tugas tersebut; keturunan menjadi blocked ketika dependensi wajib dibatalkan.
Apakah kegagalan dicoba ulang secara otomatis? Tidak. Pemanggil mengirimkan generasi baru dan bertanggung jawab atas idempoten untuk efek samping.
Apakah ready() mengembalikan satu tugas atau satu batch? Kembalikan paling banyak maxConcurrency - running tugas dalam urutan deterministik.

Jawaban tiga puluh detik

Simpan status setiap tugas, jumlah dependensi yang belum selesai, dan daftar ketetanggaan terbalik. Sebelum penjadwalan, jalankan algoritma Kahn atau DFS tiga warna dan kembalikan jalur siklus jika ada. Masukkan tugas dengan indegree nol ke dalam antrean siap jalan yang stabil. Di bawah satu lock, klaim tugas dengan mengubah ready menjadi running; jika berhasil, kurangi hitungan setiap dependen dan masukkan ke antrean bagi yang mencapai nol. Kegagalan dan pembatalan menandai keturunan yang terpengaruh sebagai blocked. Setiap callback membawa informasi generasi sehingga worker usang tidak melepaskan dependen dua kali. Pool worker tetap atau semafor memberlakukan batasan konkurensi.

Solusi langkah demi langkah

Langkah 1: Tentukan status dan batasannya

Status bergerak maju: pending ke ready, lalu running, dan akhirnya succeeded atau failed. Pembatalan dapat terjadi saat pending atau ready; pembatalan fungsi yang sedang berjalan bersifat kooperatif. blocked berarti fungsi tidak dijalankan karena dependensi wajib tidak dapat berhasil lagi. Status terminal tidak pernah kembali ke ready, mencegah eksekusi duplikat.

Simpan generation per ID tugas. Pengiriman duplikat dapat ditolak atau membuat generasi baru; solusi ini memilih penggantian hanya selama versi lama tidak sedang berjalan. Versi yang sedang berjalan tidak dapat ditimpa secara diam-diam; kembalikan konflik atau tunggu callback terminalnya.

Langkah 2: Bangun indegree dan edge terbalik

Tabel tugas menyimpan remainingDeps; peta terbalik menyimpan dependents[dependencyId]. Daftarkan setiap edge sekali saja. Tugas dengan indegree nol masuk ke antrean siap jalan selama inisialisasi, dan perubahan berikutnya hanya memperbarui hitungan yang terpengaruh.

text

Task:
  id, generation, dependencies, dependents
  remainingDeps, state, fn, error

submit(task):
  validateUniqueDependencies(task)
  registerEdges(task)
  if task.remainingDeps == 0:
      task.state = READY
      readyQueue.push(task.id)

Dependensi yang tidak dikenal tidak boleh dianggap telah selesai. Biarkan dalam status waiting hingga dikirimkan, atau tolak dengan error UnknownDependency jika kontrak membutuhkan graf tertutup.

Langkah 3: Laporkan siklus sebelum eksekusi

Untuk graf statis, algoritma Kahn menyalin indegree, memproses node ber-indegree nol, dan menghapus edge keluarnya. Jika node yang diproses lebih sedikit dari total node, sisanya mengandung siklus. Kembalikan jalur konkret seperti A → B → C → A, bukan hanya boolean.

Sebagai alternatif, DFS putih-abu-abu-hitam menemukan edge abu-ke-abu dan merekonstruksi siklus melalui pointer induk. Jalankan deteksi sebelum tugas apa pun menjadi running. Larang penambahan edge setelah eksekusi dimulai kecuali kontrak membuat versi graf baru.

Langkah 4: Klaim tugas dan tegakkan batas konkurensi

ready() menghitung slot yang tersedia, mengambil tugas dalam urutan pengiriman yang stabil, dan mengubah setiap status menjadi running dalam critical section yang sama. Setelah dikembalikan, pemanggil lain tidak dapat mengklaim tugas tersebut. complete(id, generation) memvalidasi generasi dan status; callback yang terlambat dari worker lama mengembalikan konflik dan tidak dapat melepaskan dependen.

Gunakan jumlah worker tetap atau semafor untuk batas konkurensi. Panjang antrean bukan jumlah tugas aktif: hanya tugas running yang mengonsumsi slot. Jika batch yang diminta melebihi slot yang tersedia, kembalikan jumlah yang tersedia atau CapacityExceeded alih-alih menaikkan konkurensi secara diam-diam.

Langkah 5: Propagasikan keberhasilan, kegagalan, dan pembatalan

Jika berhasil, telusuri dependen langsung. Kurangi remainingDeps hanya untuk versi yang masih pending; masukkan node ke antrean saat hitungan mencapai nol. Jika gagal, kontrak ini menandai keturunan langsung dan transitif sebagai blocked dan mencatat penyebab pemblokiran pertama. Kebijakan dependensi alternatif hanya valid jika dinyatakan secara eksplisit.

Pembatalan memengaruhi versi yang belum dimulai. Fungsi yang sedang berjalan dapat menerima AbortSignal, tetapi hanya fungsi tersebut yang dapat mengonfirmasi keluar secara kooperatif. Keturunan menjadi blocked ketika dependensi wajib gagal atau dibatalkan; mereka tidak pernah berpura-pura bahwa dependensi tersebut berhasil.

Langkah 6: Buat pengiriman dan callback bersifat idempoten

Gunakan (taskId, generation) sebagai kunci idempotensi. Panggilan complete, fail, atau cancel yang berulang mengembalikan status terminal yang diketahui dan tidak mengurangi dependen dua kali. Saat mengganti versi pending, hapus edge terbalik lamanya sebelum mendaftarkan yang baru; hanya menimpa objek akan menyisakan edge usang dan dapat membuat dependen menunggu selamanya.

Jika pembaruan tidak diperlukan, menolak ID duplikat lebih sederhana. Nyatakan untung-ruginya (tradeoff): builder statis dapat menolak duplikat, sedangkan alur kerja yang berjalan lama biasanya membutuhkan generasi, catatan audit, dan versi coba ulang yang eksplisit.

Langkah 7: Shutdown, coba ulang, dan pemulihan

close() menolak pengiriman baru, menghentikan ready() dari mengklaim lebih banyak pekerjaan, dan menunggu callback yang sedang berjalan atau batas waktu (timeout) yang ditentukan. Tugas dalam antrean dibatalkan atau dipertahankan sesuai kontrak; mengosongkan memori tanpa mencatat alasan akan menghilangkan informasi. Percobaan ulang membuat generasi baru dan memeriksa ulang snapshot dependensi alih-alih mengubah failed kembali ke ready.

Scheduler in-memory tidak dapat pulih setelah proses crash. Persistensi memerlukan penyimpanan tugas, versi, status, dependensi, dan lease. Worker pemulihan mengklaim tugas dengan penulisan kondisional, dan fungsi tugas harus idempoten. Pemulihan dapat memberikan eksekusi setidaknya satu kali (at-least-once), bukan efek samping tepat satu kali (exactly-once).

Langkah 8: Kompleksitas dan pengujian

Inisialisasi graf adalah O(V + E). Setiap penyelesaian hanya memindai edge keluar, sehingga seluruh lintasan propagasi tetap O(V + E); antrean siap jalan berbasis heap melakukan klaim dalam O(log V). Kompleksitas ruang adalah O(V + E).

Uji graf kosong, cabang independen, rantai panjang, siklus, dependensi tidak dikenal, dua dependensi yang selesai bersamaan, propagasi kegagalan, pembatalan keturunan, callback duplikat, pengiriman duplikat, kapasitas nol, race condition saat shutdown, dan callback terlambat dari generasi lama. Model status kecil dapat membandingkan setiap set siap jalan dan memastikan paling banyak satu transisi pending → running per versi.

Jawaban model

Saya akan membekukan (freeze) graf terlebih dahulu, kemudian menyimpan status, generasi, jumlah dependensi yang tersisa, dan ketetanggaan terbalik untuk setiap tugas. Algoritma Kahn ditambah pointer induk akan melaporkan siklus konkret. Tugas tanpa dependensi masuk ke antrean siap jalan yang stabil. ready() mengklaim hingga slot konkurensi yang tersisa di bawah satu lock dan segera menandai tugas sebagai running. Callback penyelesaian harus cocok dengan generasi dan hanya boleh bertransisi satu kali; keberhasilan mengurangi hitungan downstream dan memasukkan node yang mencapai nol ke antrean. Kegagalan dan pembatalan menghasilkan keturunan blocked alih-alih keberhasilan palsu. Callback duplikat bersifat idempoten, percobaan ulang membuat generasi baru, dan shutdown menolak pekerjaan baru sebelum menyelesaikan callback yang sedang berjalan. Lintasannya adalah O(V + E) dan pengujian mencakup batasan konkurensi serta efek samping.

Kesalahan umum

Melakukan satu kali topological sort tanpa mendefinisikan transisi penyelesaian dan kegagalan secara langsung.
Memindai setiap node untuk kesiapan setelah setiap penyelesaian alih-alih menggunakan edge terbalik.
Hanya mengembalikan boolean siklus tanpa jalur diagnostik.
Menghilangkan generasi dari callback penyelesaian, memungkinkan worker usang melepaskan dependen.
Memperlakukan kegagalan dependensi sebagai keberhasilan dan menjalankan pekerjaan downstream tanpa prasyarat.
Mengklaim bahwa pembatalan fungsi yang sedang berjalan bersifat memaksa tanpa kontrak sinyal kooperatif.
Menambah jumlah worker untuk menyembunyikan backlog dan menghabiskan kapasitas downstream.
Menggunakan kembali status gagal untuk percobaan ulang tanpa semantik idempotensi, efek samping, atau lease.

Pertanyaan lanjutan

Bagaimana Anda menangani graf yang terlalu besar untuk memori?

Simpan metadata tugas dan edge secara persisten, dan muat hanya jendela aktif berdasarkan tenant atau partisi. Simpan kursor di memori. Klaim menggunakan penulisan kondisional atau lease singkat, dan penyelesaian tetap memeriksa generasi. Jelaskan dependensi lintas partisi, konsistensi paginasi, dan eksekusi duplikat setelah masa berlaku lease habis.

Bagaimana cabang yang gagal dapat berlanjut sementara node dependen berhenti?

Beri label pada edge sebagai wajib (required) atau opsional. Tugas menjadi siap jalan hanya setelah semua dependensi wajib berhasil dan dependensi opsional mencapai status terminal. Catat kegagalan opsional dalam ringkasan input dan metrik alih-alih menghapusnya secara diam-diam; ini memperluas state machine dan pengujian.

Bagaimana Anda menambahkan dependensi secara dinamis?

Izinkan edge baru hanya saat tugas berstatus pending, menambah indegree dalam critical section yang sama. Tolak perubahan pada tugas yang berstatus ready atau running. Jika perubahan saat runtime diperlukan, buat generasi baru dan jalankan terhadap graf baru setelah versi lama mencapai status terminal.

Bagaimana Anda membatalkan dependensi bersama tanpa mengganggu cabang yang tidak terkait?

Ubah hanya status terminal dependensi tersebut, lalu periksa hubungan edge wajib di sepanjang edge terbalik. Cabang tanpa dependensi tersebut tetap berlanjut; setiap tugas downstream yang membutuhkannya menjadi blocked. Audit siapa yang membatalkannya, kapan, dan di sepanjang jalur propagasi mana.

Bagaimana beberapa proses worker menghindari eksekusi ganda?

Klaim dengan pembaruan database atomik atau lease dan sertakan generasi dalam kondisinya. Lease dapat kedaluwarsa dan memungkinkan klaim lain, sehingga fungsi harus bersifat idempoten atau dapat dikompensasi. Lock in-memory hanya melindungi satu proses.

Sinyal observabilitas apa yang penting?

Lacak jumlah siklus, jumlah terblokir, waktu tunggu siap jalan, durasi eksekusi, konflik klaim, kedaluwarsa lease, callback duplikat, dan latensi propagasi per edge. Segmentasikan berdasarkan tipe tugas dan tenant agar rata-rata tidak menyembunyikan tail backlog, serta bedakan kesalahan konfigurasi graf dari kegagalan fungsi.

Bagaimana Anda membuktikan bahwa suatu tugas tidak diklaim dua kali?

Tempatkan pemeriksaan status, pengurangan slot, dan penulisan running dalam satu critical section atau pembaruan kondisional atomik, serta sertakan generasi dalam callback. Pengujian model dapat menginterleave dua panggilan ready() dan memastikan paling banyak satu transisi pending → running per versi; penyelesaian duplikat mengembalikan status terminal yang diketahui.