Wawancara Koding: Bagaimana Cara Mengimplementasikan Cache LFU O(1)?

Masalah dan ruang lingkup

Implementasikan LFUCache dengan kapasitas tetap. Jika suatu kunci ada, get(key) mengembalikan nilainya dan meningkatkan frekuensi aksesnya; jika tidak, ia mengembalikan -1. put(key, value) menyisipkan kunci baru atau mengubah nilai yang sudah ada. Memperbarui kunci yang ada juga dihitung sebagai sebuah akses. Kunci baru dimulai dengan frekuensi 1. Saat menyisipkan ke dalam cache yang penuh, lakukan eviksi terhadap kunci dengan frekuensi terendah. Jika beberapa kunci memiliki frekuensi yang sama, lakukan eviksi terhadap kunci yang paling jarang digunakan baru-baru ini (LRU) di antara kunci-kunci tersebut.

Baik get maupun put harus berjalan dalam waktu O(1) yang diharapkan berdasarkan asumsi kinerja rata-rata yang lazim untuk hash map. Kapasitas 0 adalah valid dan membuat setiap put menjadi no-op. Ruang lingkupnya adalah struktur data dalam memori (in-memory) berutas tunggal (single-threaded). TTL, kapasitas berbasis bita, persistensi, dan konsistensi terdistribusi dikecualikan.

Catatan wawancara publik berbahasa Mandarin bulan Desember 2025 secara eksplisit mencantumkan LFU Cache, dan halaman wawancara publik tahun 2026 tetap mempertahankan masalah yang sama. LeetCode 460 menyediakan kontrak yang stabil, sementara makalah O(1) LFU mendokumentasikan struktur bertingkat dua dengan linked list. Hal ini mendukung representasi masalah tersebut saat ini tanpa menetapkan atribusi perusahaan yang terverifikasi secara independen, sehingga companyName tetap bernilai null.

Hal yang dievaluasi oleh pewawancara

Pertama, apakah kandidat dapat menurunkan struktur data dari dua dimensi eviksi tersebut? Pencarian kunci membutuhkan hash map. Pemilihan berdasarkan frekuensi membutuhkan indeks frekuensi. Kunci pada frekuensi yang sama tetap membutuhkan urutan keterkinian (recency). Sebuah heap tunggal dapat menemukan frekuensi terendah, tetapi setiap hit mengubah prioritas dan biasanya memakan biaya O(log capacity).

Kedua, apakah kandidat dapat menyatakan invarian? Setiap kunci harus mengidentifikasi tepat satu simpul (node). Setiap simpul harus menjadi anggota dari tepat satu bucket yang cocok dengan frekuensinya. Setiap bucket diurutkan dari yang paling terkini hingga yang paling usang. minFrequency harus mengidentifikasi frekuensi terkecil yang ada saat ini. Hanya menghafal "dua map dan sebuah doubly linked list" tidak menjelaskan penghapusan bucket kosong, pembaruan, atau perilaku saat kapasitas bernilai satu.

Ketiga, apakah pemecahan kesamaan (tie-break) tetap benar? Ketika sebuah simpul berpindah dari frekuensi f ke f + 1, simpul tersebut masuk ke ujung paling terkini pada bucket barunya karena akses pemicunya baru saja terjadi. Eviksi menghapus simpul yang paling usang dari bucket berfrekuensi minimum. Unordered set dapat memenuhi aturan LFU pertama tetapi kehilangan pemecah kesamaan LRU.

Terakhir, pewawancara ingin mendengar bukti kompleksitas dan strategi pengujian. Setiap operasi hanya boleh melakukan sejumlah operasi konstan pada map, pencarian bucket, dan perubahan linked list. Pengujian harus mencakup kesamaan frekuensi, bucket minimum lama yang menjadi kosong, pembaruan kunci yang sudah ada, kapasitas nol, dan perbandingan diferensial terhadap model referensi lambat pada urutan acak yang panjang.

