Compile Ready
Module 14 · Machine Coding

Build: LRU Cache

Intermediate12m read35m practice47m total
Machine CodingCacheMapData Structures

Introduction

An LRU cache evicts the least recently used entry when capacity is exceeded. In JavaScript, Map preserves insertion order, which lets us implement get and put in O(1) average time by deleting and reinserting keys to refresh recency.

This is a popular machine-coding problem because it combines API design, edge cases, and data-structure reasoning.

Why This Matters

Caching is used in API clients, image loaders, memoization utilities, data grids, and backend services. Interviewers ask LRU because the naive array solution is easy but not optimal; a Map-based or doubly-linked-list solution demonstrates awareness of O(1) recency updates.

Theory

Map-based recency

A JavaScript Map iterates keys in insertion order. Treat the first key as least recently used and the last key as most recently used. On get(key), delete and reinsert the entry so it becomes most recent. On put(key, value), do the same, then evict the first key if size exceeds capacity.

API decisions

Common interview APIs are get(key) returning value or -1, and put(key, value) returning nothing. Production APIs may prefer undefined, has, or explicit result objects to avoid ambiguity when cached values can be -1.

Alternative design

In languages without ordered maps, use a hash map from key to linked-list node plus a doubly linked list ordered by recency. JavaScript's Map gives us that order directly for interview-scale implementations.

Visual Diagrams

LRU order in a Map
least recent                         most recent
    |                                      |
    v                                      v
  key A  ->  key B  ->  key C

get(A): delete A, insert A

least recent                         most recent
    |                                      |
    v                                      v
  key B  ->  key C  ->  key A

Refreshing recency is delete plus set.

Code Examples

Complete Map-based LRU cache

This implementation keeps all operations O(1) on average using Map insertion order.

Loading…

Playground

Loading editor…
Console

Press Run to execute the code and see output here.

Output Prediction

Predict the output #1

javascript
1function LRUCache(capacity) {
2  this.capacity = capacity;
3  this.cache = new Map();
4}
5 
6LRUCache.prototype.get = function (key) {
7  if (!this.cache.has(key)) {
8    return -1;
9  }
10 
11  var value = this.cache.get(key);
12  this.cache.delete(key);
13  this.cache.set(key, value);
14  return value;
15};
16 
17LRUCache.prototype.put = function (key, value) {
18  if (this.cache.has(key)) {
19    this.cache.delete(key);
20  }
21 
22  this.cache.set(key, value);
23 
24  if (this.cache.size > this.capacity) {
25    this.cache.delete(this.cache.keys().next().value);
26  }
27};
28 
29var cache = new LRUCache(2);
30cache.put('a', 1);
31cache.put('b', 2);
32console.log(cache.get('a'));
33cache.put('c', 3);
34console.log(cache.get('b'));

Coding Exercises

Implement an O(1) LRU cache

Medium

Implement LRUCache(capacity).

Requirements:

  • capacity must be a positive integer.
  • get(key) returns the value if present, otherwise -1.
  • get marks the key as most recently used.
  • put(key, value) inserts or updates a value.
  • put marks the key as most recently used.
  • If capacity is exceeded, evict the least recently used key.
  • Add optional helpers has, size, and keysLeastToMostRecent.

Constraints:

  • Use JavaScript Map insertion order.
  • get and put should be O(1) average time.

Interview Questions

1How would you implement LRU in a language without ordered maps?

Use a hash map from key to doubly-linked-list node. The list stores recency order. get and put move nodes to the tail in O(1), and eviction removes the head in O(1).

Asked at:AmazonGoogleMicrosoft

Follow-ups

  • How would you make it thread-safe?
  • How would you add TTL expiration?
2Why does updating an existing key delete first?

Setting an existing key in a Map updates its value but does not move it to the end. Deleting then setting refreshes insertion order so the key becomes most recent.

Quiz

1. After `get(key)` succeeds in an LRU cache, what should happen to that key?

Summary

  • An LRU cache evicts the least recently used entry on overflow.
  • JavaScript `Map` preserves insertion order, enabling a compact O(1) average implementation.
  • Refresh recency with delete plus set.
  • The first Map key is the eviction candidate.

Cheat Sheet

LRU checklist

  • Validate positive capacity.
  • Data: Map from key to value.
  • Most recent = last inserted.
  • get: missing -> -1; hit -> delete, set, return value.
  • put: delete existing, set new value.
  • Overflow: delete map.keys().next().value.
  • Complexity: O(1) average time, O(capacity) space.