Temu Duga Pengekodan: Bagaimana Anda Melaksanakan Cache LFU O(1)?

Masalah dan skop

Laksanakan LFUCache dengan kapasiti tetap. Jika sesuatu kunci wujud, get(key) mengembalikan nilainya dan menambah kekerapan aksesnya; jika tidak, ia mengembalikan -1. put(key, value) memasukkan kunci baharu atau mengubah nilai sedia ada. Mengemas kini kunci sedia ada juga dikira sebagai satu akses. Kunci baharu bermula pada kekerapan 1. Apabila memasukkan ke dalam cache yang penuh, singkirkan kunci dengan kekerapan terendah. Jika beberapa kunci berkongsi kekerapan tersebut, singkirkan kunci yang paling lama tidak digunakan (LRU) antara kunci-kunci berkenaan.

Kedua-dua get dan put mesti berjalan dalam masa jangkaan O(1) di bawah andaian prestasi purata biasa bagi peta cincangan (hash map). Kapasiti 0 adalah sah dan menjadikan setiap put sebagai no-op. Skopnya adalah struktur data dalam ingatan (in-memory) berbenang tunggal (single-threaded). TTL, kapasiti berasaskan bait, ketekalan (persistence), dan ketekalan teragih adalah dikecualikan.

Rekod temu duga awam China pada Disember 2025 secara eksplisit menyenaraikan LFU Cache, dan halaman temu duga awam 2026 mengekalkan masalah yang sama. LeetCode 460 membekalkan kontrak yang stabil, manakala kertas kerja O(1) LFU mendokumentasikan struktur berpaut dua peringkat. Ini menyokong kerelevanan semasa soalan ini tanpa menetapkan atribusi syarikat yang disahkan secara bebas, maka companyName kekal null.

Perkara yang dinilai oleh penemu duga

Pertama, bolehkah calon memperoleh struktur tersebut daripada dua dimensi penyingkiran? Carian kunci memerlukan peta cincangan. Pemilihan mengikut kekerapan memerlukan indeks kekerapan. Kunci pada kekerapan yang sama masih memerlukan susunan kekinian (recency). Tindanan (heap) tunggal boleh mencari kekerapan terendah, tetapi setiap capaian mengubah keutamaan dan biasanya menelan kos O(log capacity).

Kedua, bolehkah calon menyatakan invariant? Setiap kunci mesti mengenal pasti tepat satu nod. Setiap nod mesti tergolong dalam tepat satu baldi yang sepadan dengan kekerapannya. Setiap baldi disusun daripada yang paling terkini kepada yang paling lama. minFrequency mesti mengenal pasti kekerapan terkecil yang ada pada masa ini. Sekadar membaca "dua peta dan senarai pautan berganda" tidak menjelaskan pemadaman baldi kosong, kemas kini, atau tingkah laku kapasiti satu.

Ketiga, adakah pemecahan seri kekal betul? Apabila nod berpindah daripada kekerapan f kepada f + 1, ia memasuki hujung paling terkini bagi baldi baharunya kerana akses pencetus baru sahaja berlaku. Penyingkiran membuang nod paling lama daripada baldi kekerapan minimum. Set tidak tertib boleh memenuhi peraturan LFU pertama tetapi kehilangan pemecah seri LRU.

Akhir sekali, penemu duga ingin mendengar bukti kerumitan dan strategi ujian. Setiap operasi hanya boleh melakukan bilangan operasi peta, carian baldi, dan perubahan senarai pautan yang malar. Ujian harus merangkumi seri kekerapan, baldi minimum lama yang menjadi kosong, kemas kini kunci sedia ada, kapasiti sifar, dan perbandingan pembezaan terhadap model rujukan yang perlahan pada jujukan rawak yang panjang.

Soalan penjelasan sebelum menjawab