Pertanyaan klarifikasi sebelum menjawab

• Apakah memperbarui kunci yang sudah ada meningkatkan frekuensinya? Ya. Setelah mengubah nilainya, put menggunakan jalur promosi yang sama seperti get yang berhasil.
• Bagaimana frekuensi yang sama diselesaikan? Melalui LRU di dalam frekuensi tersebut: eviksi kunci yang get berhasil atau put pembaruannya paling lama terjadi.
• Apakah kunci baru dimulai pada frekuensi 0 atau 1? Pada 1, karena penyisipan itu sendiri dihitung sebagai satu kali penggunaan.
• Apakah kapasitas 0 valid? Ya. Setiap put langsung kembali, dan setiap get menghasilkan miss.
• Apakah targetnya adalah O(1) kasus terburuk yang ketat? Perubahan linked list bersifat konstan pada kasus terburuk. Map biasa memberikan jaminan waktu konstan rata-rata atau yang diharapkan seperti biasanya, sehingga klaim keseluruhannya adalah O(1) yang diharapkan.
• Bisakah frekuensi bertambah tanpa batas? Implementasi wawancara biasanya mengasumsikan integer tetap berada dalam rentang yang aman. Cache produksi yang berjalan lama harus mendefinisikan overflow, penuaan (aging), atau renormalisasi, yang akan mengubah kontraknya.
• Haruskah cache thread-safe? Tidak. Karena get mengubah frekuensi dan urutan, versi konkuren harus menjadikan pembaruan multi-struktur sebagai satu critical section.

Kerangka jawaban 30 detik

“Saya akan menggunakan satu map dari kunci ke simpul dan satu map lainnya dari frekuensi ke doubly linked list. Setiap list hanya berisi simpul-simpul berfrekuensi sama, yang diurutkan dari yang terbaru di depan dan yang terlama di belakang. minFrequency secara langsung mengidentifikasi bucket untuk eviksi. Operasi get yang berhasil atau put yang memperbarui kunci akan melepas simpul dari frekuensi f, menghapus bucket lama yang kosong jika diperlukan, meningkatkan frekuensi, dan menyisipkan simpul di bagian depan bucket baru. Untuk kunci baru, jika cache penuh, saya menghapus simpul paling belakang dari bucket minFrequency; kemudian saya menambahkan simpul baru ke frekuensi 1 dan menyetel nilai minimum ke 1. Setiap langkah menggunakan sejumlah konstan operasi map dan pointer, sehingga get dan put memiliki kompleksitas O(1) yang diharapkan, dengan ruang O(kapasitas).”

Solusi langkah demi langkah

Langkah 1: Mengeliminasi pendekatan langsung yang tidak memenuhi batas kompleksitas

Dengan satu map dari key ke {value, frequency, lastUsed}, eviksi memindai semua kunci dan memakan biaya O(capacity). Min-heap mengurangi biaya eviksi menjadi O(log capacity), tetapi akses yang berhasil mengubah frekuensi dan keterkinian, sehingga membutuhkan indeks posisi dan perbaikan heap. Balanced tree yang diurutkan berdasarkan (frequency, time) juga memakan biaya O(log capacity).

O(1) yang diharapkan mengharuskan pemisahan urutan. Sebuah map menemukan frekuensi secara langsung. Doubly linked list mempertahankan keterkinian hanya di antara simpul-simpul dalam satu frekuensi yang sama dan mendukung penghapusan, penyisipan di depan, serta penghapusan di belakang untuk simpul yang diketahui. Satu integer mencatat frekuensi minimum saat ini.

Langkah 2: Menentukan empat invarian

