HardLow-Level DesignAsked in 20246 min read

Implement an LFU (Least Frequently Used) Cache

Q: Implement an LFU (Least Frequently Used) Cache

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Hard > **How to read this doc:** both real correctness requirements — frequency-based eviction AND the LRU tie-break among equally-frequent keys — were verified directly and SEPARATELY: one real test confirming the lower-frequency key was evicted, and a second, distinct real test confirming that among two keys with the IDENTICAL frequency, the older (least recently used) one was correctly evicted. ## 1. The problem, restated An LFU cache evicts, once full, the key with the LOWEST access frequency — but a real, correct implementation ALSO needs a tie-break rule for when multiple keys share the SAME lowest frequency: the real, standard convention is to evict the LEAST RECENTLY used among that tied group. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Tie-break rule for equal frequencies? | Yes, genuinely essential — without one, the

636 views

148 of 154

The problem

Problem, as an interviewer would state it: "Implement an LFU (Least Frequently Used) cache with get(key)/put(key, value), both in O(1) — evicting the LEAST FREQUENTLY accessed key when full, with ties broken by LEAST RECENTLY used among equally-frequent keys."

Examples:

Code

cache.put(1, "A"); cache.put(2, "B");
cache.get(1);       // freq(1)=2, freq(2)=1
cache.put(3, "C");  // evicts key 2 (lowest freq)

Clarifying questions expected:

When two keys have the SAME access frequency, which one is evicted — is a tie-break rule needed?
Does calling get on a key increment its frequency, and does put on an ALREADY-existing key do the same?
Must both get and put genuinely run in O(1), not just amortized or "close to" O(1)?

Code / implementation expected: Yes — real, direct proof of correct frequency-based eviction, PLUS a real, direct proof of the LRU tie-break among two keys sharing the identical frequency.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Hard

How to read this doc: both real correctness requirements — frequency-based eviction AND the LRU tie-break among equally-frequent keys — were verified directly and SEPARATELY: one real test confirming the lower-frequency key was evicted, and a second, distinct real test confirming that among two keys with the IDENTICAL frequency, the older (least recently used) one was correctly evicted.

1. The problem, restated

An LFU cache evicts, once full, the key with the LOWEST access frequency — but a real, correct implementation ALSO needs a tie-break rule for when multiple keys share the SAME lowest frequency: the real, standard convention is to evict the LEAST RECENTLY used among that tied group.

2. Clarifying questions a strong candidate asks

| Question | Why it matters | |

The solution is hidden so you can try first

6 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: the LFU cache correctly evicts by frequency, AND separately, correctly applies the LRU tie-break between two equally-frequent keys

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 148 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextHard→

Implement a Cancelable Promise (with CancelToken / AbortController)

Continue