Implement get(key) and put(key, value) for a least-recently-used cache. A successful get and every put make that key the most recently used. When capacity is exceeded, evict the least recently used key.
Use a hash map from keys to list nodes and a doubly linked list ordered from least to most recently used. Define sentinel nodes or explicit head/tail cases, and write one helper that unlinks and one that inserts a node. The target is O(1) expected time per operation.
Test updating an existing key, reading the current least-recent item, capacity one, and repeated eviction. Explain why a hash map alone cannot identify the least-recent item efficiently.