MediumDSA6 min read

Implement LRU Cache (get/put with O(1))

Q: Implement LRU Cache (get/put with O(1))

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Medium > **How to read this doc:** the classic answer is a hash map plus a doubly linked list. In JavaScript a plain `Map` already remembers insertion order, so the whole structure collapses to one `Map`: "delete then set" moves a key to the newest position, and the first key in iteration order is the least recently used. The LeetCode trace was reproduced, and 10x more operations were verified to take 10.0x the time. ## 1. The problem, restated A bounded cache that, when full, discards the entry that was used longest ago. Every `get` and every `put` must both find an entry and reorder the recency list, which is why O(1) requires combining a hash lookup with an order structure that supports cheap "move to front" and "remove oldest". ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | What counts as a use? | Both reads and writes refresh

338 views

119 of 154

The problem

Problem, as an interviewer would state it: "Design an LRU cache with get(key) and put(key, value) in O(1). Evict the least recently used entry when capacity is exceeded. Use a Map or a doubly linked list."

Examples:

Code

const c = new LRUCache(2);
c.put(1, 1); c.put(2, 2);
c.get(1);    // 1
c.put(3, 3); // evicts key 2
c.get(2);    // not found

Clarifying questions expected:

Does a get count as a "use" that refreshes recency, and does put on an existing key too?
What should get return for a missing key?
What if capacity is zero or invalid?

Code / implementation expected: Yes — real, direct proof of the eviction order, recency refresh on both operations, and the O(1) scaling.

lru
cache
map
doubly-linked-list

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: Medium

How to read this doc: the classic answer is a hash map plus a doubly linked list. In JavaScript a plain Map already remembers insertion order, so the whole structure collapses to one Map: "delete then set" moves a key to the newest position, and the first key in iteration order is the least recently used. The LeetCode trace was reproduced, and 10x more operations were verified to take 10.0x the time.

1. The problem, restated

A bounded cache that, when full, discards the entry that was used longest ago. Every get and every put must both find an entry and reorder the recency list, which is why O(1) requires combining a hash lookup with an order structure that supports cheap "move to front" and "remove oldest".

2. Clarifying questions a strong candidate asks

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: an LRU cache on Map insertion order reproduces the LeetCode trace, refreshes recency on update, and evicts the oldest entry

Practice

Discussion

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

No comments yet. Share how you would answer it.

Question 119 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 nextMedium→

Promise Retry with Backoff

Continue