JavaScript LRU Cache

Can you keep hot data one lookup away — and throw out the thing nobody has touched, in constant time?

Level: Hard · Coding Round · Data Structures

Why This Question Matters

• Every product cache (API, search, images) will grow forever unless something is evicted.
• Interviewers use LRU to test O(1) lookup + order, not whether you can write a Map.
• Getting recency wrong serves stale UI or blows memory — both show up in real apps.
• It is a standard coding-round DS question (LeetCode-style) that still maps to frontend work.

Problem

“Implement an LRU cache. Capacity is fixed. get and put should both be O(1).”

class LRUCache {
  constructor(capacity) {}
  get(key) {}
  put(key, value) {}
}

get(key)

• If the key is in the cache, return its value and treat it as most recently used.
• If it is not, return undefined. Do not insert. Do not change order.

put(key, value)

• If the key already exists, update the value and treat it as most recently used. Do not evict another key.
• If it is new and there is room, insert it as most recently used.
• If it is new and the cache is full, evict the least recently used key, then insert.

Clarify before you code

• undefined is a valid stored value — check presence with has, not truthiness.
• Capacity is a positive integer.
• Both operations: O(1) expected time.

Example

Capacity is 2.

const cache = new LRUCache(2);
 
cache.put("a", 1);
cache.put("b", 2);

LRU → MRU

[ a, b ]

Access a:

cache.get("a");

a becomes the most recently used:

[ b, a ]

Add c:

cache.put("c", 3);

The cache is full, so remove b:

[ a, c ]

Therefore:

cache.get("b"); // undefined
cache.get("a"); // 1
cache.get("c"); // 3

Mental Model

LRU                              MRU
 ↓                                ↓
[ oldest ] → [ ... ] → [ newest ]

Every successful access moves the item to the MRU position.

Solution

JavaScript Map

For JavaScript, Map gives us a clean implementation because it preserves insertion order.

First key → LRU
Last key  → MRU

To move a key to MRU:

map.delete(key);
map.set(key, value);

To find the LRU key:

map.keys().next().value;

Implementation

class LRUCache {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new Error("Capacity must be a positive integer");
    }
 
    this.capacity = capacity;
    this.cache = new Map();
  }
 
  get(key) {
    if (!this.cache.has(key)) {
      return undefined;
    }
 
    const value = this.cache.get(key);
 
    // Move to MRU
    this.cache.delete(key);
    this.cache.set(key, value);
 
    return value;
  }
 
  put(key, value) {
    // Existing key → update + move to MRU
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
 
    // New key + full cache → remove LRU
    else if (this.cache.size === this.capacity) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
 
    // Add as MRU
    this.cache.set(key, value);
  }
}

Why This Works

There are three cases.

get(existing)

[ a, b, c ]

get(a)

[ b, c, a ]

a becomes MRU.

put(existing)

[ a, b ]

put(a, 10)

[ b, a ]

Update the value and refresh recency.

No eviction.

put(new) when full

[ a, b, c ]

put(d, 4)

Remove a
Add d

[ b, c, d ]

Edge Cases

Cache miss

cache.get("missing");
// undefined

The cache order doesn’t change.

undefined as a value

Don’t use:

cache.get(key) === undefined

to determine whether a key exists.

Use:

cache.has(key)

because this is valid:

cache.put("a", undefined);

Capacity = 1

const cache = new LRUCache(1);
 
cache.put("a", 1);
cache.put("b", 2);

Result:

[ b ]

Complexity

Use Cases

API Response Cache

Avoid repeated expensive API requests for recently requested data.

Search Result Cache

Reuse results for recently searched queries.

Image / Asset Cache

Keep recently accessed assets while limiting memory usage.

Database Query Cache

Reduce repeated queries for recently requested data.

Browser / Application Cache

Keep recently used data without allowing the cache to grow indefinitely.

Senior Follow-Ups

1. Why not use an Array?

Q. Why not store {key, value} pairs in an array?

Answer: Finding or moving an item in an array can require O(n) time.

LRU requires:

get() → O(1)
put() → O(1)

So an array alone doesn’t meet the requirement.

2. Why use Map?

Q. Why Map instead of a plain object?

Answer: We need fast key lookup and predictable insertion order.

Map gives us both:

Map
├── O(1) expected lookup
└── insertion order

That lets us treat:

first → LRU
last  → MRU

3. Why does get() change the order?

Q. get only reads. Why move the key?

Answer: Because accessing an item makes it recently used.

Before:

[ A, B, C ]

get(A)

After:

[ B, C, A ]

If we don’t update the order, we could evict an item that was just accessed.

