Wawancara Koding: Menggunakan Quickselect untuk Menemukan Elemen Terbesar ke-K dengan Duplikat

Pertanyaan dan cakupan

Diberikan sebuah array bilangan bulat yang belum terurut nums dan 1 ≤ k ≤ nums.length, kembalikan elemen ke-k dalam urutan tidak naik (non-increasing). Elemen duplikat menempati posisi terpisah: nilai terbesar kedua dalam [5, 5, 4] adalah 5, bukan nilai unik (distinct) kedua. Waktu rata-rata yang ditargetkan adalah O(n) dengan ruang ekstra O(1) ketika memodifikasi array diizinkan; nyatakan asumsi tersebut sebelum mulai menulis kode.

Apa yang diuji oleh pewawancara

Jawaban yang kuat memetakan "terbesar ke-k" ke indeks menaik target = n-k, lalu menjelaskan bahwa partisi hanya perlu menetapkan batas di sekitar pivot; sisi lainnya tidak perlu diurutkan sama sekali. Jawaban tersebut juga menangani duplikat, k=1, k=n, input yang sudah terurut, serta perbedaan antara kompleksitas rata-rata teracak (randomized) dan jaminan kasus terburuk.

Klarifikasi sebelum menulis kode

1. Apakah input boleh dimodifikasi? Partisi in-place membutuhkan ruang ekstra O(1); mempertahankan input aslinya membutuhkan salinan O(n).
2. Apakah ini posisi ke-k atau nilai unik ke-k? Perhitungan posisi adalah pernyataan yang umum; pemilihan nilai unik memerlukan penanganan duplikat yang berbeda.
3. Apakah data masuk sebagai stream? Quickselect ditujukan untuk satu array yang sudah terwujud (materialized); min-heap berukuran k memberikan pemrosesan O(n log k) untuk sebuah stream.
4. Apakah batasan kasus terburuk yang deterministik diwajibkan? Quickselect teracak rata-rata berkinerja O(n); median-of-medians atau jaminan bawaan library diperlukan untuk klaim kasus terburuk yang ketat.

Solusi yang disarankan dan derivasi

Gunakan partisi tiga arah (three-way partitioning) ke dalam nilai-nilai yang lebih kecil dari, sama dengan, dan lebih besar dari pivot. Untuk indeks menaik yang telah dikonversi target, lanjutkan dengan interval kiri ketika target berada di sebelah kiri lt, interval kanan ketika berada di sebelah kanan gt, dan kembalikan pivot ketika berada di [lt, gt]. Rentang nilai yang sama membuat input yang seluruh isinya bernilai sama selesai dalam satu kali pemindaian, alih-alih berulang kali membuang satu per satu elemen.

import random

def kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k out of range")
    target = len(nums) - k
    left, right = 0, len(nums) - 1
    while left <= right:
        pivot = nums[random.randint(left, right)]
        lt, i, gt = left, left, right
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1
        if target < lt:
            right = lt - 1
        elif target > gt:
            left = gt + 1
        else:
            return pivot
    raise RuntimeError("unreachable")

Setiap iterasi memindai interval saat ini sebanyak satu kali. Jika pivot menyusutkan interval sebesar fraksi konstan, T(n)=T(cn)+O(n) menghasilkan rata-rata O(n); berulang kali memilih elemen ekstrem tetap menghasilkan O(n²) pada kasus terburuk. Bentuk iteratif menghindari kedalaman rekursi dan menggunakan ruang ekstra O(1).

Alternatif dan pertimbangan

Pengurutan penuh adalah yang paling mudah diverifikasi, memerlukan biaya O(n log n), dan masuk akal jika array berukuran kecil atau urutan lengkap diperlukan nantinya. Min-heap berukuran k mempertahankan input asli dan membutuhkan waktu O(n log k) serta ruang O(k), yang cocok untuk stream atau ketika k jauh lebih kecil daripada n. std::nth_element pada C++ mengekspos semantik partisi yang sama dengan kompleksitas rata-rata linear; fungsi ini tidak mengurutkan sisi mana pun dari posisi yang dipilih.

Modus kegagalan, batas, dan contoh kontra

• Menulis target = k-1 akan menemukan nilai terkecil ke-k, yang membalikkan urutan yang diminta.
• Partisi dua arah yang hanya membuang satu item bernilai sama dapat memakan waktu O(n²) pada [7, 7, 7, ...]; partisi tiga arah langsung menghabiskan rentang nilai yang sama sekaligus.
• Selalu memilih elemen terakhir dapat mengalami penurunan performa pada input yang terurut dan terurut terbalik. Pengacakan menurunkan probabilitas terjadinya hal ini, bukan batasan kasus terburuk asimtotiknya.
• "Nilai unik terbesar ke-k" tidak dapat menggunakan kembali kondisi berhenti tanpa menghitung atau menghapus rentang nilai yang sama.
• Tolak array kosong, k=0, atau k>n pada batas awal, alih-alih membiarkan kesalahan indeks menutupi pertanyaan yang tidak valid.

Uji dan daftar periksa verifikasi

Bandingkan kasus-kasus teracak dengan sorted(nums)[-k]; sertakan nilai yang semuanya sama, bilangan negatif dan duplikat, k=1, k=n, input terurut, dan input terurut terbalik. Ketika mutasi diizinkan, pastikan untuk memeriksa hasil nilai yang dicari daripada urutan array secara penuh. Kunci seed acak untuk reproduktibilitas dan catat jumlah perbandingan seiring bertambahnya n; satu eksekusi yang beruntung bukanlah bukti kompleksitas.

Pertanyaan lanjutan

Bagaimana kasus terburuk dapat dijamin linear?

Pilih pivot median-of-medians sehingga setiap putaran membuang fraksi yang tetap, menghasilkan waktu kasus terburuk O(n). Konstanta miliknya lebih tinggi, sehingga kode produksi umumnya memilih pemilihan teracak (randomized selection) atau implementasi library standar.

Bagaimana cara mengubahnya untuk mencari yang terkecil ke-k?

Gunakan target = k-1 sambil tetap mempertahankan partisi menaik. Mempertahankan formulasi terbesar sebagai target=n-k sering kali lebih jelas daripada membalikkan array.

Bagaimana cara mendukung operasi penyisipan (insert) dan banyak kueri peringkat?

Quickselect satu kali jalan (one-shot) akan memindai ulang pada setiap kueri. Untuk satu k yang bernilai tetap, pertahankan sebuah min-heap berukuran k; untuk kueri peringkat yang arbitrer, pertimbangkan pohon seimbang yang ditambah dengan informasi ukuran subtree (augmented balanced tree) dan pilih berdasarkan rasio pembaruan terhadap kueri.