1. Setiap kunci dalam nodes menunjuk ke tepat satu simpul riil, dan setiap simpul riil muncul dalam nodes.
2. Simpul dengan frekuensi f hanya muncul dalam frequencyLists.get(f); map tidak menyimpan list yang kosong.
3. Setiap list frekuensi diurutkan dari yang paling baru digunakan di depan hingga yang paling usang di belakang.
4. Ketika cache tidak kosong, minFrequency adalah frekuensi minimum dari semua simpul; nilainya 0 ketika cache kosong.

Satu promosi hanya memindahkan simpul dari f ke f + 1. Jika f adalah minimumnya dan bucket tersebut menjadi kosong, minimum yang baru tepat adalah f + 1: tidak ada bucket yang lebih rendah sebelumnya, dan simpul yang dipromosikan menjamin keberadaan bucket f + 1. Simpul yang baru disisipkan memiliki frekuensi 1, sehingga penyisipan secara langsung mereset minFrequency menjadi 1.

Langkah 3: Mengimplementasikan simpul dan list frekuensi

Doubly linked list menggunakan sentinet head dan tail untuk menghindari percabangan terpisah pada kasus kosong, satu simpul, dan titik ujung. Sebuah simpul menyimpan kuncinya sehingga eviksi dapat menghapus entri yang cocok dari nodes tanpa pencarian terbalik.

class Entry {
  frequency = 1
  prev: Entry | null = null
  next: Entry | null = null

  constructor(
    readonly key: number,
    public value: number,
  ) {}
}

class FrequencyList {
  private readonly head = new Entry(0, 0)
  private readonly tail = new Entry(0, 0)
  size = 0

  constructor() {
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  addFirst(node: Entry): void {
    node.prev = this.head
    node.next = this.head.next
    this.head.next!.prev = node
    this.head.next = node
    this.size += 1
  }

  remove(node: Entry): void {
    node.prev!.next = node.next
    node.next!.prev = node.prev
    node.prev = null
    node.next = null
    this.size -= 1
  }

  removeLast(): Entry {
    const node = this.tail.prev
    if (!node || node === this.head) {
      throw new Error("cannot remove from an empty frequency list")
    }
    this.remove(node)
    return node
  }
}

Sentinel bukanlah entri cache, tidak muncul dalam nodes, dan tidak dihitung ke dalam kapasitas. remove hanya menerima simpul riil yang saat ini ada di dalam list tersebut; invarian LFUCache menetapkan prasyarat ini.

Langkah 4: Mengimplementasikan promosi, pembacaan, dan penulisan

class LFUCache {
  private readonly nodes = new Map<number, Entry>()
  private readonly frequencyLists = new Map<number, FrequencyList>()
  private minFrequency = 0

  constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity < 0) {
      throw new RangeError("capacity must be a non-negative integer")
    }
  }

  get(key: number): number {
    const node = this.nodes.get(key)
    if (!node) return -1

    this.promote(node)
    return node.value
  }

  put(key: number, value: number): void {
    if (this.capacity === 0) return

    const existing = this.nodes.get(key)
    if (existing) {
      existing.value = value
      this.promote(existing)
      return
    }

    if (this.nodes.size === this.capacity) {
      const victimList = this.frequencyLists.get(this.minFrequency)
      if (!victimList) throw new Error("missing minimum-frequency list")

      const victim = victimList.removeLast()
      this.nodes.delete(victim.key)
      if (victimList.size === 0) {
        this.frequencyLists.delete(this.minFrequency)
      }
    }

    const node = new Entry(key, value)
    this.getOrCreateList(1).addFirst(node)
    this.nodes.set(key, node)
    this.minFrequency = 1
  }

  private promote(node: Entry): void {
    const oldFrequency = node.frequency
    const oldList = this.frequencyLists.get(oldFrequency)
    if (!oldList) throw new Error("missing source frequency list")

    oldList.remove(node)
    if (oldList.size === 0) {
      this.frequencyLists.delete(oldFrequency)
      if (this.minFrequency === oldFrequency) {
        this.minFrequency = oldFrequency + 1
      }
    }

    node.frequency = oldFrequency + 1
    this.getOrCreateList(node.frequency).addFirst(node)
  }

  private getOrCreateList(frequency: number): FrequencyList {
    let list = this.frequencyLists.get(frequency)
    if (!list) {
      list = new FrequencyList()
      this.frequencyLists.set(frequency, list)
    }
    return list
  }
}