• Adakah mengemas kini kunci sedia ada menambah kekerapannya? Ya. Selepas menukar nilai, put menggunakan laluan promosi yang sama seperti get yang berjaya.
• Bagaimanakah kekerapan yang sama diselesaikan? Melalui LRU dalam kekerapan tersebut: singkirkan kunci yang get berjaya atau put pengemas kiniannya paling lama berlaku.
• Adakah kunci baharu bermula pada kekerapan 0 atau 1? Pada 1, kerana pemasukan itu sendiri dikira sebagai satu penggunaan.
• Adakah kapasiti 0 sah? Ya. Setiap put kembali serta-merta, dan setiap get mengalami miss.
• Adakah sasarannya O(1) kes terburuk yang ketat? Perubahan senarai pautan adalah malar pada kes terburuk. Peta biasa memberikan jaminan masa malar purata atau jangkaan yang biasa, jadi tuntutan keseluruhan ialah jangkaan O(1).
• Bolehkah kekerapan membesar tanpa batas? Pelaksanaan temu duga biasanya menganggap integer kekal dalam julat yang selamat. Cache pengeluaran yang berjalan lama mesti mentakrifkan limpahan (overflow), penuaan (aging), atau penormalan semula, yang mengubah kontrak tersebut.
• Adakah cache perlu thread-safe? Tidak. Oleh kerana get mengubah kekerapan dan susunan, versi serempak mesti menjadikan kemas kini berbilang struktur sebagai satu bahagian genting (critical section).

Kerangka jawapan 30 saat

“Saya akan menggunakan satu peta daripada kunci kepada nod dan satu lagi daripada kekerapan kepada senarai pautan berganda. Setiap senarai hanya mengandungi nod dengan kekerapan yang sama, disusun dengan yang terbaharu di hadapan dan yang paling lama di belakang. minFrequency secara langsung mengenal pasti baldi penyingkiran. Get yang berjaya atau put pengemas kinian mengalih keluar nod daripada kekerapan f, memadamkan baldi lama yang kosong jika perlu, menambah kekerapan, dan memasukkan nod di hadapan baldi baharu. Bagi kunci baharu, jika cache penuh, saya membuang nod belakang bagi baldi minFrequency; kemudian saya menambah nod baharu kepada kekerapan 1 dan menetapkan minimum kepada 1. Setiap langkah menggunakan bilangan operasi peta dan penunjuk yang malar, jadi get dan put adalah jangkaan O(1), dengan ruang O(kapasiti).”

Penyelesaian langkah demi langkah

Langkah 1: Hapuskan pendekatan langsung yang tidak mencapai batas kerumitan

Dengan satu peta daripada key kepada {value, frequency, lastUsed}, penyingkiran mengimbas semua kunci dan menelan kos O(capacity). Min-heap mengurangkan penyingkiran kepada O(log capacity), tetapi akses yang berjaya mengubah kedua-dua kekerapan dan kekinian, memerlukan indeks kedudukan dan pembaikan heap. Pokok seimbang yang disusun mengikut (frequency, time) juga menelan kos O(log capacity).

Jangkaan O(1) memerlukan pemisahan susunan. Peta mencari kekerapan secara langsung. Senarai pautan berganda mengekalkan kekinian hanya dalam kalangan nod dengan satu kekerapan yang sama dan menyokong penyingkiran, pemasukan di hadapan, dan penyingkiran di belakang bagi nod yang diketahui. Satu integer merekodkan kekerapan minimum semasa.

Langkah 2: Takrifkan empat invariant

1. Setiap kunci dalam nodes menunjuk kepada tepat satu nod sebenar, dan setiap nod sebenar muncul dalam nodes.
2. Nod dengan kekerapan f hanya muncul dalam frequencyLists.get(f); peta tidak menyimpan senarai yang kosong.
3. Setiap senarai kekerapan berjalan daripada yang paling terkini digunakan di hadapan kepada yang paling lama digunakan di belakang.
4. Apabila cache tidak kosong, minFrequency ialah kekerapan minimum bagi semua nod; ia adalah 0 apabila cache kosong.

