Wawancara Koding: Menemukan Elemen Terbesar ke-K dalam Sebuah Array

Prompt dan Konteks yang Berlaku

Diberikan sebuah array integer nums dan sebuah integer k, kembalikan elemen terbesar ke-k dalam urutan terurut, bukan nilai unik (distinct) ke-k. Asumsikan 1 <= k <= nums.length <= 100,000 dan -10,000 <= nums[i] <= 10,000.

Sebagai contoh, nums = [3, 2, 1, 5, 6, 4] dan k = 2 mengembalikan 5. Untuk nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] dan k = 4, jawabannya adalah 4: nilai duplikat menempati peringkat terpisah.

Ini adalah masalah order-statistics yang representatif dalam wawancara koding. Pengurutan penuh (full sort), min-heap berukuran k, dan quickselect semuanya valid di bawah batasan yang berbeda. Jawaban utama di bawah ini menggunakan randomized three-way quickselect karena input berupa array yang dapat dimutasi di dalam memori (mutable) dan hanya satu peringkat yang dibutuhkan. Solusi ini memutasi nums; salin array terlebih dahulu jika pemanggil mewajibkan preservasi input.

Apa yang Dievaluasi Pewawancara

Sinyal pertama adalah ketepatan kontrak. “Terbesar ke-k” berarti posisi k dalam urutan terurut menurun (descending), termasuk duplikat. Ini tidak berarti nilai unik ke-k, nilai k terbesar, atau indeks k dalam array berbasis nol (zero-based). Dalam urutan menaik (ascending), elemen yang diminta memiliki indeks berbasis nol n - k.

Sinyal kedua adalah apakah kandidat menurunkan alternatif solusi alih-alih sekadar menghafal quickselect. Pengurutan adalah baseline paling aman pada O(n log n). Min-heap berukuran k membutuhkan waktu O(n log k) dan ruang O(k) serta dapat bekerja untuk input streaming. Quickselect membuang partisi yang tidak mungkin memuat target dan memiliki ekspektasi waktu O(n), namun pivoting acak tidak menghilangkan kasus terburuk O(n^2).

Sinyal ketiga adalah pernyataan invarian partisi. Kode yang sekadar “terlihat seperti quicksort” tidaklah cukup. Kandidat harus dapat menjelaskan apa yang diketahui tentang elemen-elemen sebelum lt, antara lt dan i, antara i dan gt, dan setelah gt, lalu menjelaskan mengapa interval pencarian berikutnya masih memuat peringkat target.

Terakhir, pewawancara mencari penanganan duplikat, penjelasan mutasi, perilaku terhadap input tidak valid, kontrol iteratif untuk menghindari risiko kedalaman rekursi, dan pengujian yang membandingkan hasilnya dengan oracle sederhana. Algoritma yang dioptimalkan tanpa batasan pembuktian atau pengujian adversarial dianggap tidak lengkap.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Apakah elemen terbesar ke-k menghitung duplikat? Jawaban ini mengikuti posisi terurut, sehingga [5, 5, 4] dengan k = 2 mengembalikan 5. Persyaratan peringkat unik (distinct) akan memerlukan deduplikasi atau seleksi berbasis frekuensi.
• Apakah k dijamin valid, dan bisakah array-nya kosong? Kontrak wawancara yang dinyatakan menjamin 1 <= k <= n. Implementasi tetap melempar ValueError di luar rentang tersebut agar perilaku mandirinya eksplisit.
• Bolehkah fungsi memutasi input? Partisi in-place memberikan ruang bantu O(1). Jika mutasi dilarang, salin terlebih dahulu dan terima ruang tambahan O(n).
• Apakah input tersedia sepenuhnya atau berupa streaming? Quickselect membutuhkan akses acak (random access) dan mutasi. Untuk stream tanpa batas, gunakan min-heap berukuran k sebagai gantinya.
• Apakah kita membutuhkan satu kueri atau banyak kueri peringkat pada data yang sama? Quickselect menarik untuk satu peringkat. Mengurutkan sekali bisa lebih baik jika banyak kueri berikutnya menjustifikasi beban kerja awal O(n log n).
• Apakah rentang nilai benar-benar kecil dan tetap? Rentang yang dinyatakan hanya memiliki 20.001 kemungkinan nilai integer, sehingga counting adalah alternatif yang valid. Metode ini memakan waktu O(n + R) dan ruang O(R) untuk lebar rentang R, tetapi tidak boleh disajikan sebagai solusi umum jika nilainya tidak terbatas.
• Haruskah waktu kasus terburuk dibatasi? Randomized quickselect memberikan ekspektasi waktu linier, bukan waktu linier deterministik pada kasus terburuk. Jika jaminan kasus terburuk yang ketat diperlukan, diskusikan median-of-medians atau pilih heap dengan waktu O(n log k) yang dapat diprediksi.