Percabangan untuk kunci yang sudah ada harus mendahului pemeriksaan kapasitas. Percabangan ini tidak menambah jumlah entri dan tidak boleh mengeviksi kunci lain yang tidak terkait, meskipun percabangan ini mempromosikan simpul dan menyegarkan keterkinian di dalam bucket baru. Untuk kunci baru, eviksi terjadi sebelum penyisipan, sementara minFrequency masih mengidentifikasi bucket korban.

Langkah 5: Membuktikan kebenaran dan kompleksitas

Keempat invarian berlaku setelah inisialisasi. Kondisi miss tidak mengubah apa pun. Akses yang berhasil menghapus satu simpul dari bucket lama yang benar dan menyisipkan simpul yang sama, dengan frekuensi barunya, pada ujung paling terkini di bucket baru. Keanggotaan tidak berubah, penetapan bucket dan keterkinian berubah, dan penanganan minimum yang kosong mempertahankan nilai minimum yang benar.

Memperbarui kunci yang sudah ada hanya mengubah nilainya sebelum menjalankan promosi yang sama. Jika penyisipan menemukan cache yang penuh, simpul belakang dari bucket berfrekuensi minimum memenuhi kedua aturan korban: simpul tersebut memiliki frekuensi terendah dan merupakan yang paling usang di antara frekuensi tersebut. Menghapusnya dari list dan nodes mempertahankan invarian keanggotaan satu-ke-satu. Simpul baru masuk ke ujung paling terkini pada frekuensi 1, dan minFrequency = 1 memulihkan setiap invarian.

Setiap metode melakukan sejumlah operasi tetap untuk pencarian, penyisipan, atau penghapusan map, serta sejumlah perubahan pointer linked list yang tetap. Di bawah asumsi kinerja rata-rata untuk map, get dan put keduanya bernilai O(1) yang diharapkan. Setiap simpul riil berada dalam satu map kunci dan satu list, sementara jumlah bucket tidak dapat melebihi jumlah simpul, sehingga ruangnya adalah O(capacity).

Langkah 6: Verifikasi dengan penelusuran (trace) dan pengujian diferensial

Untuk kapasitas 2, jalankan urutan ini:

put(1, 10)  -> key 1 has frequency 1
put(2, 20)  -> keys 1 and 2 tie; 2 is newer
get(1)      -> returns 10; key 1 moves to frequency 2
put(3, 30)  -> evicts key 2 at frequency 1
get(3)      -> returns 30; key 3 moves to frequency 2 and is newer than 1
put(4, 40)  -> keys 1 and 3 tie; evicts older key 1

Kumpulan pengujian juga harus mencakup kapasitas 0 dan 1, miss yang membiarkan state tidak berubah, pembaruan pada kunci yang sudah ada, promosi berurutan yang mengosongkan bucket minimum, dan perubahan keterkinian berulang di antara kunci-kunci dengan frekuensi yang sama. Pemeriksaan yang lebih kuat mengimplementasikan model referensi O(capacity) yang memindai korban, kemudian membandingkan setiap hasil get dan state kunci-nilai akhir yang terlihat pada aliran operasi acak yang deterministik. Hal ini menangkap pergeseran minFrequency dan tautan list yang rusak yang mungkin baru muncul setelah penelusuran panjang.

Contoh jawaban berkualitas tinggi

“Pertama-tama saya akan menetapkan kontraknya: kunci baru memiliki frekuensi 1; get yang berhasil dan put yang memperbarui data keduanya meningkatkan frekuensi; frekuensi yang sama menggunakan LRU; dan kapasitas 0 adalah valid. Targetnya adalah O(1) yang diharapkan di bawah perilaku map biasa.

