Wawancara coding: Bagaimana Anda menggunakan wavelet matrix untuk kueri k-th dalam rentang?

Prompt dan cakupan

Diberikan sebuah array integer statis a, jawab banyak kueri rentang setengah terbuka [l, r): kembalikan nilai terkecil ke-k, frekuensi dari x, dan jumlah elemen dalam [lo, hi). Array tidak pernah berubah dan nilainya bisa berukuran besar. Rancang dan analisis struktur yang lebih cepat daripada mengurutkan setiap rentang.

Sebuah wavelet matrix mempartisi nilai secara stabil berdasarkan bit dari yang paling signifikan hingga yang paling tidak signifikan, menyimpan bitvector dan hitungan prefix-one di setiap level. Struktur ini tidak memerlukan pointer pohon eksplisit; setiap kueri memetakan intervalnya ke level berikutnya. Nyatakan bahwa k berbasis nol (zero-based), tangani kompresi koordinat dan duplikat, serta berikan batasannya.

Apa yang dievaluasi oleh pewawancara

• Menjelaskan mengapa partisi stabil, awal blok nol, dan pemetaan rank mempertahankan urutan.
• Memilih nilai ke-k pada [l, r) dan mengakumulasi bit dengan benar.
• Menangani duplikat, rentang kosong, k di luar rentang, dan nilai bertanda (signed).
• Membedakan jalur untuk hitungan domain nilai, frekuensi titik, dan kueri ke-k.
• Memberikan batas kueri O(B), konstruksi O(nB), dan ruang yang dapat dikompresi.
• Menyadari bahwa struktur statis tidak menyediakan pembaruan yang murah dan mengetahui alternatifnya.

Pertanyaan klarifikasi

1. Apakah r bersifat eksklusif, dan apakah k berbasis nol atau berbasis satu?
2. Apakah array benar-benar immutable? Jika tidak, berapa tingkat pembaruan dan kuerinya?
3. Apakah nilainya bertanda, dan berapa lebar bit maksimumnya? Bisakah kita melakukan kompresi koordinat padanya?
4. Berapa memori yang tersedia untuk rank, dan bisakah bitvector diblok atau dikompresi?
5. Apakah kita hanya membutuhkan ke-k, atau juga frekuensi, predecessor, atau penjumlahan rentang (range sum)? Operasi-operasi ini memengaruhi pilihan.

Jawaban 30 detik

Saya akan melakukan kompresi koordinat pada nilai-nilai ke kode non-negatif dengan lebar bit B. Selama konstruksi, partisi urutan saat ini secara stabil dari bit tertinggi ke bawah, menyimpan bitvector setiap level dan hitungan prefix rank-one. Untuk ke-k, simpan [l,r), hitung nol pada level tersebut, dan petakan ke blok nol atau kurangi nol lalu petakan ke blok satu sambil menyetel bit jawaban tersebut. Frekuensi menggunakan dua penelusuran rank; hitungan domain nilai adalah selisih dari dua panggilan countLess. Biaya kueri adalah O(B) dan biaya konstruksi adalah O(nB).

Solusi langkah demi langkah

1. Encode domain nilai

Untuk integer bertanda arbitrer, urutkan nilai-nilai unik dan petakan ke 0..m-1, dengan mempertahankan array kode-ke-nilai. Maka B adalah ceil(log2(m)), dengan kasus eksplisit untuk m=1. Jika urutan alami harus dipertahankan secara langsung, balik bit tanda sebelum memperlakukan nilai bertanda sebagai tidak bertanda (unsigned).

2. Bangun satu level yang stabil

Periksa cur pada bit, tambahkan semua nilai bit nol ke next, lalu semua nilai bit satu, dengan mempertahankan urutan di dalam kedua grup. bv[i] mencatat bit pada posisi asli i, dan zeroCount adalah jumlah angka nol. Stabilitas menjaga interval berikutnya tetap terikat pada elemen asli yang sama.

rank1(i) = number of ones in bv[0..i)
zeroCount = n - rank1(n)
for interval [l, r):
  zero interval = [l - rank1(l), r - rank1(r))
  one interval  = [zeroCount + rank1(l), zeroCount + rank1(r))

3. Kueri nilai rentang ke-k

Di setiap level hitung zeros = (r-l) - (rank1(r)-rank1(l)). Ketika k lebih kecil dari nol, petakan ke interval nol. Jika tidak, kurangi nol, petakan ke interval satu, dan setel bit jawaban saat ini. Setelah B level, dekode kode kembali ke nilai aslinya.

4. Kueri frekuensi satu nilai

Perlakukan setiap bit target sebagai cabang tetap dan petakan [l,r) dengan cara yang sama. Target nol mengikuti interval nol; target satu mengikuti interval satu menggunakan zeroCount. Setelah B level, panjang interval adalah frekuensinya. Target yang tidak ada dalam kamus terkompresi mengembalikan nol.

5. Kueri rentang nilai