Satu promosi hanya memindahkan nod daripada f kepada f + 1. Jika f ialah nilai minimum dan baldinye menjadi kosong, nilai minimum baharu adalah tepat f + 1: tiada baldi yang lebih rendah wujud sebelum ini, dan nod yang dipromosikan menjamin bahawa baldi f + 1 wujud. Nod yang baru dimasukkan mempunyai kekerapan 1, jadi pemasukan terus menetapkan semula minFrequency kepada 1.

Langkah 3: Laksanakan nod dan senarai kekerapan

Senarai pautan berganda menggunakan sentinel kepala dan ekor bagi mengelakkan percabangan berasingan untuk kes kosong, satu nod, dan titik hujung. Nod menyimpan kuncinya supaya penyingkiran boleh memadamkan entri yang sepadan daripada nodes tanpa carian songsang.

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 bukan entri cache, tidak muncul dalam nodes, dan tidak dikira dalam kapasiti. remove hanya menerima nod sebenar yang kini berada dalam senarai tersebut; invariant LFUCache menetapkan prasyarat ini.

Langkah 4: Laksanakan promosi, bacaan, 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
  }
}

Cabang kunci sedia ada mesti mendahului semakan kapasiti. Ia tidak meningkatkan bilangan entri dan tidak boleh menyingkirkan kunci lain yang tidak berkaitan, walaupun ia mempromosikan nod dan memperbaharui kekinian dalam baldi baharu. Bagi kunci baharu, penyingkiran berlaku sebelum pemasukan, semasa minFrequency masih mengenal pasti baldi mangsa.

Langkah 5: Buktikan ketepatan dan kerumitan

Kesemua empat invariant kekal sah selepas permulaan. Keadaan miss tidak mengubah apa-apa. Akses yang berjaya mengeluarkan satu nod daripada baldi lama yang betul dan memasukkan nod yang sama, dengan kekerapan baharunya, di hujung paling terkini dalam baldi baharu. Keahlian tidak berubah, peruntukan baldi dan kekinian berubah, dan pengendalian minimum kosong mengekalkan nilai minimum yang betul.

Mengemas kini kunci sedia ada hanya menukar nilainya sebelum menjalankan promosi yang sama. Jika pemasukan mendapati cache penuh, nod belakang baldi kekerapan minimum memenuhi kedua-dua peraturan mangsa: ia mempunyai kekerapan terendah dan paling lama dalam kekerapan tersebut. Mengeluarkannya daripada senarai dan nodes mengekalkan invariant keahlian satu-ke-satu. Nod baharu memasuki hujung paling terkini pada kekerapan 1, dan minFrequency = 1 memulihkan setiap invariant.

Setiap kaedah melakukan bilangan carian, pemasukan, atau pemadaman peta yang tetap dan bilangan perubahan penunjuk senarai pautan yang tetap. Di bawah andaian prestasi purata untuk peta, get dan put kedua-duanya adalah jangkaan O(1). Setiap nod sebenar wujud dalam satu peta kunci dan satu senarai, manakala bilangan baldi tidak boleh melebihi bilangan nod, jadi ruang adalah O(capacity).

Langkah 6: Sahkan dengan surihan (trace) dan ujian pembezaan

Untuk kapasiti 2, jalankan jujukan 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

Set ujian juga harus merangkumi kapasiti 0 dan 1, miss yang membiarkan keadaan tidak berubah, kemas kini kepada kunci sedia ada, promosi berturut-turut yang mengosongkan baldi minimum, dan perubahan kekinian berulang dalam kalangan kunci berkekerapan sama. Pemeriksaan yang lebih mantap melaksanakan model rujukan O(capacity) yang mengimbas mangsa, kemudian membandingkan setiap hasil get dan keadaan kunci-nilai akhir yang kelihatan merentasi aliran operasi rawak deterministik. Ini menangkap hanyutan minFrequency dan pautan senarai yang rosak yang mungkin hanya muncul selepas surihan yang panjang.

Contoh jawapan berkualiti tinggi

