LRU Cache (LC 146) + Multithreading Variant

The single most repeated Microsoft coding prompt. O(1) get/put bounded cache, with frequent follow-ups on thread safety and LFU variants. Requirements Implement an LRUCache(capacity) with O(1) get(key) and put(key, value). On eviction, drop the least-recently-used entry. get counts as a use. Reported follow-ups, in order of frequency: Strict O(1). Multiple interviewers explicitly reject OrderedDict.move_to_end based solutions on the grounds that internal reordering is O(log N) under Python's hash table assumption; the expected answer is hashmap + doubly-linked-list. Thread safety (MAI variant). Multiple concurrent get / put callers; protect with a single RLock or with reader-writer locks if performance is probed. LFU (one VO round): same shape as LRU but evict the least-frequently-used; on frequency ties, fall back to LRU. Notes The canonical hashmap + doubly-linked-list pattern: Dict maps key → Node. Doubly-linked list ordered MRU → LRU. Head sentinel for MRU, tail sentinel for LRU. get(key): O(1) lookup, splice node to head. put(key, value): insert at head; if over capacity, unlink tail.prev and pop from dict. Use sentinel nodes at both ends to make every splice a four-pointer reassignment with no special cases. For thread safety, the simplest correct answer is a single threading.RLock wrapping every public method. Interviewers who push on this expect you to acknowledge the contention cost and discuss sharding the cache (split into N independent shards by hash(key) % N, each with its own lock) — the same pattern as ConcurrentHashMap. LFU is LRU + a freq → DLL index: each get / put bumps the node from its current frequency bucket into the next; eviction targets the LRU node within the lowest-frequency bucket. Track the minimum frequency to find the eviction bucket in O(1). Preparation Write the LRU skeleton from scratch under 12 minutes; type the sentinel-node pattern until it is automatic. Drill the four splice operations (unlink, push-to-head, unlink-tail, pop-from-dict) on paper. Pre-rehearse the thread-safety extension: "wrap with RLock for correctness; shard for throughput". For LFU, write it once end-to-end the night before; the bucket bookkeeping is the part candidates lose time on.