Wawancara coding: Pengambilan sampel seragam pada persegi dan pemindaian subarray meningkat terpanjang

Petunjuk dan cakupan

Catatan wawancara publik membagi latihan ini menjadi dua tugas singkat: memanggil fungsi rand01() yang mengembalikan nilai seragam antara 0 dan 1 untuk mengambil sampel sebuah titik di dalam persegi dengan sisi side, kemudian menemukan segmen kontigu yang meningkat secara ketat terpanjang dari sebuah array. Artikel ini menempatkan sudut kiri bawah persegi pada (0, 0), memperlakukan sumber acak sebagai [0, 1), dan mengembalikan hasil kosong untuk array kosong.

Apa yang diuji oleh pewawancara

Latihan ini menggabungkan pemodelan probabilitas, pemetaan rentang, invarian satu kali lintasan (one-pass invariant), dan semantik hasil yang tepat. Catatan kuliah Cornell menjelaskan bahwa dua variabel seragam independen pada [0,1] membentuk sebuah titik yang seragam terhadap luas pada persegi satuan; materi probabilitas persegi MIT memberikan interpretasi luas yang sama. Pemindaian menguji apakah kandidat menjaga kontinuitas, memperlakukan kesetaraan nilai sebagai pemutus, dan memilih pemecah seri (tie-break) yang deterministik.

Pertanyaan klarifikasi yang perlu diajukan

1. Apakah rand01() bersifat tertutup atau setengah terbuka? Jawaban ini mengasumsikan [0, 1).
2. Apakah perseginya mengalami translasi? Jawaban ini dimulai dari titik asal; translasi hanya menambahkan offset.
3. Apakah peningkatan bersifat ketat (strict)? Jawaban ini memerlukan a[i] > a[i-1].
4. Deret terpanjang mana yang menang jika terjadi seri? Jawaban ini mengembalikan titik awal yang paling awal.
5. Apakah deduplikasi atau keacakan kriptografis diperlukan? Latihan dasar tidak memerlukan keduanya.

Jawaban 30 detik

“Saya memanggil rand01() secara independen dua kali dan mengalikan nilai-nilai tersebut dengan panjang sisi. Koordinat seragam yang independen membuat probabilitas setiap persegi panjang kecil sama dengan luasnya. Untuk array, saya menyimpan indeks awal dari deret meningkat ketat saat ini serta indeks awal/akhir terbaik. Nilai yang tidak meningkat mereset titik awal saat ini; saya memperbarui jawaban hanya ketika deret saat ini benar-benar lebih panjang. Pengambilan sampel adalah O(1), pemindaian adalah O(n), dan ruang ekstra adalah O(1). Saya akan menguji batas, nilai yang sama, input kosong, array monoton, dan hasil seri.”

Solusi langkah demi langkah

1. Menurunkan sampel seragam

Misalkan U dan V adalah variabel seragam independen pada [0,1). Untuk setiap persegi panjang sejajar sumbu [a,b) × [c,d), probabilitas jatuh di dalamnya adalah (b-a)(d-c), tepatnya seluas area tersebut. Oleh karena itu (side × U, side × V) seragam di dalam persegi. Menggunakan kembali satu kali pengambilan acak akan membuat koordinat berkorelasi sempurna dan menempatkan setiap titik pada garis diagonal.

2. Mempertahankan invarian pemindaian linier

Pada indeks i, currentStart adalah awal dari deret meningkat ketat terpanjang yang berakhir di i; bestStart dan bestEnd mendeskripsikan deret terbaik pada prefiks tersebut. Jika a[i] > a[i-1], perpanjang deret tersebut. Jika tidak, setel currentStart = i. Perbarui hanya pada panjang yang benar-benar lebih besar, yang menjaga deret paling awal di antara hasil seri.

3. Implementasi referensi

from typing import Callable


def sample_square(side: float, rand01: Callable[[], float]) -> tuple[float, float]:
    if side < 0:
        raise ValueError("side must be non-negative")
    u, v = rand01(), rand01()
    if not (0 <= u < 1 and 0 <= v < 1):
        raise ValueError("rand01 must return values in [0, 1)")
    return side * u, side * v