Kerangka Jawaban 30 Detik

“Elemen terbesar ke-k adalah item pada indeks menaik n - k, dengan duplikat tetap dihitung. Pengurutan memberikan baseline O(n log n) yang sederhana, dan min-heap berukuran k memberikan waktu O(n log k) untuk input streaming atau non-mutasi. Karena masalah ini menanyakan satu peringkat dalam array in-memory yang dapat dimutasi, saya akan menggunakan randomized quickselect iteratif. Saya mempartisi interval aktif menjadi nilai-nilai yang lebih kecil dari, sama dengan, dan lebih besar dari pivot acak. Jika n - k berada di rentang yang sama dengan pivot, pivot tersebut adalah jawabannya; jika tidak, saya hanya mempertahankan sisi yang memuat indeks tersebut. Partisi three-way menghindari pemrosesan berulang pada nilai-nilai yang sama. Ekspektasi waktunya adalah O(n), kasus terburuk O(n^2), dan ruang bantunya adalah O(1). Saya akan memverifikasinya terhadap pengurutan pada array acak ditambah kasus semua-elemen-sama, terurut, terbalik, banyak duplikat, dan batas k.”

Jawaban Mendalam Langkah demi Langkah

Mulailah dengan sebuah oracle. Mengurutkan secara menaik dan mengembalikan sorted(nums)[len(nums) - k] mudah dijelaskan dan sulit untuk salah. Ini menetapkan konversi peringkat dan menyediakan hasil referensi untuk pengujian. Biayanya adalah waktu O(n log n) dan ruang O(n) jika mempertahankan input asli dengan salinan.

Bounded heap mengoptimalkan kerja ketika k kecil atau data datang secara inkremental. Masukkan setiap nilai ke dalam min-heap dan hapus nilai minimum setiap kali ukurannya melebihi k. Setelah semua nilai diproses, akarnya adalah yang terkecil di antara k elemen terbesar, yang merupakan elemen terbesar ke-k. Heap menyimpan k nilai, sehingga biayanya adalah waktu O(n log k) dan ruang O(k). Jika k mendekati n dan seluruh array sudah tersedia, keunggulan ini berkurang.

Quickselect memanfaatkan fakta bahwa hanya satu posisi akhir yang penting. Konversikan peringkat menurun menjadi target = len(nums) - k. Di setiap interval aktif [left, right], pilih nilai pivot acak dan lakukan partisi Dutch national flag. Selama pemindaian, pertahankan:

• [left, lt) memuat nilai-nilai yang lebih kecil dari pivot.
• [lt, i) memuat nilai-nilai yang sama dengan pivot.
• [i, gt] belum diklasifikasikan.
• (gt, right] memuat nilai-nilai yang lebih besar dari pivot.

Ketika pemindaian selesai, [lt, gt] adalah rentang lengkap elemen yang sama. Jika target < lt, lanjutkan di sisi nilai yang lebih kecil. Jika target > gt, lanjutkan di sisi nilai yang lebih besar. Jika tidak, target berada di dalam rentang yang sama, sehingga nilai pivot adalah jawabannya. Penanganan ini penting untuk array seperti [7, 7, 7, 7]: partisi two-way dapat berulang kali menghasilkan beban kerja yang hampir tidak berkurang, sementara versi three-way selesai setelah satu kali pemindaian.

import random


def find_kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k must be between 1 and len(nums)")

    target = len(nums) - k
    left = 0
    right = len(nums) - 1

    while left <= right:
        pivot = nums[random.randrange(left, right + 1)]
        lt = left
        i = left
        gt = 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 for a valid k")

Inkrementasi i sengaja dibuat asimetris. Setelah menukar nilai yang lebih besar dari pivot dengan nums[gt], nilai baru di i belum diklasifikasikan, sehingga i tetap di posisinya. Setelah memindahkan nilai yang lebih kecil ke kiri, kedua posisi yang ditukar memiliki klasifikasi yang sudah diketahui, sehingga baik lt maupun i maju.

Kebenaran algoritma mengikuti invarian dan eliminasi peringkat. Partisi mempertahankan setiap elemen input dan berakhir dengan semua nilai yang lebih kecil sebelum rentang sama dan semua nilai yang lebih besar setelahnya. Oleh karena itu, setiap indeks di [lt, gt] memiliki nilai pivot dalam urutan terurut. Jika target berada di luar rentang tersebut, sisi yang dibuang dan rentang yang sama tidak memuat elemen yang dapat menempati indeks target; interval yang dipertahankan masih memuatnya. Setiap iterasi mengembalikan hasil atau secara tegas memperpendek interval, sehingga target yang valid pada akhirnya akan dikembalikan.

