Design a cache with fixed capacity supporting get(key) and put(key,value), both in O(1). When full, evict the least-recently-used entry. Any get or put counts as a use.
Composing two structures so that both lookup and recency-reordering are O(1) — the canonical 'design' interview.
No single structure gives you both O(1) lookup and O(1) 'move to most-recent'. The standard answer composes two: a hash map from key → node for O(1) find, and a doubly linked list holding nodes in usage order (most-recent at the head, least-recent at the tail). On get: look up the node, unlink it, splice it to the head, return its value. On put: if the key exists, update and move to head; otherwise create a node at the head and, if over capacity, drop the tail node and delete its key from the map. The doubly linked list is essential — you need O(1) removal of an arbitrary node, which a singly linked list can't do without the predecessor. A dummy head and dummy tail sentinel remove all the null-edge bookkeeping. In JS you can cheat with a `Map`, which preserves insertion order: delete-then-set moves a key to the end, and `map.keys().next().value` is the oldest — but interviewers usually want the explicit map+DLL to prove you understand why. LFU is the harder cousin (frequency buckets).
Need O(1) lookup AND O(1) ordering/recency updates → hash map for find + doubly linked list for order.
Time O(1) get/put · Space O(capacity)