Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

LRU Cache

LeetCode #146Medium
Hash map + doubly linked list · O(1) get / put

Design a data structure for a Least-Recently-Used (LRU) cache with a fixed capacity. Support get(key) and put(key, value), both in O(1) average time. When the cache is full, evict the least-recently-used entry.

Asked atAmazonMicrosoftGoogleBloomberg
step 1 / 13
Hash map + doubly linked list
▸
1map: key → node;  DLL ordered newest → oldest
2get(key):
3    if key not in map: return -1     // MISS
4    node ← map[key]                  // O(1) lookup
5    moveToFront(node)                // splice + relink, O(1)
6    return node.value
7put(key, value):
8    if key in map:
9        node.value ← value; moveToFront(node)   // UPDATE
10    else:
11        if size == capacity: evict(tail)         // drop LRU, O(1)
12        insert new node at FRONT; map[key] ← node
state
  • map{}
  • opstart
  • capacity0/2

line 1DESIGN problem: build a cache where BOTH get and put are O(1), evicting the least-recently-used entry when full. The trick is to combine two structures — a hash map (key → node) for O(1) lookup, and a doubly linked list ordered most-recent → least-recent for O(1) move-to-front and O(1) eviction from the tail. The row below is the DLL: newest on the LEFT, oldest on the RIGHT. capacity = 2.