Wawancara coding: Bagaimana cara memaksimalkan reward dengan pekerjaan yang tidak tumpang tindih?

Prompt dan use case

Setiap pekerjaan adalah (start, end, reward). Pilih pekerjaan yang kompatibel dengan total reward maksimum; waktu selesai yang sama dengan waktu mulai berikutnya diperbolehkan. Untuk (1,3,50), (3,5,40), (2,6,100), dua pekerjaan pertama menang dengan reward 90. Ini adalah pertanyaan coding yang menguji pengurutan interval, pencarian pendahulu (predecessor lookup), dan pemrograman dinamis, terlepas dari bahasa implementasinya.

Materi algoritma publik menggunakan weighted interval/job scheduling sebagai latihan pemrograman dinamis dan pola interval, dan akun wawancara publik juga mencatat varian interval-scheduling. Nyatakan persyaratan yang dapat diverifikasi tanpa mengklaim frekuensi wawancara yang tidak dapat diverifikasi.

Apa yang dievaluasi oleh pewawancara

• Apakah Anda mengurutkan berdasarkan waktu selesai sehingga pekerjaan terakhir yang dipilih membentuk keputusan yang terurut.
• Apakah Anda mendefinisikan p(i), yaitu pekerjaan terakhir yang selesai tidak lebih lambat dari waktu mulai pekerjaan i.
• Apakah Anda membandingkan antara melewatkan dan mengambil pekerjaan saat ini, alih-alih secara greedy mengambil reward individual terbesar.
• Apakah binary search mengurangi pencarian pendahulu menjadi O(log n) dan apakah Anda dapat merekonstruksi pekerjaan yang dipilih.
• Apakah Anda menangani end == start, waktu selesai yang sama, input kosong, dan reward bernilai nol.

Klarifikasi sebelum menjawab

• Apakah waktu selesai dan mulai yang sama kompatibel? Jawaban ini mengasumsikan ya: end <= start.
• Apakah reward bisa bernilai negatif? Jika ya, izinkan secara eksplisit untuk tidak memilih pekerjaan apa pun, dengan baseline 0.
• Apakah hanya reward maksimum yang diperlukan? Artikel ini juga merekonstruksi himpunan pekerjaan; abaikan data parent jika tidak diperlukan.
• Apakah waktu berupa bilangan bulat? Pengurutan hanya membutuhkan komparabilitas; binary search tidak memerlukan bilangan bulat berurutan.
• Bisakah suatu pekerjaan dipilih dua kali? Asumsikan setiap pekerjaan input dapat dipilih paling banyak satu kali.
• Bisakah start > end terjadi? Tolak atau normalisasi sebelum rekurensi; jangan menyembunyikan data yang tidak valid.
• Bagaimana interval yang sama harus diurutkan? Gunakan tie-break yang stabil; reward optimal apa pun dapat diterima.

Kerangka jawaban 30 detik

"Saya mengurutkan pekerjaan berdasarkan end dan menetapkan dp[i] sebagai reward terbaik dari i pekerjaan pertama. Untuk pekerjaan i, lakukan binary search untuk pekerjaan terakhir yang selesainya paling lambat start[i]; sebut ukuran prefix kompatibelnya sebagai p. Hubungan rekurensinya adalah dp[i] = max(dp[i-1], reward[i] + dp[p]): lewati pekerjaan tersebut atau ambil bersama prefix kompatibelnya. Saya menyimpan penanda pilihan dan melakukan backtrack untuk memulihkan pekerjaan. Pengurutan dan setiap binary search membutuhkan waktu O(n log n) dan array menggunakan ruang O(n)."

Jawaban mendalam langkah demi langkah

Langkah 1: Jelaskan mengapa aturan greedy tidak cukup.

Greedy earliest-finish-time benar jika setiap pekerjaan memiliki nilai yang sama. Dengan reward yang berbeda, pekerjaan singkat bernilai rendah dapat menghalangi kombinasi yang lebih baik, sehingga waktu selesai lokal atau reward lokal saja tidak cukup.

