Design an LRU Cache

Medium·Tagsllddesignlrucachehashmapdoubly-linked-list

Problem Statement

Design a Least-Recently-Used (LRU) cache with O(1) get and put. Both operations must run in constant time regardless of cache size. API contract ```java class LRUCache { public LRUCache(int capacity); // capacity > 0; throws otherwise /** Return the value associated with key, or -1 if absent. * A successful get marks the key as most-recently-used. */ public int get(int key); /** Insert or update key→value. * - If the key exists, update the value and mark as most-recently-used. * - If the cache is at capacity and the key is new, evict the LEAST-recently-used * entry, then insert. */ public void put(int key, int value); public int size(); } ``` *Recency rule* Every `get` and every `put` (insert or update) marks that key as most-recently-used. The eviction victim is whichever key has gone the longest without being touched by either operation. The validator runs three checks: 1. *basic_get_put_and_miss* — put `(1,10)` and `(2,20)` into a capacity-2 cache; `get(1) == 10`, `get(2) == 20`, `get(3) == -1`, `size() == 2`. 2. *eviction_on_capacity* — capacity 2. After `put(1,1)`, `put(2,2)`, `put(3,3)`: key 1 (the LRU) is evicted; `get(1) == -1`, `get(2) == 2`, `get(3) == 3`, `size() == 2`. 3. *recency_updates_on_get_and_put* — capacity 2. After `put(1,1)`, `put(2,2)`, `get(1)` (now 2 is LRU), `put(3,3)`: key 2 is evicted, not key 1. Updating an existing key (`put(1, 99)`) also marks it as MRU and does not change size. The stub class throws `UnsupportedOperationException` from every method, so it fails every check until you implement it. Starter code and validators are available in Java, Python, and C++.

Examples

Example 1

Input

var c = new LRUCache(2); c.put(1,10); c.put(2,20); c.get(1)

Output

"10"

Why

Hit. Key 1 becomes the most recently used; key 2 is now the LRU.

Example 2

Input

c.put(3,30); c.get(2)

Output

"-1"

Why

Capacity is 2; key 2 was the LRU before the put, so it gets evicted.

Example 3

Input

c.put(1, 99); c.get(1)

Output

"99"

Why

Updating an existing key replaces the value and refreshes its recency. Size does not change.

Constraints

•Capacity > 0; throws IllegalArgumentException otherwise.
•get(key) returns -1 for absent keys.
•Both get and put run in O(1).
•Both get and put mark the key as most-recently-used.
•When the cache is full and a new key is inserted, evict the least-recently-used key first.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

Use a HashMap<Integer, Node> + a doubly-linked list of Nodes. The map gives O(1) lookup; the list maintains recency order. Head = MRU, tail = LRU.

Hint 2

Sentinel head and tail nodes (both always present) simplify boundary handling — every real node has a non-null prev and next.

Hint 3

Helper methods: removeNode(node) (unlinks from current position) and addToHead(node) (inserts right after head sentinel). Both are O(1).

Hint 4

get(key): if the map contains the key, removeNode + addToHead, return value. Otherwise return -1.

Hint 5

put(key, value): if the key exists, update the node's value and move it to the head. If new and at capacity, evict the tail.prev node (the LRU) — remove from both list and map — then insert at head. If new and under capacity, just insert at head.

Hint 6

size() returns map.size(). The list and map stay in sync because every add/remove touches both.