Setiap partisi memindai interval saat ini sekali. Dengan pivot acak, ekspektasi total kerja atas interval yang dipertahankan secara berturut-turut adalah O(n). Urutan pivot yang konsisten ekstrem dapat menyisakan interval berukuran n - 1, n - 2, dan seterusnya, menghasilkan waktu kasus terburuk O(n^2). Implementasinya bersifat iteratif dan mempartisi secara in-place, sehingga ruang bantunya adalah O(1). State pembangkit bilangan acak dan array input itu sendiri tidak dihitung sebagai penyimpanan bantu.

Ujilah dengan oracle pengurutan sederhana daripada hanya contoh-contoh statis:

def oracle(nums: list[int], k: int) -> int:
    return sorted(nums)[len(nums) - k]


cases = [
    ([3, 2, 1, 5, 6, 4], 2),
    ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4),
    ([1], 1),
    ([7, 7, 7, 7], 3),
    ([-5, -1, -3, -1], 2),
    (list(range(1000)), 1),
    (list(range(1000)), 1000),
]

for values, rank in cases:
    assert find_kth_largest(values.copy(), rank) == oracle(values, rank)

Tambahkan array yang digenerasi dengan banyak nilai duplikat dan bandingkan setiap k yang valid dengan oracle. Pastikan juga bahwa k = 0, k > n, dan array kosong melempar error yang terdokumentasi. Memberikan seed pada generator acak membuat uji properti yang gagal dapat direproduksi; menjalankan beberapa seed akan menguji jalur partisi yang berbeda.

Contoh Jawaban Berkualitas Tinggi

“Saya akan memperlakukan duplikat sebagai posisi terurut yang terpisah dan mengasumsikan k valid. Jika array diurutkan secara menaik, jawabannya akan berada pada indeks n - k. Baseline saya adalah mengurutkan dan mengambil indeksnya, yaitu O(n log n). Min-heap berukuran k membutuhkan O(n log k) dan akan menjadi pilihan saya untuk data streaming.

Di sini kita memiliki satu kueri dan boleh memutasi array, jadi saya akan menggunakan randomized quickselect. Di dalam rentang aktif, saya memilih pivot acak dan membagi nilai menjadi lebih kecil dari, sama dengan, dan lebih besar dari pivot. Pembagian three-way penting karena duplikat harus menempati beberapa peringkat dan input yang semua nilainya sama harus selesai dalam satu partisi. Setelah partisi, jika n - k berada di dalam rentang sama, saya mengembalikan pivot. Jika tidak, saya membuang sisi yang tidak mungkin memuat indeks tersebut dan mengulangi secara iteratif.

Invariannya adalah semua elemen sebelum lt lebih kecil, semua elemen dari lt hingga i sama, semua elemen setelah gt lebih besar, dan bagian tengah yang belum diketahui masih belum diklasifikasikan. Ini membuktikan rentang sama yang final memiliki interval peringkat terurut yang benar. Oleh karena itu, sisi yang dipertahankan masih memuat jawabannya.

Ekspektasi waktu eksekusinya adalah O(n) karena pivot acak biasanya membuang sebagian besar elemen, meskipun kasus terburuknya tetap O(n^2). Loop dan partisi in-place menggunakan ruang bantu O(1). Saya akan menyampaikan bahwa fungsi ini memutasi inputnya, membandingkannya dengan oracle pengurutan pada array yang digenerasi, dan menyertakan kasus duplikat, data bernilai sama semua, array terurut dan terbalik, nilai negatif, k = 1, serta k = n.”

Kesalahan Umum