def longest_increasing_run(values: list[int]) -> tuple[int, int] | None:
    if not values:
        return None
    current_start = best_start = best_end = 0
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]:
            current_start = i
        current_length = i - current_start + 1
        best_length = best_end - best_start + 1
        if current_length > best_length:
            best_start, best_end = current_start, i
    return best_start, best_end

4. Kompleksitas dan pengujian

Pengambilan sampel melakukan dua panggilan sumber acak, sehingga waktu dan ruang ekstra adalah O(1). Pemindaian mengunjungi setiap elemen satu kali, membutuhkan waktu O(n) dan ruang ekstra O(1); mematerialisasi nilai yang dikembalikan akan membutuhkan biaya tambahan O(k). Gunakan urutan rand01 yang tetap untuk menguji pemetaan koordinat, [1, 2, 2, 3] untuk menguji ketatnya peningkatan, dan [5, 4, 3] untuk menguji jawaban elemen tunggal.

Contoh jawaban

“Saya memodelkan kedua koordinat sebagai variabel seragam independen: panggil rand01 dua kali dan skalakan dengan panjang sisi. Hal ini membuat probabilitas persegi panjang kecil mana pun sama dengan luasnya. Saya menemukan deret yang meningkat dengan satu pointer awal dan indeks terbaik dalam pemindaian linier, mereset pada kondisi tidak meningkat dan memperbarui hanya untuk deret yang benar-benar lebih panjang, sehingga hasil seri memilih segmen paling awal. Pengambilan sampel adalah O(1), pemindaian adalah O(n), dan keduanya menggunakan ruang ekstra O(1). Saya akan memverifikasi kontrak sumber acak, sisi negatif, nilai yang sama, dan array kosong.”

Kesalahan umum

• Menggunakan kembali satu pengambilan acak → koordinat berkorelasi dan terletak pada garis diagonal → ambil secara independen dua kali.
• Mengasumsikan rentang rand01 yang arbitrer → koordinat dapat keluar dari persegi → nyatakan dan validasi kontrak [0,1).
• Mengurutkan atau menggunakan pemrograman dinamis untuk deret kontigu → urutan hilang atau ruang bertambah → pertahankan satu status pemindaian.
• Menggunakan >= untuk peningkatan → nilai yang sama digabungkan secara salah → wajibkan >.
• Menimpa pada panjang terbaik yang sama → perilaku pemecah seri menjadi tidak disengaja → perbarui hanya pada panjang yang benar-benar lebih besar.
• Memindai array secara rekursif → kedalaman stack bertambah seiring ukuran input → gunakan iterasi.

Tindak lanjut dan ekstensi

Bagaimana cara mengambil sampel persegi panjang atau persegi yang ditranslasikan?

Gunakan x = xmin + (xmax-xmin)U dan y = ymin + (ymax-ymin)V untuk persegi panjang. Translasi hanya menambahkan offset ke kedua koordinat dan tetap mempertahankan independensi.

Bagaimana Anda mendiagnosis keseragaman?

Bagi persegi menjadi sel-sel dengan luas yang sama, ambil banyak sampel, dan bandingkan jumlah hitungan tiap sel. Ini adalah diagnostik, bukan bukti mutlak; seed yang tetap berguna untuk regresi tetapi tidak menjamin keseragaman visual.

Bagaimana jika setiap deret terpanjang harus dikembalikan?

Simpan panjang terbaik saat ini dan sebuah daftar. Kosongkan daftar saat menemukan deret yang lebih panjang dan tambahkan saat menemukan deret dengan panjang yang sama; ruang tambahannya adalah O(r), di mana r adalah jumlah deret yang seri.

Bagaimana jika array tiba sebagai aliran data (stream)?

Simpan hanya nilai sebelumnya, awal saat ini, indeks terbaik, dan posisi saat ini. Keluarkan interval terbaik di akhir stream, dengan memori yang independen dari panjang total input.