Langkah 2: Tentukan state yang terurut.

Setelah pengurutan, misalkan dp[i] adalah nilai optimal untuk pekerjaan 0..i-1, dengan dp[0] = 0. Melewatkan pekerjaan i-1 langsung menghasilkan dp[i-1].

Langkah 3: Hitung pendahulu (predecessor).

Untuk pekerjaan i-1, temukan j < i-1 terbesar dengan end[j] <= start[i-1]. Lakukan binary search pada waktu selesai yang telah diurutkan dan kembalikan ukuran prefix kompatibelnya p; mengambil pekerjaan tersebut menghasilkan reward[i-1] + dp[p].

Langkah 4: Tulis relasi rekurensi dan rekonstruksi.

dp[0] = 0
for i = 1..n:
  skip = dp[i - 1]
  take = reward[i - 1] + dp[p(i - 1)]
  dp[i] = max(skip, take)
  chose[i] = take > skip

Lakukan backtrack dari i = n: jika chose[i] bernilai true, catat pekerjaan i-1 dan lompat ke p(i-1); jika tidak, kurangi i. Balikkan daftar yang terkumpul. Tentukan pemecah seri (tie-break) jika kedua reward bernilai sama.

Langkah 5: Buktikan kebenarannya.

Setiap solusi optimal atas i pekerjaan pertama bisa jadi mengecualikan pekerjaan i-1, menghasilkan paling banyak dp[i-1], atau menyertakannya. Dalam kasus terakhir, setiap pekerjaan lainnya berada di dalam p(i-1) pekerjaan pertama yang kompatibel, menghasilkan paling banyak reward[i-1] + dp[p(i-1)]. Rekurensi mengambil nilai yang lebih besar dari kasus-kasus menyeluruh ini. Dengan base case dp[0] = 0, induksi membuktikan bahwa setiap state adalah optimal.

Langkah 6: Lindungi batasan implementasi.

Pencarian pendahulu harus menggunakan <= agar pekerjaan yang berdekatan tetap kompatibel. Mulai dari nol untuk mendukung reward negatif dan himpunan kosong. Balikkan hasil backtracking karena rekonstruksi berjalan dari akhir.

Langkah 7: Analisis kompleksitas.

Pengurutan membutuhkan biaya O(n log n), dan satu binary search per pekerjaan juga membutuhkan total O(n log n). Array pemrograman dinamis, pendahulu, dan pilihan menggunakan ruang O(n). Sebutkan ukuran output secara terpisah jika dihitung.

Langkah 8: Identifikasi alternatif.

Jika waktu selesai berupa bilangan bulat kecil yang terbatas, pemindaian terindeks waktu dapat menghindari pengurutan berbasis perbandingan. Jika reward bernilai sama, greedy earliest-finish sudah cukup. Batasan paling banyak k pekerjaan atau beberapa sumber daya menambahkan dimensi state dan memerlukan rekurensi baru.

Contoh jawaban berkualitas tinggi

"Saya mengurutkan berdasarkan waktu selesai dan mendefinisikan dp[i] sebagai reward maksimum di antara i pekerjaan pertama. Untuk setiap pekerjaan, lakukan binary search untuk pendahulu terakhir dengan end <= start. Melewatkan menghasilkan dp[i-1]; mengambil menghasilkan reward[i] + dp[p(i)], jadi saya menyimpan nilai yang lebih besar dan mencatat pilihan untuk backtracking. Pembuktian mempartisi setiap solusi optimal berdasarkan apakah solusi tersebut memuat pekerjaan saat ini; jika ya, sisa pekerjaan harus berasal dari prefix yang kompatibel. Pengurutan dan binary search membutuhkan waktu O(n log n) dan ruang pembantu O(n). Saya menguji pekerjaan yang berdekatan, waktu selesai yang sama, reward negatif, tumpang tindih penuh, dan input kosong."