Saya akan mengelola key -> node, frequency -> doubly linked list, dan minFrequency. Sebuah simpul menyimpan kunci, nilai, frekuensi, dan tautan list-nya. Di dalam satu frekuensi, bagian depan adalah yang terbaru dan bagian belakang adalah yang terlama. Saat terjadi hit, saya melepaskan simpul dari bucket f dan menghapus bucket lama jika menjadi kosong. Jika bucket tersebut merupakan nilai minimum, saya menaikkan minimum ke f+1. Kemudian saya menyisipkan simpul di bagian depan bucket f+1.

Untuk put, kunci yang sudah ada akan diubah nilainya dan dipromosikan tanpa eviksi. Untuk kunci baru di cache yang penuh, saya menghapus simpul belakang dari bucket frekuensi minimum dan menghapus indeks kuncinya. Kemudian saya menyisipkan simpul baru ke dalam frekuensi 1 dan mereset minimum menjadi 1. Invarian kuncinya adalah satu kunci per simpul, satu bucket yang benar per simpul, urutan keterkinian di setiap bucket, dan frekuensi minimum yang akurat. Setiap langkah menggunakan sejumlah operasi hash dan pointer yang konstan, dengan ruang linear terhadap kapasitas.

Saya akan menguji penelusuran kesamaan pada kapasitas dua, kapasitas nol dan satu, pembaruan kunci yang sudah ada, dan bucket minimum yang dikosongkan, lalu menjalankan pengujian diferensial deterministik terhadap model pemindaian. Ekstensi produksi memerlukan kontrak terpisah untuk penuaan frekuensi, overflow, konkurensi, dan TTL; hal-hal tersebut tidak dapat digabungkan ke dalam klaim kompleksitas saat ini.”

Kesalahan umum

• Hanya menyimpan key -> frequency → eviksi tetap memindai semua kunci → lacak bucket frekuensi minimum secara langsung.
• Menggunakan unordered set di setiap bucket frekuensi → kunci terlama pada frekuensi yang sama tidak diketahui → pertahankan list LRU berbentuk doubly linked list per bucket.
• Menambahkan simpul yang dipromosikan di bagian belakang → kunci yang baru saja diakses menjadi yang paling usang → sisipkan simpul yang dipromosikan di ujung yang paling terkini.
• Menyimpan bucket lama yang kosong → minFrequency dapat menunjuk ke tidak adanya korban → hapus bucket yang kosong dan naikkan nilai minimum bila diperlukan.
• Memeriksa kapasitas sebelum menangani kunci yang sudah ada → pembaruan mengeviksi entri lain yang tidak terkait meskipun ukuran tidak bertambah → perbarui, promosikan, dan return terlebih dahulu.
• Hanya menghapus korban dari list-nya → map kunci menyimpan simpul hantu (ghost node) → hapus kunci yang sama dari kedua struktur.
• Gagal mereset minimum setelah penyisipan → eviksi berikutnya dapat melewatkan frekuensi 1 → setel nilainya ke 1 untuk setiap kunci baru.
• Menyebut solusi heap sebagai O(1) → perubahan prioritas yang dipicu oleh akses memerlukan perbaikan heap → terima O(log capacity) atau gunakan bucket frekuensi.
• Mengklaim O(1) yang ketat → map biasa bergantung pada perilaku hash rata-rata → nyatakan O(1) yang diharapkan.
• Hanya menjalankan contoh yang dipublikasikan → pergeseran urutan kesamaan dan bucket kosong tetap tersembunyi → tambahkan pemeriksaan invarian dan pengujian diferensial acak.

Pertanyaan lanjutan

Pertanyaan lanjutan 1: Mengapa minFrequency dapat bertambah tepat satu ketika bucket minimum kosong?

