22. Implement an LRU Cache — Frontend Interview Question

hard•

People reach for a doubly linked list plus a hash map here, and that's the textbook answer. In JavaScript you can skip all of it, because Map already keeps keys in insertion order. Lean on that and the whole thing is a dozen lines.

Why Map is the cheat code

A Map iterates its keys in the order they were inserted, and map.keys().next().value hands you the oldest one in O(1)-ish time. So "least recently used" becomes "first key in the Map," as long as you keep re-inserting keys whenever you touch them.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key);
    // Touching a key makes it the most recent: delete, then re-insert.
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    // If it exists, drop it so the re-insert moves it to the newest end.
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);

    if (this.map.size > this.capacity) {
      // The first key is the oldest — evict it.
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

The three things to narrate

  1. get is not read-only. Reading a key bumps its recency, so it has to delete-and-re-set even though the value doesn't change. People forget this and fail the "get refreshes recency" case.
  2. put on an existing key also reorders. Same delete-then-set move, otherwise an update wouldn't count as recent use.
  3. Eviction happens after insert. Add first, then check size, then evict the front. Doing it in the other order makes off-by-one bugs.

If they want the "real" data structure

Some interviewers specifically want the doubly linked list version, because Map reordering is technically O(1) but feels like sleight of hand. Be ready to say: a hash map gives O(1) lookup from key to node, and a doubly linked list gives O(1) removal and move-to-front. The Map approach gives you the same complexity with far less code. Offer to write the linked-list version if they'd rather see the mechanics.

What to practice

Get both test cases green in the editor. Then try breaking your own solution: comment out the delete-re-set inside get and watch the recency test fail. Understanding why it fails is the whole point of this question.

More questions

index.js
class LRUCache {
  constructor(capacity) {
    // your code here
  }
  get(key) {
    // your code here
  }
  put(key, value) {
    // your code here
  }
}

// Try it:
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
console.log(cache.get("a")); // 1
cache.put("c", 3);           // evicts "b" (least recently used)
console.log(cache.get("b")); // undefined
⟂ Tests

Test Code

Enter JavaScript that runs after your solution. It should return a value or a Promise.