Definisikan countLess(x, l, r) sebagai jumlah nilai di bawah x dalam [l,r). Pada level di mana x memiliki bit satu, setiap cabang nol bernilai lebih kecil, jadi tambahkan zeros dan lanjutkan ke cabang satu. Untuk bit nol, lanjutkan hanya ke cabang nol. Hitungan dalam [lo, hi) adalah countLess(hi)-countLess(lo).

6. Batas dan verifikasi

Definisikan perilaku untuk rentang kosong atau ketika batas kiri tidak lebih kecil dari batas kanan; jangan pernah mengindeks array rank di luar batasnya. Syaratkan k berada dalam panjang rentang saat ini. Uji kasus semua elemen sama, terurut, duplikat yang diselingi, nilai negatif, rentang satu elemen, lebar bit maksimum, dan nilai yang tidak ada dalam kamus, bandingkan setiap hasil dengan brute-force sort atau count.

7. Kompleksitas dan pertimbangan kompromi (trade-offs)

Dengan hitungan prefix biasa, setiap level menyimpan O(n) penghitung, sehingga ruang dan konstruksi bernilai O(nB) dan setiap operasi bernilai O(B). Bitvector terkompresi yang mendukung rank mengurangi ruang dan konstanta. Struktur ini cocok untuk beban kerja immutable yang padat kueri. Untuk pembaruan, pertimbangkan pembangunan ulang berbasis blok, bitvector dinamis, segment tree dari ordered set, atau pemrosesan offline dan evaluasi ulang biaya memori dan pembaruan.

Contoh jawaban yang kuat

Saya akan menyatakan bahwa rentang bersifat setengah terbuka, k berbasis nol, dan array bersifat immutable. Saya akan melakukan kompresi koordinat pada nilai-nilai dan menggunakan B bit. Konstruksi mempartisi secara stabil dari bit tertinggi ke bawah, mempertahankan hitungan prefix rank-one dan panjang blok nol di setiap level.

Untuk ke-k, setiap level menghitung angka nol dalam interval saat ini. Jika k termasuk dalam nol, petakan dengan l-rank1(l) dan r-rank1(r); jika tidak, kurangi nol, petakan dengan zeroCount+rank1(l) dan zeroCount+rank1(r), dan setel bit jawaban. Frekuensi mengikuti jalur nilai tetap, sedangkan hitungan domain nilai adalah dua panggilan countLess. Konstruksi bernilai O(nB) dan setiap kueri bernilai O(B), dengan error eksplisit atau nol untuk rentang tidak valid dan kode yang tidak ada.

Kesalahan umum

• Mencampur rentang tertutup dan setengah terbuka → rank bergeser satu → gunakan [l,r) secara konsisten dan tulis pemetaannya.
• Lupa partisi stabil → interval berikutnya tidak lagi mengidentifikasi elemen yang sama → pertahankan urutan di kedua blok.
• Memasuki blok satu tanpa mengurangkan nol → nilai ke-k menjadi terlalu besar → kurangi sebelum memetakan.
• Membandingkan nilai bertanda sebagai bit tidak bertanda → bilangan negatif salah urutan → kompres atau balik bit tanda.
• Mengasumsikan pembaruan itu murah → pembaruan membatalkan permutasi level → nyatakan prasyarat statis dan alternatifnya.
• Hanya menguji nilai-nilai unik → bug pada duplikat dan batasan tetap tersembunyi → uji kasus nilai sama, diselingi, kosong, dan tidak valid.

Pertanyaan lanjutan dan tanggapan

Mengapa tidak mengurutkan setiap rentang?

Mengurutkan satu rentang memerlukan biaya O((r-l) log(r-l)) dan mengulangi pekerjaan di setiap kueri. Matriks melakukan pra-komputasi informasi percabangan, sehingga kueri hanya mengunjungi B level dan cocok untuk beban kerja statis dengan kueri tinggi.

Mengapa rank1 memetakan interval?

Prefix rank memberi tahu berapa banyak angka satu yang muncul sebelum setiap batas, yang memberikan posisi relatif interval di blok nol dan satu. Partisi stabil memastikan posisi-posisi tersebut mewakili elemen yang sama.

Bagaimana Anda menjawab k-th terbesar?

Ubah menjadi k-th terkecil dengan length - 1 - k, atau prioritaskan cabang satu di setiap level sambil mengurangi hitungannya. Keduanya tetap bernilai O(B).

Bagaimana jika domain nilai jauh lebih besar dari n?

Lakukan kompresi koordinat pada nilai yang teramati dan simpan peta pembalikannya. Untuk nilai kueri yang belum pernah terlihat, lakukan binary search pada batas penyisipannya atau kembalikan frekuensi nol.

Bagaimana jika pembaruan diperlukan?

Wavelet matrix biasa tidak ramah terhadap pembaruan. Gunakan pembangunan ulang berbasis blok, bitvector dinamis, segment tree dari struktur terurut, atau pemrosesan offline berdasarkan rasio pembaruan/kueri, target latensi, dan memori.