Pattern Recognition Drill

#138 — LRU Cache

Medium Linked Lists

The Problem

Design a data structure for Least Recently Used cache with O(1) get and put.

What approach would you use?

Think about it before scrolling down.

Key Signals

'O(1) get and put' → hash map for lookup
'Least recently used eviction' → need ordering → doubly linked list for O(1) removal/insertion

Hash Map

OrderedDict or HashMap + doubly linked list. Get moves to end. Put evicts front if over capacity. O(1).

Common Trap

A regular dict doesn't track access order. You need either OrderedDict or a manual DLL + HashMap.

← #137