Mendesain Struktur Data untuk Item Frekuensi Top-K Dinamis

Pertanyaan dan kapan menggunakannya

Aliran ID integer yang tak berujung tiba satu per satu. add(x) mencatat satu kemunculan lagi dari ID x. topK(k) mengembalikan hingga k ID berbeda dengan frekuensi tertinggi saat ini beserta jumlah kemunculannya; ID dengan frekuensi sama (tie) dapat muncul dalam urutan apa pun, dan k dapat berubah di antara setiap kueri. Desain solusi eksak untuk beban kerja read-heavy dan write-heavy serta analisis biaya waktu dan ruangnya. Jika jumlah ID yang berbeda dapat bertambah tanpa batas sementara memori bernilai tetap, berikan desain aproksimasi dan definisikan arti dari nilai kesalahannya (error).

Pertanyaan ini cocok untuk wawancara rekayasa perangkat lunak dan algoritma. Kontrak eksak ini hanya mengizinkan penambahan (inkremen) frekuensi: tidak ada penghapusan, sliding window, atau penggabungan terdistribusi (distributed merge). Misalkan N adalah jumlah pembaruan sejauh ini dan D adalah jumlah ID unik, dengan k << D pada kasus umum. Versi publik dari soal ini secara eksplisit meminta desain yang bergantung pada beban kerja serta ekstensi streaming dengan memori terbatas, sehingga "hash map plus min-heap" hanyalah awal dari jawaban.

Hal yang dievaluasi oleh pewawancara

Pertama, apakah kandidat menetapkan kontrak operasi dan rasio beban kerja? Operasi batch yang hanya meminta hasil satu kali setelah aliran berakhir tidak seharusnya menanggung biaya pemeliharaan yang sama seperti papan peringkat online yang dikueri setelah setiap pembaruan.

Kedua, apakah kompleksitas yang disebutkan sesuai dengan status (state) yang dikelola? Menghitung kemunculan dalam hash map dan membangun min-heap berukuran k pada waktu kueri menghasilkan ekspektasi O(1) untuk add dan O(D log k) untuk topK. Klaim pemeliharaan heap senilai O(log k) per pembaruan juga memerlukan pelacakan posisi heap serta penjelasan kapan suatu item di luar heap masuk ke dalamnya.

Ketiga, dapatkah kandidat membuktikan kebenaran struktur dinamis? Jawaban yang kuat menyatakan tiga invarian: setiap ID tepat berada di dalam satu frequency bucket; frekuensi bucket meningkat secara ketat (strictly increasing) dan tidak ada bucket yang kosong; serta frekuensi bucket suatu ID sama dengan jumlah akumulasi kemunculan sebenarnya. Argumen kompleksitas harus diturunkan dari invarian-invarian tersebut.

Keempat, dapatkah kandidat membedakan top-k eksak, heavy hitters, dan estimasi frekuensi? Space-Saving mempertahankan kunci kandidat dengan batas jumlah di bawah anggaran counter tetap. Count-Min Sketch utamanya memperkirakan frekuensi dari kunci yang diberikan dan tidak menyimpan himpunan ID yang dapat diiterasi (enumerable) secara mandiri. Memperlakukan sketsa saja sebagai daftar top-k menyisakan proses pencarian kandidat (candidate discovery) yang tidak terjelaskan.

Pertanyaan klarifikasi sebelum menjawab

• Apakah k bernilai tetap atau spesifik per kueri? Nilai K yang tetap memungkinkan penggunaan heap terindeks berukuran K. Nilai k yang arbitrer lebih cocok menggunakan struktur yang terurut di seluruh frekuensi.
• Berapa rasio pembaruan terhadap kueri? Sistem yang write-heavy dapat menunda pemrosesan hingga waktu kueri. Kueri yang sering membenarkan perlunya pemeliharaan urutan pada setiap add.
• Haruskah nilai yang sama (tie) memiliki urutan yang deterministik? Kontrak ini mengizinkan urutan apa pun, sehingga hash set di dalam setiap bucket sudah cukup. Mengharuskan ID yang menaik (ascending) memerlukan ordered set dan menghilangkan ekspektasi pembaruan O(1).
• Apakah penghapusan atau jendela waktu (time windows) diperlukan? Dengan operasi inkremen saja, sebuah item berpindah dari frekuensi f ke frekuensi yang bersebelahan f + 1. Penghapusan menambahkan pergerakan sebaliknya; sebuah window juga membutuhkan status kedaluwarsa.
• Apakah D muat di dalam memori? Jawaban eksak untuk distribusi tanpa batas menyimpan jumlah kemunculan setiap ID unik. Memori tetap membutuhkan aproksimasi atau pass kedua yang dapat diputar ulang (replayable).
• Berapa toleransi kesalahan (error) yang dapat diterima? "Hampir benar" tidak dapat diuji. Tentukan batas kesalahan jumlah aditif, himpunan kandidat yang tidak pasti, atau kondisi pemisahan frekuensi yang memvalidasi top-k.
• Bisakah counter meluap (overflow)? Layanan yang berjalan lama membutuhkan counter 64-bit atau lebih besar. Contoh berikut menggunakan number JavaScript dan hanya eksak dalam rentang safe-integer.