4. How would you implement the classic LRU without relying on Map ordering?

Q. What if we cannot depend on Map insertion order?

Answer: Use:

Hash Map + Doubly Linked List

The Map finds the node in O(1):

key → node

The linked list maintains:

LRU ↔ ... ↔ MRU

This gives O(1) lookup, removal, movement, and eviction.

5. Why a doubly linked list?

Q. Why not a singly linked list?

Answer: We need to remove and move any node in O(1).

With:

node.prev
node.next

we can remove a node without traversing the list.

A singly linked list would normally require finding the previous node first.

6. How would you add TTL?

Q. How do you expire items after a time limit?

Answer: Store expiration metadata:

{
  value,
  expiresAt
}

Then decide when expiration is handled:

• During get()
• Periodically in the background
• By the underlying cache system

TTL and LRU solve different problems:

TTL → How long can an item live?
LRU → What gets removed when capacity is reached?

They can be combined.

7. What if the cache is limited by memory instead of item count?

Q. What if the cap is 100MB, not 1000 keys?

Answer: Instead of:

capacity = 1000 entries

use a weighted capacity such as:

capacity = 100 MB

Each entry needs a size/weight.

When the limit is exceeded, evict LRU entries until enough space is available.

8. Is LRU always the right eviction policy?

Q. Should every cache use LRU?

Answer: No. It depends on the access pattern.

Common alternatives:

If frequency matters more than recency, LFU may be more appropriate.

9. What happens with multiple application servers?

Q. Do two servers share this cache?

Answer: An in-memory LRU is local to one process:

Server A → Cache A
Server B → Cache B
Server C → Cache C

Each server can have different cache contents.

If the cache must be shared across servers, a distributed cache such as Redis may be more appropriate.

10. What would you test?

Q. What cases do you cover before you say you are done?

Answer: At minimum:

✓ get existing key
✓ get missing key
✓ get moves key to MRU
✓ put new key
✓ put existing key
✓ eviction removes correct LRU
✓ capacity = 1
✓ undefined as a value
✓ repeated get/update

Example:

const cache = new LRUCache(2);
 
cache.put("a", 1);
cache.put("b", 2);
 
cache.get("a");
cache.put("c", 3);
 
console.log(cache.get("b")); // undefined
console.log(cache.get("a")); // 1
console.log(cache.get("c")); // 3

Classic LRU Implementation

If the interviewer asks for the classic data-structure solution:

Map + Doubly Linked List

LRU                              MRU
 ↓                                ↓
HEAD ↔ A ↔ B ↔ C ↔ TAIL

Implementation

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}
 
class LRUCache {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new Error("Capacity must be a positive integer");
    }
 
    this.capacity = capacity;
    this.cache = new Map();
 
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
 
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
 
  addToEnd(node) {
    const last = this.tail.prev;
 
    last.next = node;
    node.prev = last;
 
    node.next = this.tail;
    this.tail.prev = node;
  }
 
  get(key) {
    const node = this.cache.get(key);
 
    if (!node) {
      return undefined;
    }
 
    this.remove(node);
    this.addToEnd(node);
 
    return node.value;
  }
 
  put(key, value) {
    const node = this.cache.get(key);
 
    if (node) {
      node.value = value;
 
      this.remove(node);
      this.addToEnd(node);
 
      return;
    }
 
    if (this.cache.size === this.capacity) {
      const lru = this.head.next;
 
      this.remove(lru);
      this.cache.delete(lru.key);
    }
 
    const newNode = new Node(key, value);
 
    this.cache.set(key, newNode);
    this.addToEnd(newNode);
  }
}

Senior Engineer Interview Answer

“We need O(1) lookup, O(1) recency updates, and O(1) eviction. In JavaScript, I can use a Map because it provides fast lookup and preserves insertion order. I’ll treat the first entry as LRU and the last as MRU. A successful get() or update moves the key to the end. When inserting a new key into a full cache, I remove the first key before inserting the new one.”

If the interviewer wants the classic implementation:

“I’ll use a hash map from key to linked-list node for O(1) lookup, and a doubly linked list to maintain LRU-to-MRU order. That gives O(1) lookup, removal, repositioning, and eviction.”

Interview Checklist

✓ get(existing) → value
✓ get(existing) → MRU
✓ get(missing) → undefined
✓ put(new) → insert
✓ put(existing) → update + MRU
✓ full + new → evict LRU
✓ capacity = 1
✓ undefined as a value
✓ O(1) expected get
✓ O(1) expected put
✓ O(capacity) space

LRU = Recently used stays. Least recently used gets evicted.