Wawancara coding: perhentian pengisian bahan bakar minimum dengan max heap

Prompt dan konteks

Ini adalah masalah greedy dengan keterbatasan sumber daya. Bahan bakar hanya dapat diambil dari stasiun yang telah dilewati, dan tujuannya adalah jumlah perhentian, bukan total bahan bakar. Jawaban wawancara yang kuat menghubungkan ketercapaian, keputusan tertunda (lazy decisions), invarian max-heap, dan segmen akhir dari stasiun terakhir ke target.

Apa yang dievaluasi pewawancara

• Apakah Anda mengubah "mengisi bahan bakar hanya saat diperlukan" menjadi strategi lazy greedy.
• Apakah Anda membuktikan bahwa mengambil bahan bakar terbesar yang dilewati tidak dapat meningkatkan jumlah perhentian optimal.
• Apakah Anda menangani posisi awal, target, posisi duplikat, dan kasus yang tidak dapat dicapai.
• Apakah Anda menyediakan implementasi waktu O(n log n) dan ruang O(n).

Pertanyaan klarifikasi

Konfirmasikan bahwa stasiun diurutkan berdasarkan posisi, apakah posisi duplikat diperbolehkan, bahwa bahan bakar bernilai non-negatif, dan apakah target itu sendiri merupakan sebuah stasiun. Tanyakan tentang ukuran input dan rentang integer. Model default dimulai pada posisi 0 dan hanya mengizinkan bahan bakar dari stasiun setelah mencapainya.

Garis besar jawaban 30 detik

Pindai stasiun berdasarkan posisi dan masukkan (push) setiap jumlah bahan bakar yang dilewati ke dalam max heap. Sebelum mencapai setiap stasiun berikutnya atau target, kurangi jaraknya. Jika bahan bakar menjadi negatif, perhentian terpaksa dilakukan, jadi keluarkan (pop) bahan bakar terbesar yang telah dilewati secara berulang dan tambahkan hitungan perhentian. Jika heap kosong, kembalikan -1. Memilih bahan bakar terbesar yang tersedia pada setiap perhentian paksa memaksimalkan jarak yang dapat ditempuh tanpa menambah jumlah perhentian.

Solusi langkah demi langkah

1. Menetapkan invarian ketercapaian

Pada posisi p, heap berisi bahan bakar dari setiap stasiun pada atau sebelum p, sementara fuel adalah jumlah yang belum terpakai. Jika jumlah bahan bakar negatif, progres tidak mungkin dilakukan tanpa menggunakan salah satu dari stasiun tersebut. Setiap pop memperluas jangkauan yang dapat dicapai hingga jumlah bahan bakar menjadi non-negatif kembali.

2. Membuktikan pilihan lazy greedy

Misalkan sebuah rencana optimal memilih jumlah yang dilewati yang lebih kecil a saat harus mengisi bahan bakar, sementara jumlah yang lebih besar b tersedia. Ganti a dengan b: jumlah perhentian tidak berubah dan sisa bahan bakar setelah titik ini tidak berkurang, sehingga setiap segmen berikutnya tetap layak. Mengulangi pertukaran ini menghasilkan rencana yang sama optimalnya yang selalu memilih nilai maksimum.

3. Memperlakukan target sebagai batas

Tambahkan stasiun virtual (target, 0) dan proses persis seperti posisi lainnya. Mulai dari posisi 0, kurangi setiap jarak, dan baru setelah itu tambahkan bahan bakar stasiun. Jika target masih memerlukan pop, perhentian tersebut dihitung; heap yang kosong saat bahan bakar negatif berarti target tidak dapat dicapai.

4. Mengimplementasikan heap

heapq Python adalah min heap, sehingga nilai bahan bakar negatif mensimulasikan max heap. Setiap stasiun di-push satu kali dan di-pop hanya ketika perhentian diperlukan:

import heapq

def min_refuel_stops(target, start_fuel, stations):
    fuel = start_fuel
    previous = 0
    max_heap = []
    stops = 0

    for position, station_fuel in [*stations, (target, 0)]:
        fuel -= position - previous
        while fuel < 0 and max_heap:
            fuel += -heapq.heappop(max_heap)
            stops += 1
        if fuel < 0:
            return -1
        heapq.heappush(max_heap, -station_fuel)
        previous = position
    return stops

5. Menganalisis kompleksitas dan batas

Dengan n stasiun, setiap nilai bahan bakar masuk dan keluar dari heap paling banyak satu kali, menghasilkan waktu O(n log n) dan ruang heap O(n). Uji dengan bahan bakar awal yang cukup, stasiun pertama yang tidak dapat dicapai, perhentian yang diperlukan setelah stasiun terakhir, bahan bakar nol, posisi duplikat, kedatangan target yang tepat, dan target yang tidak dapat dicapai.

Contoh jawaban berkualitas tinggi

Saya akan menambahkan target sebagai stasiun virtual dengan bahan bakar nol. Selama pemindaian, kurangi jarak perjalanan dan push bahan bakar dari stasiun yang telah dicapai. Kapan pun sisa bahan bakar bernilai negatif, perhentian terpaksa dilakukan; ambil bahan bakar historis terbesar secara berulang hingga posisi saat ini dapat dicapai. Heap yang kosong berarti -1. Bukti pertukaran mengganti bahan bakar yang dilewati yang lebih kecil dengan yang lebih besar yang tersedia tanpa menambah perhentian atau mengurangi ketercapaian di masa mendatang. Setiap stasiun di-push dan di-pop paling banyak satu kali, sehingga kompleksitasnya adalah waktu O(n log n) dan ruang O(n).

Kesalahan umum

• Mengisi bahan bakar langsung di setiap stasiun alih-alih menunda keputusan.
• Hanya memeriksa celah antarstasiun dan melupakan celah target akhir.
• Mencampur bahan bakar saat ini yang belum terpakai dengan bahan bakar yang tersedia di heap.
• Menggunakan min heap dan mengambil jumlah terkecil.
• Menambahkan stasiun sebelum mencapainya dan menggunakan bahan bakar masa depan terlalu awal.
• Hanya menguji contoh yang dapat dicapai dan melewatkan batas heap kosong atau batas numerik.

Pertanyaan lanjutan

Mengapa tidak mengambil nilai maksimum di setiap stasiun?

Tujuannya adalah jumlah perhentian. Mengisi bahan bakar lebih awal dapat menambah perhentian tanpa meningkatkan ketercapaian. Menunda hingga bahan bakar tidak mencukupi memastikan setiap perhentian menjawab kendala yang sebenarnya.

Apa yang berubah jika pengisian bahan bakar parsial diperbolehkan?

Status dan fungsi biaya berubah. Harga atau kapasitas tangki mungkin berpengaruh, sehingga bukti untuk mengambil seluruh bahan bakar stasiun tidak lagi berlaku secara langsung.

Mengapa posisi duplikat tetap berfungsi?

Jaraknya adalah nol, sehingga dapat di-push dalam urutan apa pun. Heap tetap mengekspos jumlah terbesar yang tersedia saat segmen berikutnya benar-benar membutuhkan bahan bakar.

Bagaimana Anda akan mengembalikan perhentian yang sebenarnya?

Simpan indeks stasiun bersama setiap nilai heap dan catat indeksnya setiap kali di-pop. Urutkan indeks yang dicatat berdasarkan posisi atau urutan pemilihan untuk merekonstruksi rute.