Kesalahan umum

• Greedy berdasarkan reward terbesar → satu pekerjaan dapat menghalangi kombinasi dengan jumlah yang lebih tinggi → bandingkan ambil dan lewati dengan DP.
• Menganggap waktu selesai/mulai yang sama sebagai konflik → pekerjaan bersebelahan yang valid hilang → gunakan end <= start.
• Hanya mengurutkan berdasarkan waktu mulai → dp[i-1] tidak lagi mendeskripsikan prefix yang stabil → urutkan berdasarkan waktu selesai.
• Pemindaian pendahulu secara linear → total waktu menjadi O(n²) → lakukan binary search pada waktu selesai.
• Menginisialisasi dari reward pertama → input yang semuanya bernilai negatif tidak dapat memilih himpunan kosong → set dp[0] = 0.
• Lupa membalikkan hasil backtracking → pekerjaan yang dipilih dikembalikan dalam urutan terbalik → balikkan setelah pengumpulan.
• Membiarkan tie reward bernilai sama tanpa spesifikasi → output berubah di berbagai eksekusi → tetapkan aturan tie-break.
• Mengklaim satu dimensi dapat menangani batas sumber daya → batasan tambahan tidak terwakili → tambahkan dimensi atau model ulang.

Pertanyaan lanjutan dan tanggapan

Pertanyaan lanjutan 1: Mengapa aturan batas yang sama (equal-boundary) aman?

Jika satu pekerjaan selesai tepat saat pekerjaan lain dimulai, keduanya tidak tumpang tindih berdasarkan konvensi yang dinyatakan. Oleh karena itu pengujian pendahulu harus menyertakan kesetaraan; mengubahnya menjadi < akan menyelesaikan masalah yang berbeda.

Pertanyaan lanjutan 2: Bisakah ini selalu menjadi O(n)?

Dengan waktu bilangan bulat kecil yang terbatas, pemindaian waktu langsung dapat menjadi linear. Dalam model perbandingan umum, pengurutan itu sendiri membutuhkan biaya O(n log n), jadi jangan menjanjikan waktu linear tanpa syarat.

Pertanyaan lanjutan 3: Bagaimana Anda merekonstruksi pekerjaan yang dipilih?

Simpan bit pilihan atau pointer parent. Dari i = n, ambil pekerjaan saat ini dan lompat ke pendahulunya, atau lakukan pengurangan indeks saat melewatkan; balikkan pekerjaan yang terkumpul.

Pertanyaan lanjutan 4: Bagaimana jika paling banyak k pekerjaan yang dapat dipilih?

Tambahkan dimensi hitungan seperti dp[i][c] untuk reward terbaik menggunakan c pekerjaan di antara i pekerjaan pertama. Waktu dan ruang akan meningkat sesuai penambahan tersebut.

Pertanyaan lanjutan 5: Bagaimana jika reward bergantung pada pekerjaan yang berdekatan?

Asumsi reward independen tidak lagi berlaku. Sertakan keterdekatan dalam state atau modelkan sebagai biaya transisi; rekurensi awal tidak dapat dibenarkan tanpa perubahan tersebut.

Pertanyaan lanjutan 6: Bagaimana jika semua pekerjaan memiliki waktu selesai yang sama?

Pengurutan yang stabil sudah cukup. Pendahulu mereka biasanya identik, dan rekurensi tetap membandingkan setiap kandidat. Untuk interval yang identik, hanya reward terbaik yang penting.

Pertanyaan lanjutan 7: Kapan pendekatan greedy benar?

Ketika semua reward bernilai sama dan tujuannya adalah memilih jumlah pekerjaan terbanyak, greedy earliest-finish memiliki argumen pertukaran (exchange argument). Dengan reward yang tidak sama, gunakan pemrograman dinamis berbobot.