rust / LEVEL 4
THEORY / RETRIEVAL
LRU means least recently used, not least recently inserted. A successful get, an update and a new insertion all move that key to the most-recent end. A miss changes nothing. Forgetting the read transition produces a cache that looks correct until a hot old key competes with a newer cold key.
A HashMap maps each key to a stable slot in average O(1) time. The slots form a doubly linked recency list through Option<usize> handles, so detach, promote and tail eviction touch only neighboring nodes. Scanning a Vec or VecDeque on every hit keeps ordering simple but makes a hot-path get O(n).
The map and node arena each own a key, so one explicit String clone is part of this API design. Nodes never move out of their slots; a full cache detaches the tail, removes its old map key, replaces the node payload and reattaches the same slot at the head. Bounds and aliasing remain compiler-checked without raw pointers.
CHECKPOINT
Select every applicable option. Credit requires an exact set match.
02 / IMPLEMENTATION
Complete LruCache with average O(1) get and put. Successful get, update and insertion become most recent; misses do not change order. A full insertion returns the evicted key/value, updates never evict, and len never exceeds capacity. Keep the public API, use no unsafe code and do not linearly scan entries.
Runner is waiting for a submission.