Sebuah simpul hanya berpindah dari f ke f + 1. Jika f adalah nilai minimum saat ini dan bucket lamanya menjadi kosong, setiap simpul lain sudah memiliki frekuensi setidaknya f + 1, sementara simpul yang dipromosikan menjamin bahwa bucket f + 1 ada. Oleh karena itu, minimum yang baru tepat adalah f + 1; pemindaian ke atas tidak diperlukan. Jika eviksi langsung diikuti oleh penyisipan baru, minimum akhirnya tetap direset ke 1.

Pertanyaan lanjutan 2: Bagaimana cara menambahkan TTL?

TTL memperkenalkan urutan kedua berdasarkan waktu kedaluwarsa. Sebuah hit harus memeriksa kedaluwarsa, dan eviksi kapasitas dapat terlebih dahulu menghapus entri yang kedaluwarsa. Min-heap dapat mengurutkan kedaluwarsa, tetapi pembaruan dan penghapusan biasanya menjadi O(log n). Timing wheel menurunkan sebagian biaya tetapi menambah kompromi pada presisi dan state. Tentukan apakah kedaluwarsa atau LFU yang diprioritaskan terlebih dahulu, lalu nyatakan kembali kompleksitasnya.

Pertanyaan lanjutan 3: Apa yang terjadi jika frekuensi terus bertambah dalam waktu yang lama?

Penghitung dapat mengalami overflow, dan kunci lama yang sering diakses (hot keys) dapat menempati cache tanpa batas. Pilihannya mencakup peluruhan berkala (periodic decay), renormalisasi ketika minimum global melewati ambang batas, atau kebijakan peluruhan waktu perkiraan. Renormalisasi penuh menciptakan tugas O(n) sesekali. Latensi yang stabil membutuhkan migrasi bertahap atau kontrak yang diamortisasi, dengan perbedaan semantik dari hitungan masa pakai persis dijelaskan secara eksplisit.

Pertanyaan lanjutan 4: Bagaimana cara membuatnya thread-safe?

Ekstensi paling sederhana yang benar menempatkan satu mutex di sekitar setiap get dan put yang lengkap, karena pembacaan yang berhasil mengubah simpul, dua bucket, dan nilai minimum. Sharding mengurangi perebutan sumber daya (contention) tetapi memberikan setiap pecahan kebijakan eviksi independen, yang berbeda dari satu LFU global yang pasti. Penguncian berbutir halus (fine-grained locking) harus menentukan urutan tetap untuk indeks kunci, bucket lama, dan bucket baru, serta mencegah eviksi saling bertumpukan dengan promosi.

Pertanyaan lanjutan 5: Apakah LFU selalu lebih baik daripada LRU?

Itu tergantung pada distribusi akses. LFU mempertahankan kunci sering diakses jangka panjang yang diakses berulang kali, tetapi lambat beradaptasi saat kunci yang dulunya sering diakses menjadi jarang diakses. LRU bereaksi lebih cepat terhadap perubahan working-set dan memiliki implementasi yang lebih sederhana. Cache produksi sering kali menggabungkan penuaan (aging), admisi, atau kebijakan aproksimasi. Implementasi wawancara ini secara tepat menguji aturan eviksi majemuk; ini tidak mewajibkan penggunaan LFU murni untuk setiap beban kerja.

Pertanyaan lanjutan 6: Mengapa bucket frekuensi Top-K dinamis yang ada tidak dapat digunakan kembali secara langsung?

Top-K dinamis hanya mencantumkan hasil berdasarkan hitungan dan biasanya dapat membiarkan urutan hitungan yang sama tidak ditentukan. Cache ini harus melakukan eviksi tepat pada batas kapasitas dan memerlukan pemecah kesamaan LRU, sehingga setiap bucket memerlukan urutan keterkinian dan setiap pembaruan harus menyegarkannya. Kedua struktur menggunakan bucket frekuensi, tetapi antarmuka, invarian, dan tujuan kebenarannya berbeda.