Kerangka jawaban 30 detik

"Pertama-tama, saya akan mengklarifikasi apakah k bervariasi, rasio baca-tulis, pengurutan nilai yang sama, dan batas memori. Untuk lalu lintas write-heavy dan jarang kueri, saya akan menggunakan hash map untuk penambahan dengan ekspektasi O(1), kemudian memindai D jumlah kemunculan ke dalam min-heap berukuran k dalam O(D log k) per kueri. Jika kueri dengan k arbitrer sering dilakukan, saya akan memelihara doubly linked list berisi frequency bucket yang terurut menaik ditambah map ID → bucket. Sebuah pembaruan hanya memindahkan satu ID dari bucket f ke bucket tetangganya f + 1, menghasilkan ekspektasi pembaruan O(1); penelusuran mundur untuk mendapatkan k hasil membutuhkan biaya O(min(k, D)), dengan ruang O(D). Jika D tidak muat di memori, saya akan menggunakan counter Space-Saving tetap dengan batas kesalahan dan memvalidasi top-k secara tersertifikasi hanya saat batas-batas tersebut terpisah. Count-Min Sketch tetap memerlukan himpunan kandidat untuk mengiterasi ID."

Solusi langkah demi langkah

Langkah 1: Bandingkan desain eksak berdasarkan beban kerja

"Hash map plus min-heap" bukanlah pemenang universal. Pendekatan ini sengaja menempatkan pemrosesan pengurutan pada jalur kueri, yang memang tepat jika operasi tulis mendominasi. Jika produk menampilkan papan peringkat setelah setiap add, pemindaian D kunci secara berulang akan menjadi bottleneck dan struktur frequency-bucket yang lebih rumit akan sebanding dengan biayanya.

Langkah 2: Tetapkan invarian frequency-bucket

Pelihara doubly linked list berisi bucket-bucket dalam urutan frekuensi menaik. Setiap bucket memiliki himpunan (set) ID dengan frekuensi tersebut, sementara hash map menemukan bucket ID secara langsung. ID baru akan bergabung ke dalam bucket dengan frekuensi 1. ID yang sudah ada berpindah dari bucket f ke bucket f + 1. Karena satu pembaruan tepat menambah satu nilai, bucket baru hanya dapat disisipkan di antara sumber dan penerusnya; tidak diperlukan pencarian list. Hapus bucket sumber segera setelah bucket tersebut menjadi kosong.

Tiga invarian membuktikan kebenaran hasilnya:

1. Setiap ID dalam locations muncul tepat di dalam satu himpunan bucket.
2. Setiap frequency bucket yang tidak kosong sama dengan jumlah kemunculan sebenarnya dari setiap ID yang dikandungnya.
3. Frekuensi meningkat secara ketat dari head ke tail.

Oleh karena itu, penelusuran mundur dari tail tidak mungkin melewatkan ID berfrekuensi lebih tinggi, sementara nilai yang sama dapat dikembalikan dalam urutan apa pun. Setiap bucket yang dikunjungi menghasilkan setidaknya satu hasil, sehingga jumlah bucket yang dikunjungi tidak lebih besar dari ukuran output dan waktu kueri adalah O(min(k, D)).

Langkah 3: Implementasikan kueri k arbitrer eksak

interface Bucket {
  frequency: number;
  values: Set<number>;
  prev: Bucket | null;
  next: Bucket | null;
}

interface TopKEntry {
  value: number;
  count: number;
}

class FrequencyIndex {
  private readonly locations = new Map<number, Bucket>();
  private head: Bucket | null = null;
  private tail: Bucket | null = null;