“Mula-mula saya akan menetapkan kontrak: kunci baharu mempunyai kekerapan 1; get yang berjaya dan put pengemas kinian kedua-duanya meningkatkan kekerapan; kekerapan yang sama menggunakan LRU; dan kapasiti 0 adalah sah. Sasarannya ialah jangkaan O(1) di bawah tingkah laku peta biasa.

Saya akan mengekalkan key -> node, frequency -> doubly linked list, dan minFrequency. Nod menyimpan kunci, nilai, kekerapan, dan pautan senarainya. Dalam satu kekerapan, bahagian hadapan adalah yang terbaharu dan bahagian belakang adalah yang paling lama. Apabila berlaku hit, saya mencabut nod daripada baldi f dan memadamkan baldi lama jika ia menjadi kosong. Jika baldi tersebut adalah minimum, saya memajukan minimum kepada f+1. Kemudian saya memasukkan nod di hadapan baldi f+1.

Bagi put, kunci sedia ada ditukar nilainya dan dipromosikan tanpa penyingkiran. Bagi kunci baharu dalam cache yang penuh, saya memadamkan nod belakang baldi kekerapan minimum dan mengeluarkan indeks kuncinya. Saya kemudian memasukkan nod baharu ke dalam kekerapan 1 dan menetapkan semula minimum kepada 1. Invariant utama ialah satu kunci bagi setiap nod, satu baldi yang betul bagi setiap nod, susunan kekinian dalam setiap baldi, dan kekerapan minimum yang tepat. Setiap langkah menggunakan bilangan operasi cincangan dan penunjuk yang malar, dengan ruang linear kepada kapasiti.

Saya akan menguji surihan seri kapasiti dua, kapasiti sifar dan satu, kemas kini kunci sedia ada, dan baldi minimum yang dikosongkan, kemudian menjalankan ujian pembezaan deterministik terhadap model pengimbasan. Lanjutan pengeluaran memerlukan kontrak berasingan untuk penuaan kekerapan, limpahan, keserempakan, dan TTL; ia tidak boleh digabungkan ke dalam tuntutan kerumitan semasa.”

Kesilapan lazim

• Hanya mengekalkan key -> frequency → penyingkiran masih mengimbas semua kunci → jejaki baldi kekerapan minimum secara langsung.
• Menggunakan set tidak tertib dalam setiap baldi kekerapan → kunci paling lama berkekerapan sama tidak diketahui → kekalkan senarai LRU berpaut berganda bagi setiap baldi.
• Menambah nod yang dipromosikan di belakang → kunci yang baru diakses menjadi yang paling lama → masukkan nod yang dipromosikan di hujung paling terkini.
• Mengekalkan baldi lama yang kosong → minFrequency boleh menunjuk kepada ketiadaan mangsa → padamkan baldi kosong dan majukan minimum apabila diperlukan.
• Menyemak kapasiti sebelum mengendalikan kunci sedia ada → kemas kini menyingkirkan entri lain yang tidak berkaitan walaupun tiada pertambahan saiz → kemas kini, promosikan, dan return terlebih dahulu.
• Mengeluarkan mangsa hanya daripada senarainya → peta kunci mengekalkan nod hantu (ghost node) → padamkan kunci yang sama daripada kedua-dua struktur.
• Gagal menetapkan semula minimum selepas pemasukan → penyingkiran kemudian mungkin melangkau kekerapan 1 → tetapkannya kepada 1 bagi setiap kunci baharu.
• Memanggil penyelesaian heap sebagai O(1) → perubahan keutamaan yang dicetuskan oleh akses memerlukan pembaikan heap → terima O(log capacity) atau gunakan baldi kekerapan.
• Mendakwa O(1) yang ketat → peta biasa bergantung pada tingkah laku cincangan purata → nyatakan jangkaan O(1).
• Hanya menjalankan contoh yang diterbitkan → hanyutan susunan seri dan baldi kosong kekal tersembunyi → tambahkan semakan invariant dan ujian pembezaan rawak.

Soalan susulan

Soalan susulan 1: Mengapakah minFrequency boleh meningkat tepat satu apabila baldi minimum kosong?

