Implement LRU Cache

Implementing a templated O(1) LRU cache in C++

This is a medium-difficulty coding problem that tests your ability to combine multiple data structures to achieve constant-time performance on all operations. LRU caches are fundamental to systems programming—used in CPU caches, database buffers, and web proxies—and quant firms value candidates who can implement them cleanly under pressure.

The core challenge is tracking both access order (which item was used most recently) and key-to-value mapping with no operation exceeding O(1) average time. This requires thoughtful pairing of a hash map for fast lookup with a linked list for efficient reordering. The subtle part: distinguishing between operations that affect recency (retrieval and insertion) and those that do not (membership checks), while handling eviction correctly when capacity is reached.

• Hash map and doubly-linked list composition
• Iterator invalidation and safe node movement
• Eviction policy and edge cases (update vs. insert, full cache)
• Templating for type-generic key and value