  add(value: number): void {
    const source = this.locations.get(value);

    if (!source) {
      let target = this.head;
      if (!target || target.frequency !== 1) {
        target = this.insertBefore(this.head, 1);
      }
      target.values.add(value);
      this.locations.set(value, target);
      return;
    }

    let target = source.next;
    if (!target || target.frequency !== source.frequency + 1) {
      target = this.insertAfter(source, source.frequency + 1);
    }

    source.values.delete(value);
    target.values.add(value);
    this.locations.set(value, target);

    if (source.values.size === 0) {
      this.removeBucket(source);
    }
  }

  topK(k: number): TopKEntry[] {
    if (!Number.isInteger(k) || k < 0) {
      throw new RangeError("k must be a non-negative integer");
    }

    const result: TopKEntry[] = [];
    let bucket = this.tail;

    while (bucket && result.length < k) {
      for (const value of bucket.values) {
        result.push({ value, count: bucket.frequency });
        if (result.length === k) break;
      }
      bucket = bucket.prev;
    }

    return result;
  }

  private insertBefore(next: Bucket | null, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev: next?.prev ?? null,
      next,
    };

    if (bucket.prev) bucket.prev.next = bucket;
    else this.head = bucket;

    if (next) next.prev = bucket;
    else this.tail = bucket;

    return bucket;
  }

  private insertAfter(prev: Bucket, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev,
      next: prev.next,
    };

    if (prev.next) prev.next.prev = bucket;
    else this.tail = bucket;

    prev.next = bucket;
    return bucket;
  }

  private removeBucket(bucket: Bucket): void {
    if (bucket.prev) bucket.prev.next = bucket.next;
    else this.head = bucket.next;

    if (bucket.next) bucket.next.prev = bucket.prev;
    else this.tail = bucket.prev;
  }
}

Kompleksitas ini menggunakan asumsi waktu konstan rata-rata (expected constant-time) yang umum untuk Map dan Set, bukan jaminan spesifikasi JavaScript untuk kasus terburuk yang ketat O(1). topK(0) mengembalikan array kosong, k > D mengembalikan semua ID, dan nilai k yang negatif atau bukan bilangan bulat akan melemparkan exception (throws).

Langkah 4: Nyatakan jaminan aproksimasi di bawah memori terbatas

Hash map eksak tumbuh seiring dengan D. Sebaliknya, Space-Saving hanya mempertahankan m counter yang berisi ID, perkiraan jumlah, dan batas kesalahan maksimum; m > k diperlukan untuk membandingkan terhadap batas kandidat k + 1. ID terlacak yang teramati akan menambah counternya. Ketika ID yang tidak terlacak tiba setelah semua counter terisi, ia menggantikan ID dengan estimasi jumlah minimum c_min; estimasi baru menjadi c_min + 1, dengan kesalahan tercatat c_min.

Untuk setiap ID yang dipantau, frekuensi sebenarnya berada dalam [estimate - error, estimate], dan makalah terkait membatasi estimasi berlebih maksimum sebesar N / m. Himpunan top-k dapat disertifikasi ketika batas bawah terkecil di antara k kandidat pertama tidak lebih kecil dari perkiraan batas atas kandidat k + 1. Jika interval-interval tersebut tumpang tindih, kembalikan kandidat perkiraan daripada menampilkan urutan perkiraan sebagai data eksak. Ketika seluruh aliran memiliki D <= m, tidak ada penggantian yang terjadi dan jumlah kemunculan tetap eksak.

Count-Min Sketch menggunakan array counter tetap berukuran width × depth. Dengan width = ceil(e / ε) dan depth = ceil(ln(1 / δ)) pada aliran khusus penambahan, estimasi untuk ID yang diberikan tidak pernah berada di bawah jumlah sebenarnya dan, dengan probabilitas setidaknya 1 - δ, tidak lebih besar dari true count + εN. Sketsa tidak menyimpan ID, sehingga tetap membutuhkan heap kandidat, himpunan kandidat, atau domain yang dapat diiterasi. Sketsa saja tidak dapat menjawab "ID mana saja yang merupakan top-k?"

Langkah 5: Verifikasi terhadap oracle, bukan hanya satu contoh

