← Back to the hash tables page
HashMap + Structure Combos
The interview power move: bolt a hashmap onto another structure to make every operation O(1). LRU cache is the canonical example.
What to know
- LRU = hashmap → DLL nodes; recency order lives in the list, lookup in the map.
- RandomizedSet = hashmap (value → index) + array (swap-with-last delete).
- LFU adds a second map from frequency → DLL of keys.
In the wild: Redis eviction policies, CDN caches, database buffer pools.
Algorithms to reach for
LRU cache
O(1)O(1) get/put with least-recently-used eviction
Insert/Delete/GetRandom O(1)
O(1)Set with uniform random sampling (LeetCode 380)
LFU cache
O(1)Evict by frequency then recency (LeetCode 460)
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.