LRU Cache

Design a cache that evicts the least recently used item when full. It's one of the few problems that tests both data structure intuition and clean API design. Interviewers love it because it reveals whether you can combine a hash map with a linked list to get O(1) operations. This pattern shows up constantly in systems design.