LRU Cache Solution

Implement the complete LRU cache with $O(1)$ operations.

Implementation checklist:

• Initialize dummy head and tail, link them together
• Hash map stores key → node pointers
• Each node stores key, value, prev, next
• get: lookup, move to front if found
• put: handle update vs. insert, check capacity

Common bugs:

• Forgetting to store the key in the node (needed for eviction)
• Not linking head and tail in constructor
• Off-by-one in capacity check

This problem appears constantly in interviews because it tests both data structure knowledge and implementation skill.

Time: $O(1)$. Space: $O(n)$.