Mulailah dengan [1, 2, 1, 3, 2, 1] dan verifikasi bahwa topK(2) mengembalikan dua ID dengan frekuensi 3 dan 2. Kemudian uji struktur kosong, k = 0, k > D, semua nilai sama (ties), satu item dominan ditambah banyak item tunggal, serta satu ID yang berpindah melalui banyak bucket.

Terakhir, buat aliran pembaruan acak dan gunakan penghitungan hash naif ditambah pengurutan penuh sebagai oracle. Pada interval tertentu, verifikasi bahwa panjang hasilnya adalah min(k, D), ID bersifat unik, setiap jumlah yang dilaporkan eksak, dan tidak ada ID yang dikecualikan memiliki jumlah di atas jumlah terkecil yang terpilih. Implementasi di atas lolos uji diferensial ini pada 10.000 pembaruan acak deterministik dan beberapa nilai k.

Contoh jawaban yang kuat

"Saya akan membatasi kontrak eksak untuk pembaruan khusus penambahan (increment-only), k yang spesifik per kueri, dan urutan nilai sama yang bebas. Untuk operasi tulis yang banyak dan kueri yang jarang, saya hanya akan memelihara hash map ID → count untuk ekspektasi penambahan O(1). Sebuah kueri memindai D ID melalui min-heap berukuran k, memakan waktu O(D log k) dan ruang tambahan O(k).

Untuk kueri papan peringkat yang sering, saya akan menggunakan doubly linked frequency buckets. Bucket diurutkan dari frekuensi rendah ke tinggi dan berisi ID dengan frekuensi yang sama; hash map menemukan bucket setiap ID. Satu add hanya memindahkan ID dari f ke f + 1, sehingga ia hanya memeriksa bucket yang bersebelahan dan menghapus bucket sumber yang kosong. Pembaruan memiliki ekspektasi O(1), penelusuran mundur dari ujung akhir mengembalikan hasil dalam O(min(k, D)), dan total ruang adalah O(D). Kebenaran dijamin oleh keanggotaan bucket yang unik, jumlah bucket yang eksak, dan urutan bucket yang meningkat secara ketat.

Jika D tidak muat di memori, kontrak eksak harus diubah. Saya akan mempertahankan m counter Space-Saving dengan interval kesalahan kandidat; estimasi berlebih maksimum dibatasi oleh N / m, dan saya hanya akan memvalidasi himpunan tersebut jika batas bawah dari k kandidat pertama terpisah dari batas atas setelahnya. Count-Min Sketch dapat memperkirakan ID yang diberikan tetapi masih memerlukan mekanisme penemuan kandidat. Sebelum perilisan, saya akan menjalankan pengujian diferensial acak terhadap pengurutan penuh dan secara eksplisit menguji nilai sama, nilai k yang tidak valid, serta batas luapan counter."

Kesalahan umum

• Memilih min-heap sebelum menanyakan tentang beban kerja → Kueri yang sering memindai semua D ID, sementara kueri yang jarang mungkin tidak sebanding dengan biaya pemeliharaan terus-menerus → Tempatkan biaya pada jalur pembaruan atau kueri sesuai dengan rasio sebenarnya.
• Mempertahankan satu K tetap saat k bervariasi → Kueri yang lebih besar dari K yang dipelihara tidak memiliki himpunan kandidat yang lengkap → Batasi k secara eksplisit atau gunakan frequency bucket atau struktur terurut yang mendukung k arbitrer.
• Mengubah kunci heap secara langsung (in place) → Heap biasa tidak mengetahui posisi suatu item, sehingga pengurutannya rusak atau catatan usang menumpuk → Pelihara ID → heap index, atau hapus dan masukkan kembali kunci lama dengan kompleksitas yang telah ditentukan.
• Membiarkan frequency bucket yang kosong tetap terhubung → Kueri dapat menelusuri celah dari frekuensi 1 ke jumlah maksimum → Putus hubungan (unlink) bucket segera setelah ID terakhirnya berpindah.
• Mengklaim hashing strictly O(1) → Map dan Set mendukung analisis kompleksitas ekspektasi biasa, bukan jaminan bahasa yang ketat → Nyatakan asumsi hash; gunakan balanced tree dan terima O(log D) jika batas worst-case diperlukan.
• Mengembalikan top-k langsung dari Count-Min Sketch → Sketsa menjawab kueri untuk kunci yang diberikan dan tidak dapat mengiterasi ID yang tidak diketahui → Pelihara penemuan kandidat secara terpisah atau gunakan Space-Saving, yang mempertahankan kunci-kunci kandidat.
• Melaporkan aproksimasi tanpa batas kesalahan → Pewawancara tidak dapat mengetahui apakah peringkat k dan k + 1 dapat dibedakan → Kembalikan estimasi, batas bawah dan atas, serta status apakah himpunan tersebut tersertifikasi.
• Hanya menguji contoh dasar → Link yang rusak, bucket kosong, dan batas nilai sama sering kali hanya muncul setelah urutan pembaruan yang panjang → Lakukan differential-test terhadap oracle pengurutan penuh dan lakukan assert pada invarian.

