Temuduga pengekodan: Persampelan seragam sebuah segi empat sama dan mengimbas subarray menaik terpanjang

Gesaan dan skop

Rekod temuduga awam membahagikan latihan ini kepada dua tugasan pendek: panggil fungsi rand01() yang mengembalikan nilai seragam antara 0 dan 1 untuk mensampel titik di dalam segi empat sama dengan sisi side, kemudian cari segmen berturutan meningkat secara ketat yang terpanjang bagi sesuatu tatasusunan. Artikel ini meletakkan sudut kiri bawah segi empat sama pada (0, 0), menganggap sumber rawak sebagai [0, 1), dan mengembalikan hasil kosong untuk tatasusunan kosong.

Perkara yang diuji oleh penemuduga

Latihan ini menggabungkan pemodelan kebarangkalian, pemetaan julat, satu laluan tak varian (one-pass invariant), dan semantik hasil yang tepat. Nota kuliah Cornell menerangkan bahawa dua pemboleh ubah seragam tak bersandar pada [0,1] membentuk titik yang seragam dari segi luas pada unit segi empat sama; bahan kebarangkalian segi empat sama MIT memberikan tafsiran luas yang sama. Imbasan ini menguji sama ada calon mengekalkan sifat berturutan, menganggap kesaksamaan nilai sebagai pemisah, dan memilih pemecah seri (tie-break) yang deterministik.

Soalan penjelasan untuk ditanya

1. Adakah rand01() tertutup atau separa terbuka? Jawapan ini mengandaikan [0, 1).
2. Adakah segi empat sama itu ditranslasikan? Jawapan ini bermula pada asalan; translasi hanya menambah ofset.
3. Adakah peningkatan itu ketat? Jawapan ini memerlukan a[i] > a[i-1].
4. Jujukan terpanjang manakah yang menang jika berlaku seri? Jawapan ini mengembalikan permulaan yang paling awal.
5. Adakah penyahduplikasian atau kerawakan kriptografi diperlukan? Latihan asas tidak memerlukan mana-mana daripadanya.

Jawapan 30 saat

“Saya memanggil rand01() secara tak bersandar sebanyak dua kali dan mendarabkan nilai tersebut dengan panjang sisi. Koordinat seragam yang tak bersandar menjadikan kebarangkalian setiap segi empat tepat kecil sama dengan luasnya. Untuk tatasusunan, saya menyimpan permulaan jujukan meningkat ketat semasa dan indeks mula/tamat terbaik. Keadaan tidak meningkat menetapkan semula permulaan semasa; saya mengemas kini jawapan hanya apabila jujukan semasa adalah lebih panjang secara ketat. Persampelan adalah O(1), pengimbasan adalah O(n), dan ruang tambahan adalah O(1). Saya akan menguji sempadan, kesaksamaan nilai, input kosong, tatasusunan monotonik dan keadaan seri.”

Penyelesaian langkah demi langkah

1. Terbitkan sampel seragam

Biar U dan V menjadi pemboleh ubah seragam tak bersandar pada [0,1). Bagi mana-mana segi empat tepat sejajar paksi [a,b) × [c,d), kebarangkalian untuk berada di dalamnya ialah (b-a)(d-c), tepat mengikut luasnya. Oleh itu (side × U, side × V) adalah seragam di dalam segi empat sama. Menggunakan semula satu cabutan akan menyebabkan koordinat berkorelasi sempurna dan meletakkan setiap titik pada pepenjuru.

2. Mengekalkan tak varian imbasan linear

Pada indeks i, currentStart ialah permulaan jujukan meningkat secara ketat terpanjang yang berakhir pada i; bestStart dan bestEnd menerangkan jujukan terbaik dalam awalan tersebut. Jika a[i] > a[i-1], lanjutkan jujukan. Jika tidak, tetapkan currentStart = i. Kemas kini hanya pada panjang yang lebih besar secara ketat, yang mengekalkan jujukan paling awal antara keadaan seri.

3. Pelaksanaan rujukan

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. Kerumitan dan ujian

Persampelan membuat dua panggilan sumber rawak, jadi masa dan ruang tambahan adalah O(1). Imbasan melawat setiap elemen sekali, mengambil masa O(n) dan ruang tambahan O(1); mematerialisasikan nilai yang dikembalikan akan memerlukan kos tambahan O(k). Gunakan jujukan rand01 yang tetap untuk menguji pemetaan koordinat, [1, 2, 2, 3] untuk menguji ketegasan peningkatan, dan [5, 4, 3] untuk menguji jawapan elemen tunggal.

Contoh jawapan

“Saya memodelkan dua koordinat tersebut sebagai pemboleh ubah seragam tak bersandar: panggil rand01 dua kali dan skalakan dengan panjang sisi. Itu menjadikan kebarangkalian mana-mana segi empat tepat kecil sama dengan luasnya. Saya mencari jujukan menaik dengan satu penunjuk mula dan indeks terbaik dalam imbasan linear, menetapkan semula apabila berlaku bukan peningkatan dan mengemas kini hanya untuk jujukan yang lebih panjang secara ketat, supaya keadaan seri memilih segmen paling awal. Persampelan adalah O(1), pengimbasan adalah O(n), dan kedua-duanya menggunakan ruang tambahan O(1). Saya akan mengesahkan kontrak sumber rawak, sisi negatif, nilai sama, dan tatasusunan kosong.”

Kesilapan lazim

• Menggunakan semula satu cabutan rawak → koordinat berkorelasi dan terletak pada pepenjuru → cabut secara tak bersandar sebanyak dua kali.
• Mengandaikan julat rand01 yang sewenang-wenangnya → koordinat boleh terkeluar dari segi empat sama → nyatakan dan sahkan kontrak [0,1).
• Menyusun atau menggunakan pengaturcaraan dinamik untuk jujukan berturutan → susunan asal hilang atau ruang bertambah → kekalkan satu keadaan imbasan.
• Menggunakan >= untuk peningkatan → nilai yang sama digabungkan secara salah → wajibkan >.
• Menulis ganti pada panjang terbaik yang sama → tingkah laku pemutus seri menjadi tidak disengajakan → kemas kini hanya pada panjang yang lebih besar secara ketat.
• Mengimbas tatasusunan secara rekursif → kedalaman tindanan bertambah mengikut saiz input → gunakan lelaran.

Susulan dan lanjutan

Bagaimanakah anda mensampel segi empat tepat atau segi empat sama yang ditranslasikan?

Gunakan x = xmin + (xmax-xmin)U dan y = ymin + (ymax-ymin)V untuk segi empat tepat. Translasi hanya menambah ofset pada kedua-dua koordinat dan mengekalkan ketakbersandaran.

Bagaimanakah anda mendiagnosis keseragaman?

Bahagikan segi empat sama kepada sel-sel dengan luas yang sama, ambil banyak sampel dan bandingkan kiraan sel. Ini adalah diagnostik, bukan bukti mutlak; benih (seed) tetap berguna untuk regresi tetapi tidak menjamin keseragaman visual.

Bagaimana jika setiap jujukan terpanjang mesti dikembalikan?

Simpan panjang terbaik semasa dan senarai. Kosongkan senarai apabila terdapat jujukan yang lebih panjang dan tambah apabila jujukan sama panjang; ruang tambahan ialah O(r), dengan r ialah bilangan jujukan yang seri.

Bagaimana jika tatasusunan tiba sebagai strim?

Simpan hanya nilai sebelumnya, permulaan semasa, indeks terbaik, dan kedudukan semasa. Pancarkan selang terbaik pada akhir strim, dengan memori yang tidak bergantung pada jumlah panjang input.