Nod hanya berpindah daripada f kepada f + 1. Jika f ialah minimum semasa dan baldi lamanya menjadi kosong, setiap nod lain sudah mempunyai kekerapan sekurang-kurangnya f + 1, manakala nod yang dipromosikan menjamin bahawa baldi f + 1 wujud. Oleh itu, minimum baharu adalah tepat f + 1; tiada imbasan ke atas diperlukan. Jika penyingkiran diikuti serta-merta oleh pemasukan baharu, minimum akhir tetap ditetapkan semula kepada 1.

Soalan susulan 2: Bagaimanakah anda menambah TTL?

TTL memperkenalkan susunan kedua berdasarkan masa tamat tempoh. Suatu hit mesti menyemak tamat tempoh, dan penyingkiran kapasiti mungkin terlebih dahulu membuang entri yang telah tamat tempoh. Min-heap boleh menyusun tamat tempoh, tetapi kemas kini dan penyingkiran biasanya menjadi O(log n). Timing wheel mengurangkan sesetengah kos tetapi menambah kompromi pada ketepatan dan keadaan. Tentukan sama ada tamat tempoh atau LFU yang diutamakan dahulu, kemudian nyatakan semula kerumitan.

Soalan susulan 3: Apakah yang berlaku apabila kekerapan berkembang untuk jangka masa yang lama?

Pembilang mungkin melimpah (overflow), dan kunci kerap lama (old hot keys) mungkin menduduki cache selama-lamanya. Pilihan termasuk pereputan berkala (periodic decay), penormalan semula apabila minimum global melepasi ambang, atau dasar pereputan masa anggaran. Penormalan semula penuh mewujudkan tugas O(n) sekali-sekala. Pendaman yang stabil memerlukan penghijrahan berperingkat atau kontrak yang dilunaskan (amortized), dengan perbezaan semantik daripada kiraan sepanjang hayat yang tepat dijelaskan secara eksplisit.

Soalan susulan 4: Bagaimanakah anda menjadikannya thread-safe?

Lanjutan betul yang paling mudah meletakkan satu mutex di sekeliling setiap get dan put yang lengkap, kerana bacaan yang berjaya mengubah nod, dua baldi, dan minimum. Pemecahan (sharding) mengurangkan pertikaian (contention) tetapi memberikan setiap pecahan dasar penyingkiran bebas, yang berbeza daripada satu LFU global yang tepat. Penguncian berbutir halus (fine-grained locking) mesti mentakrifkan susunan tetap untuk indeks kunci, baldi lama, dan baldi baharu, serta menghalang penyingkiran daripada bersilang dengan promosi.

Soalan susulan 5: Adakah LFU sentiasa lebih baik daripada LRU?

Ia bergantung pada taburan akses. LFU mengekalkan kunci kerap jangka panjang yang diakses berulang kali tetapi lambat menyesuaikan diri apabila kunci yang dahulunya kerap menjadi jarang digunakan. LRU bertindak balas lebih cepat terhadap perubahan set kerja dan mempunyai pelaksanaan yang lebih kecil. Cache pengeluaran sering menggabungkan penuaan (aging), penerimaan (admission), atau dasar anggaran. Pelaksanaan temu duga ini secara tepat menguji peraturan penyingkiran gabungan; ia tidak menetapkan LFU tulen untuk setiap beban kerja.

Soalan susulan 6: Mengapakah baldi kekerapan Top-K dinamik sedia ada tidak boleh diguna semula tanpa perubahan?

Top-K dinamik hanya menyenaraikan hasil mengikut kiraan dan biasanya boleh membiarkan susunan bagi kiraan yang sama tidak ditentukan. Cache ini mesti menyingkirkan tepat pada had kapasiti dan memerlukan pemecah seri LRU, jadi setiap baldi memerlukan susunan kekinian dan setiap kemas kini mesti menyegarkannya. Kedua-dua struktur menggunakan baldi kekerapan, tetapi antara muka, invariant, dan matlamat ketepatannya adalah berbeza.