Pertanyaan lanjutan dan jawabannya

Pertanyaan lanjutan 1: Jika topK selalu menggunakan K = 100, apakah Anda masih memerlukan frequency buckets?

Belum tentu. Count map, min-heap berukuran 100, dan ID → heap index dapat menyesuaikan anggota heap atau membandingkan terhadap nilai minimum setelah setiap pembaruan dalam O(log 100). Pendekatan ini mungkin lebih sederhana dalam kode dan tata letak memori, tetapi tidak dapat menjawab topK(1000). Frequency buckets sepadan dengan kompleksitasnya ketika k bersifat arbitrer dan pembaruan waktu konstan rata-rata (expected constant-time) diutamakan.

Pertanyaan lanjutan 2: Apa yang berubah jika ID dengan nilai yang sama harus terurut menaik (ascending)?

Ganti Set setiap bucket dengan ordered set, atau urutkan hanya bucket batas yang terpakai sebagian oleh kueri. Pilihan pertama menambahkan O(log s) pada setiap pergerakan untuk bucket berukuran s; pilihan kedua hanya menanggung biaya pengurutan batas pada saat kueri. Pilih berdasarkan seberapa sering urutan deterministik diperlukan.

Pertanyaan lanjutan 3: Bagaimana cara Anda menambahkan remove(x)?

Pindahkan ID dari frekuensi f ke f - 1 dengan memeriksa bucket pendahulu secara simetris, dan hapus ID dari locations saat mencapai nol. Tentukan apakah menghapus ID yang tidak ada akan melemparkan exception atau diabaikan. Dengan operasi add dan remove yang konkuren, pencarian, pemindahan, dan pemutusan bucket kosong harus berbagi satu critical section yang atomik, jika tidak ID yang sama dapat muncul di dua bucket berbeda.

Pertanyaan lanjutan 4: Bagaimana jika kueri hanya meminta data untuk 10 menit terakhir?

Frekuensi tidak lagi bersifat monotonik. Indeks bucket juga membutuhkan event bertanda waktu (timestamped) atau jumlah berbasis interval waktu (time-bucketed) sehingga kedaluwarsa dapat memicu pembaruan balik. Antrean per-event bersifat eksak tetapi menggunakan ruang yang sebanding dengan jumlah event di dalam window tersebut. Time buckets mengurangi state tetapi memperkenalkan batas kesalahan eksplisit. Ringkasan Space-Saving untuk semua riwayat tidak dapat mengurangkan event yang kedaluwarsa secara langsung.

Pertanyaan lanjutan 5: Bagaimana jika interval Space-Saving untuk peringkat k dan k + 1 saling tumpang tindih?

Tingkatkan anggaran counter m, laporkan bahwa himpunan kandidat belum tersertifikasi, atau putar ulang (replay) data untuk menghitung himpunan kandidat secara eksak. Pass kedua hanya memperbaiki kandidat yang dipertahankan. Jika ringkasan terlalu kecil untuk menjamin bahwa top-k sebenarnya masuk ke dalam himpunan tersebut, perbesar himpunan kandidat sebelum pemutaran ulang.

Pertanyaan lanjutan 6: Bagaimana cara Anda memperoleh top-k global di beberapa shard?

Daftar top-k lokal tidak dapat menghasilkan top-k global eksak untuk distribusi arbitrer. Sebuah ID yang berada tepat di bawah batas pada setiap shard dapat masuk ke peringkat global setelah agregasi. Desain eksak harus mengagregasi semua jumlah yang relevan atau memelihara batas kandidat yang membuktikan cakupan. Desain aproksimasi dapat menggabungkan ringkasan yang dapat digabungkan (mergeable summaries), tetapi kontraknya harus menyertakan batas kesalahan tambahan dan latensi pelaporan.