How do you approach LRU Cache (Operations API)?

A hash map alone gets O(1) get/put but you can't find the LRU element in O(1).

What is the time complexity of LRU Cache (Operations API)?

Time complexity: O(1) per operation. Space complexity: O(capacity).

What are common mistakes on LRU Cache (Operations API)?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

Sitelet https://gitgood.dev/coding/lru-cache-ood

gitGood.dev

← Back to problems

LRU Cache (Operations API)

HardObject-Oriented Design

Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

The cache supports two operations:

get(key): Return the value of key if it exists, otherwise return -1.
put(key, value): Update the value of key if it exists. Otherwise, add the (key, value) pair to the cache. If inserting causes the cache to exceed its capacity, evict the least recently used key.

Both operations must run in O(1) average time.

For the auto-grader: implement a single function lruCacheOps(capacity, operations) that returns the result of each operation in order. Each operation is one of:

["put", key, value] → returns null (use null in JavaScript / None in Python).
["get", key] → returns the value or -1.

Example 1

Input: capacity = 2, operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]

Output: [null,null,1,null,-1,null,-1,3,4]

Explanation: After put(3,3) the LRU key 2 is evicted (cache is now {1,3}). put(4,4) evicts key 1 (cache becomes {3,4}). get(1) returns -1 (evicted), get(3) returns 3, get(4) returns 4.

Constraints

- 1 <= capacity <= 3000 - 0 <= key <= 10^4 - 0 <= value <= 10^5 - At most 2 * 10^5 calls will be made.

LRU Cache (Operations API): approach, complexity and pitfalls

A hard design problem, graded against 5 test cases (2 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

A hash map alone gets O(1) get/put but you can't find the LRU element in O(1).
Combine a hash map with a doubly linked list. The map points key → list node; the list maintains usage order.
On get/put-existing, move the node to the head. On insertion overflow, evict the tail node and remove its key from the map.

The optimal approach

Show the approach: Hash Map + Doubly Linked List

The hash map gives us O(1) lookup of the node for any key. The doubly linked list lets us reorder in O(1) - moving a node to the head when it's accessed, and detaching the tail when we evict.

Use sentinel head/tail nodes to avoid null edge cases. Helpers:

- `addToHead(node)` - splice between head and head.next

- `remove(node)` - splice node out

- `moveToHead(node)` = remove + addToHead

- `popTail()` - returns the node before `tail`, then removes it

Common pitfalls:

- Forgetting to update the map on eviction.

- Forgetting to overwrite the value (and move to head) on a `put` for an existing key.

- A singly linked list won't work - removing an arbitrary node by reference is O(n).

Time: O(1) per operation
Space: O(capacity)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.