LiveCodingInterview.com
CodingMedium92% interview frequency · Last seen 2026-01

LRU Cache

MetaAmazonMicrosoft

Problem

Design and implement a data structure for a Least Recently Used (LRU) cache.


Implement the `LRUCache` class:

- `LRUCache(int capacity)` Initialize the LRU cache with positive size capacity.

- `int get(int key)` Return the value of the key if it exists, otherwise return -1.

- `void put(int key, int value)` Update the value if the key exists. Otherwise, add the key-value pair. If the number of keys exceeds capacity, evict the least recently used key.


Both get and put must run in O(1) average time complexity.

Common follow-ups

  • How would you make this thread-safe?
  • What if capacity is very large — any memory concerns?

Step-by-step study guide

Step 1: Clarify the operations

You need O(1) `get` and `put`. `get` should mark a key as recently used. `put` inserts or updates, then evicts the oldest key if size exceeds capacity.

Ask: Are keys and values integers only? Is capacity always positive? What to return when a key is missing?

Step 2: Trace examples

Capacity = 2:

  1. `put(1, 1)` → cache: {1=1}
  2. `put(2, 2)` → cache: {1=1, 2=2}
  3. `get(1)` → returns 1; key 1 is now most recent
  4. `put(3, 3)` → evict key 2 (LRU); cache: {1=1, 3=3}
  5. `get(2)` → returns -1

Step 3: Brute force

Store pairs in an array. On `get`, scan for the key O(n), move it to the end to mark recent O(n). On `put`, scan/update O(n), shift on eviction O(n). Total: O(n) per operation — too slow.

Step 4: Identify the pattern

You need two things at once:

  • O(1) lookup by key → hash map
  • O(1) reorder by recency → doubly linked list

The map stores key → list node. List order = usage order (head = most recent, tail = LRU).

Step 5: Design the optimized structure

Use dummy head and tail nodes to avoid null checks when splicing.

  • `get(key)`: if missing return -1. Otherwise move node to front (remove + insert at head), return value.
  • `put(key, value)`: if key exists, remove old node. Create node, insert at head, update map. If size > capacity, remove tail.prev node from list and map.

Step 6: Implement carefully

Helper methods `_remove(node)` and `_insert(node)` keep get/put readable. Always update both the list and the map on eviction.

Test: capacity 1 (every put evicts), repeated get on same key, update existing key without changing size.

Step 7: Complexity and follow-ups

  • Time: O(1) average for get and put (hash map + constant-time list splices)
  • Space: O(capacity)

Thread safety: wrap map + list in a lock, or use concurrent hash map with careful ordering.

Memory at scale: bounded by capacity; consider TTL or external store for very large caches.

Solution

# Solution locked
# Sign in to unlock expert solutions
# with multi-language code and analysis

Sign in to unlock

Create a free account to preview problems. Subscribe for full access to our curated bank — expert tutorials, follow-ups, and practice tools you won't find on public sites.