Coding Interview: How Do You Implement an O(1) LFU Cache?

Problem and scope

Implement a fixed-capacity LFUCache. If a key exists, get(key) returns its value and increments its access frequency; otherwise it returns -1. put(key, value) inserts a new key or changes an existing value. Updating an existing key also counts as an access. A new key starts at frequency 1. When inserting into a full cache, evict a key with the lowest frequency. If several keys share that frequency, evict the least recently used one among them.

Both get and put must run in expected O(1) time under the usual average-performance assumption for hash maps. A capacity of 0 is valid and makes every put a no-op. The scope is a single-threaded, in-memory data structure. TTL, byte-based capacity, persistence, and distributed consistency are excluded.

A December 2025 Chinese public interview record explicitly lists LFU Cache, and a 2026 public interview page retains the same problem. LeetCode 460 supplies a stable contract, while the O(1) LFU paper documents the two-level linked structure. This supports the question's current representativeness without establishing one independently verified company attribution, so companyName remains null.

What the interviewer evaluates

First, can the candidate derive the structure from the two eviction dimensions? Key lookup needs a hash map. Selecting by frequency needs a frequency index. Keys at the same frequency still need a recency order. A single heap can find the lowest frequency, but every hit changes a priority and usually costs O(log capacity).

Second, can the candidate state invariants? Every key must identify exactly one node. Every node must belong to exactly one bucket matching its frequency. Each bucket is ordered from most recent to least recent. minFrequency must identify the smallest frequency currently present. Reciting “two maps and a doubly linked list” does not explain empty-bucket deletion, updates, or capacity-one behavior.

Third, does the tie-break remain correct? When a node moves from frequency f to f + 1, it enters the most-recent end of its new bucket because the triggering access just occurred. Eviction removes the least-recent node from the minimum-frequency bucket. An unordered set can satisfy the first LFU rule but loses the LRU tie-break.

Finally, the interviewer should hear a complexity proof and a test strategy. Each operation may perform only a constant number of map operations, bucket lookups, and linked-list changes. Tests should include frequency ties, an old minimum bucket becoming empty, an existing-key update, zero capacity, and differential comparison against a slow reference model over long random sequences.

Clarifying questions before answering

• Does updating an existing key increment its frequency? Yes. After changing the value, put uses the same promotion path as a successful get.
• How are equal frequencies resolved? By LRU within that frequency: evict the key whose last successful get or updating put is oldest.
• Does a new key start at frequency 0 or 1? At 1, because insertion itself counts as one use.
• Is capacity 0 valid? Yes. Every put returns immediately, and every get misses.
• Is the target strict worst-case O(1)? Linked-list changes are worst-case constant. Ordinary maps give the usual average or expected constant-time guarantee, so the overall claim is expected O(1).
• Can frequencies grow without bound? Interview implementations normally assume integers remain in a safe range. A long-running production cache must define overflow, aging, or renormalization, which changes the contract.
• Must the cache be thread-safe? No. Since get changes frequency and order, a concurrent version must make the multi-structure update one critical section.

30-second answer framework

“I will use one map from key to node and another from frequency to a doubly linked list. Each list contains only equal-frequency nodes, ordered newest at the front and oldest at the back. minFrequency directly identifies the eviction bucket. A successful get or updating put removes the node from frequency f, deletes an empty old bucket when needed, increments the frequency, and inserts the node at the front of the new bucket. For a new key, if the cache is full, I remove the back node of the minFrequency bucket; then I add the new node to frequency 1 and set the minimum to 1. Every step uses a constant number of map and pointer operations, so get and put are expected O(1), with O(capacity) space.”

Step-by-step solution

Step 1: Eliminate direct approaches that miss the bound

With one map from key to {value, frequency, lastUsed}, eviction scans all keys and costs O(capacity). A min-heap reduces eviction to O(log capacity), but a successful access changes both frequency and recency, requiring a position index and heap repair. A balanced tree ordered by (frequency, time) also costs O(log capacity).

Expected O(1) requires splitting the order. A map locates a frequency directly. A doubly linked list maintains recency only among nodes of one frequency and supports removal, front insertion, and back removal for a known node. One integer records the current minimum frequency.

Step 2: Define four invariants

1. Every key in nodes points to exactly one real node, and every real node appears in nodes.
2. A node with frequency f appears only in frequencyLists.get(f); the map retains no empty list.
3. Every frequency list runs from most recently used at the front to least recently used at the back.
4. When the cache is nonempty, minFrequency is the minimum frequency of all nodes; it is 0 when the cache is empty.

One promotion moves a node only from f to f + 1. If f is the minimum and its bucket becomes empty, the new minimum is exactly f + 1: no lower bucket existed, and the promoted node guarantees an f + 1 bucket exists. A newly inserted node has frequency 1, so insertion directly resets minFrequency to 1.

Step 3: Implement nodes and frequency lists

A doubly linked list uses head and tail sentinels to avoid separate branches for empty, one-node, and endpoint cases. A node stores its key so eviction can delete the matching entry from nodes without a reverse search.

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
  }
}

The sentinels are not cache entries, do not appear in nodes, and do not count against capacity. remove accepts only a real node currently in that list; the LFUCache invariants establish this precondition.

Step 4: Implement promotion, reads, and writes

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
  }
}

The existing-key branch must precede the capacity check. It does not increase the entry count and must not evict an unrelated key, though it does promote the node and refresh recency within the new bucket. For a new key, eviction occurs before insertion, while minFrequency still identifies the victim bucket.

Step 5: Prove correctness and complexity

All four invariants hold after initialization. A miss changes nothing. A successful access removes one node from the correct old bucket and inserts that same node, with its new frequency, at the most-recent end of the new bucket. Membership does not change, bucket assignment and recency do, and empty-minimum handling preserves the correct minimum.

