LRU Cache

Design a Least Recently Used (LRU) cache with a fixed capacity:

LRUCache(capacity) — create the cache with the given positive capacity.
get(key) — return the value for key if present, else -1. A get counts as a use.
put(key, value) — insert or update key. If the cache exceeds its capacity, evict the least recently used key.

Both get and put must run in O(1) average time. (The first operation names the class and its capacity argument.)

Hints

· Stuck? Reveal one nudge at a time.

You need O(1) lookup and O(1) 'which key is least recently used' — one structure can't do both.

Combine a hash map (key -> node) with a doubly linked list ordered by recency.

Every access moves a node to the front; eviction removes the node at the back.

Common doubts

You must unlink an arbitrary node (the one the map points to) in O(1). Without a prev pointer you'd need to find its predecessor, which is O(n).

Just before the tail sentinel — every access moves nodes toward the head, so the oldest drifts to the tail.

They remove all the null-checks for the ends, so inserting at the front and removing at the back are uniform O(1) pointer updates.

Interview follow-ups

· What an interviewer asks next.

Yes — Java's LinkedHashMap, Python's OrderedDict, or JS's Map preserve insertion order and support move-to-end, giving a shorter O(1) LRU. The hash-map-plus-DLL version is what interviews expect you to build.

LFU evicts by lowest access frequency (breaking ties by recency), which needs frequency buckets on top of this structure.

Fun facts

LRU is the caching policy behind CPU caches, database buffer pools, and CDN edge caches.
The hash-map-plus-doubly-linked-list combo is the canonical 'two structures, two guarantees' design answer.

Asked at

AmazonGoogleMetaMicrosoftBloomberg

Frequently Sometimes Occasionally

Example 1

Input: capacity=2; put(1,1),put(2,2),get(1),put(3,3),get(2)
Output: 1, -1
get(1) returns 1; put(3,3) evicts key 2, so get(2) returns -1.

Example 2

Input: capacity=1; put(2,1),get(2),put(3,2),get(2)
Output: 1, -1
put(3,2) evicts key 2 (capacity 1), so the later get(2) returns -1.

Constraints

- 1 <= capacity <= 3000 - 0 <= key <= 10^4 - 0 <= value <= 10^5 - At most 2 * 10^5 calls to get and put

Two requirements pull in opposite directions: O(1) lookup by key (a hash map) and O(1) ordering by recency (so you can find and evict the least-recently-used item). Combine them: a hash map from key to node, and a doubly linked list ordering nodes from most- to least-recently used. Every access moves a node to the front; eviction removes the node at the back.

Prerequisites

Before you start

· Concepts used directly in the solution.

Hash map. O(1) lookup of a key's node.

Doubly linked list. O(1) removal and front-insertion given a node pointer, and O(1) access to the tail (LRU).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The policy

“Does get count as a use?”

Yes — a successful get makes that key the most recently used.

“When does eviction happen?”

On a put that would exceed capacity — evict the least recently used key first.

The ideal opening — say it like this

I need O(1) lookup and O(1) recency updates, so I pair a hash map with a doubly linked list.

The map points key to its list node; the list orders nodes most- to least-recently used.

Every get or put moves the node to the front; a put over capacity removes the node at the back.

Understand the problem

Worked example — capacity = 2: put(1,1), put(2,2), get(1), put(3,3), get(2)

put(1,1) -> {1}                         (null)
put(2,2) -> {2, 1}                       (null)
get(1)   -> 1; move 1 to front -> {1, 2}
put(3,3) -> over capacity, evict 2 -> {3, 1}   (null)
get(2)   -> -1  (2 was evicted)

Key observations

1Aha

Two structures, two guarantees

The hash map gives O(1) lookup; the doubly linked list gives O(1) recency reordering and O(1) access to the LRU node at the tail.

2Aha

Every access moves a node to the front

get and a put on an existing key both mark it most-recently used by unlinking and re-inserting at the front.

3Aha

Evict from the tail

When capacity is exceeded, the node just before the tail sentinel is the least-recently used; remove it from the list and the map.

Summary

Key takeaway

Hash map (key -> node) plus a doubly linked list (most- to least-recently used). get/put unlink the touched node and re-insert it at the front; a put over capacity evicts the node before the tail. Sentinels make every pointer operation O(1).

get(key):  if absent return -1; move node to front; return value
put(k,v):  if present update + move to front
           else add node at front + map; if size > cap: remove tail.prev from list and map