• Mengembalikan nilai unik (distinct) ke-k → duplikat adalah posisi terpisah dalam kontrak → Konversikan langsung ke indeks menaik n - k tanpa deduplikasi.
• Menggunakan indeks k atau k - 1 dalam urutan menaik → konversi arahnya salah → Periksa bahwa k = 1 dipetakan ke n - 1 dan k = n dipetakan ke 0.
• Mengklaim solusi min-heap adalah O(n log n) → heap tidak pernah melebihi k elemen → Nyatakan waktu O(n log k) dan ruang O(k).
• Melakukan rekursi ke kedua partisi → itu melakukan kerja quicksort dan mengabaikan tujuan pencarian peringkat tunggal → Lanjutkan hanya pada interval yang memuat target.
• Selalu memilih pivot pertama atau terakhir → input yang terurut atau dirancang khusus dapat berulang kali membuat interval berukuran n - 1 → Acak pivot dan tetap sampaikan peringatan kasus terburuk.
• Menggunakan partisi two-way tanpa mendiskusikan duplikat → array dengan banyak nilai identik dapat mengalami progres yang buruk → Buat satu rentang sama dan kembalikan nilai saat target berada di dalamnya.
• Menginkrementasi i setelah menukar dengan gt → nilai yang baru masuk belum diklasifikasikan dan bisa terlewat → Biarkan i tetap di tempatnya sampai nilai tersebut diklasifikasikan.
• Mengklaim randomisasi menjamin waktu linier → pivot yang tidak menguntungkan masih bisa terjadi → Katakan ekspektasi O(n), kasus terburuk O(n^2).
• Menyembunyikan mutasi input → pemanggil mungkin bergantung pada urutan asli → Nyatakan kontrak mutasi atau lakukan penyalinan dan perhitungkan ruang O(n).
• Hanya menguji dua contoh → bug off-by-one, duplikat, dan partisi tetap tidak terlihat → Bandingkan terhadap pengurutan pada kasus batas, kasus terstruktur, dan input yang digenerasi.

Pertanyaan Lanjutan dan Cara Menanganinya

Pertanyaan Lanjutan 1: Apa yang berubah jika inputnya adalah stream tanpa batas?

Quickselect tidak lagi cocok karena array akses acak yang lengkap tidak tersedia. Pertahankan sebuah min-heap dengan paling banyak k nilai. Masukkan elemen sampai ukurannya mencapai k; setelah itu ganti akar hanya jika nilai yang lebih besar datang. Akarnya adalah nilai terbesar ke-k yang terlihat sejauh ini. Pembaruan memakan biaya O(log k), kueri memakan biaya O(1), dan memorinya adalah O(k). Jika k itu sendiri berubah secara arbitrer, state ini mungkin tidak cukup dan kontrak memerlukan struktur terurut yang lebih kaya atau penyimpanan data.

Pertanyaan Lanjutan 2: Bagaimana jika fungsinya harus mempertahankan input?

Adaptasi paling sederhana adalah working = nums.copy() dan quickselect pada working, mengubah ruang bantu menjadi O(n). Heap berukuran k mempertahankan input dengan ruang O(k) dan mungkin lebih baik jika k kecil. Pengurutan penuh atas salinan lebih sederhana jika n berukuran sedang atau banyak kueri peringkat akan menggunakan kembali hasil terurut tersebut.

Pertanyaan Lanjutan 3: Bisakah Anda menjamin waktu kasus terburuk yang linier?

Median-of-medians memilih pivot yang membuang fraksi konstan pada kasus terburuk, memberikan seleksi deterministik O(n). Implementasi dan konstantanya lebih besar, sehingga randomized quickselect sering kali menjadi pilihan praktis dalam wawancara kecuali persyaratannya secara eksplisit menuntut batasan kasus terburuk. Bounded heap menawarkan alternatif yang lebih sederhana dan dapat diprediksi pada O(n log k).

Pertanyaan Lanjutan 4: Bagaimana Anda memanfaatkan rentang integer yang kecil?

Buat array frekuensi untuk nilai dari -10,000 hingga 10,000, pindai nums, lalu telusuri frekuensi dari tinggi ke rendah sambil mengurangkan hitungan dari k. Bucket pertama yang memuat sisa peringkat adalah jawabannya. Dengan lebar rentang R = 20,001, ini memakan waktu O(n + R) dan ruang O(R). Pendekatan ini deterministik dan menangani duplikat secara alami, tetapi menjadi tidak cocok jika rentangnya besar atau tidak terbatas.

Pertanyaan Lanjutan 5: Bagaimana jika pewawancara meminta k elemen terbesar, dalam keadaan terurut?

Satu order statistic bukan lagi keseluruhan output. Heap berukuran k yang diikuti dengan pengurutan heap memakan waktu O(n log k + k log k) dan ruang O(k). Quickselect dapat mempartisi di sekitar peringkat n - k, setelah itu mengurutkan k nilai terpilih memakan ekspektasi waktu O(n + k log k). Pilihlah berdasarkan mutasi, memori, persyaratan kasus terburuk, dan apakah urutan output diwajibkan.

Pertanyaan Lanjutan 6: Bagaimana cara membuat kegagalan uji acak dapat direproduksi?

Terima injeksi random-number generator atau beri seed pada generator sebelum setiap pengujian. Catat seed, input, dan k saat terjadi kegagalan. Jalankan input yang sama pada beberapa seed tetap, dan bandingkan setiap jawaban dengan oracle pengurutan. Ini memisahkan kesalahan algoritma dari satu jalur pivot tertentu sambil mempertahankan pengulangan (repeatability) dalam integrasi berkelanjutan (continuous integration).