Updating an existing key changes only its value before running the same promotion. If insertion finds a full cache, the back node of the minimum-frequency bucket satisfies both victim rules: it has the lowest frequency and is oldest among that frequency. Removing it from the list and nodes preserves the one-to-one membership invariant. The new node enters the most-recent end of frequency 1, and minFrequency = 1 restores every invariant.

Each method performs a fixed number of map lookups, insertions, or deletions and a fixed number of linked-list pointer changes. Under the average-performance assumption for maps, get and put are both expected O(1). Every real node exists in one key map and one list, while the number of buckets cannot exceed the number of nodes, so space is O(capacity).

Step 6: Verify with traces and differential tests

For capacity 2, run this sequence:

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

The test set should also cover capacities 0 and 1, misses leaving state unchanged, updates to existing keys, consecutive promotions emptying the minimum bucket, and repeated recency changes among equal-frequency keys. A stronger check implements an O(capacity) reference model that scans for a victim, then compares every get result and final visible key-value state over a deterministic random operation stream. This catches minFrequency drift and broken list links that may appear only after long traces.

High-quality sample answer

“I will first fix the contract: a new key has frequency 1; successful get and updating put both increment frequency; equal frequencies use LRU; and capacity 0 is valid. The target is expected O(1) under ordinary map behavior.

I will maintain key -> node, frequency -> doubly linked list, and minFrequency. A node stores its key, value, frequency, and list links. Within one frequency, the front is newest and the back is oldest. On a hit, I detach the node from bucket f and delete the old bucket if it becomes empty. If that bucket was the minimum, I advance the minimum to f+1. Then I insert the node at the front of bucket f+1.

For put, an existing key changes value and promotes without eviction. For a new key in a full cache, I delete the back node of the minimum-frequency bucket and remove its key index. I then insert the new node into frequency 1 and reset the minimum to 1. The key invariants are one key per node, one correct bucket per node, recency order within each bucket, and an accurate minimum frequency. Every step uses a constant number of hash and pointer operations, with space linear in capacity.

I would test the capacity-two tie trace, capacities zero and one, existing-key updates, and an emptied minimum bucket, then run deterministic differential tests against a scanning model. Production extensions need separate contracts for frequency aging, overflow, concurrency, and TTL; they cannot be folded into the current complexity claim.”

Common mistakes

• Keeping only key -> frequency → eviction still scans all keys → track the minimum-frequency bucket directly.
• Using an unordered set in each frequency bucket → the oldest equal-frequency key is unknown → maintain a doubly linked LRU list per bucket.
• Adding a promoted node at the back → a just-accessed key becomes the oldest → insert promoted nodes at the most-recent end.
• Retaining an empty old bucket → minFrequency can point to no victim → delete empty buckets and advance the minimum when required.
• Checking capacity before handling an existing key → an update evicts an unrelated entry despite no size growth → update, promote, and return first.
• Removing a victim only from its list → the key map keeps a ghost node → delete the same key from both structures.
• Failing to reset the minimum after insertion → later eviction may skip frequency 1 → set it to 1 for every new key.
• Calling the heap solution O(1) → access-triggered priority changes require heap repair → accept O(log capacity) or use frequency buckets.
• Claiming strict O(1) → ordinary maps depend on average hash behavior → state expected O(1).
• Running only the published example → empty-bucket and tie-order drift remain hidden → add invariant checks and random differential tests.

Follow-up questions

Follow-up 1: Why can minFrequency increase by exactly one when the minimum bucket empties?

A node moves only from f to f + 1. If f is the current minimum and its old bucket becomes empty, every other node already has frequency at least f + 1, while the promoted node guarantees that an f + 1 bucket exists. The new minimum is therefore exactly f + 1; no upward scan is needed. If eviction is immediately followed by a new insertion, the final minimum is reset to 1 anyway.

Follow-up 2: How would you add TTL?

TTL introduces a second order based on expiration time. A hit must check expiration, and capacity eviction may first remove expired entries. A min-heap can order expirations, but updates and removals usually become O(log n). A timing wheel lowers some costs but adds precision and state trade-offs. Define whether expiration or LFU wins first, then restate the complexity.

Follow-up 3: What happens when frequencies grow for a long time?

Counters may overflow, and old hot keys may occupy the cache indefinitely. Options include periodic decay, renormalization when the global minimum crosses a threshold, or an approximate time-decayed policy. A full renormalization creates an occasional O(n) task. Stable latency requires incremental migration or an amortized contract, with the semantic difference from exact lifetime counts made explicit.

Follow-up 4: How would you make it thread-safe?

The simplest correct extension puts one mutex around each complete get and put, because a successful read changes a node, two buckets, and the minimum. Sharding reduces contention but gives each shard an independent eviction policy, which differs from one exact global LFU. Fine-grained locking must define a fixed order for the key index, old bucket, and new bucket, and prevent eviction from interleaving with promotion.

Follow-up 5: Is LFU always better than LRU?

It depends on the access distribution. LFU preserves repeatedly accessed long-term hot keys but adapts slowly when historical hot keys become cold. LRU reacts faster to working-set changes and has a smaller implementation. Production caches often combine aging, admission, or approximate policies. The interview implementation precisely exercises a compound eviction rule; it does not prescribe pure LFU for every workload.

Follow-up 6: Why can’t the existing dynamic Top-K frequency buckets be reused unchanged?

Dynamic Top-K only enumerates results by count and can usually leave equal-count order unspecified. This cache must evict exactly at capacity and requires an LRU tie-break, so every bucket needs a recency order and every update must refresh it. Both structures use frequency buckets, but their interfaces, invariants, and correctness goals differ.