Data Structure Patterns

Design problems ask you to combine two plain structures so their strengths cancel each other’s weaknesses.

Think design when you see:

• “Design a data structure supporting X, Y, Z in O(1)”
• Cache with an eviction policy
• Insert/delete/search/getRandom together
• Values keyed by (key, timestamp)

Quick Recognition Cheat Sheet

If you see…	Think…
Evict least recently used	Hashmap + doubly-linked list
Evict least frequently used	Hashmap + frequency buckets
insert + delete + getRandom all O(1)	Hashmap + dynamic array
Value changes over time (timestamps)	Key → sorted version list
Ordered operations (floor/ceiling)	Balanced BST / sorted map

Pattern Table

Pattern	Core Combo	Trick
LRU Cache	Map + linked list	Move-to-front on every touch
LFU Cache	Map + freq buckets	Track minFreq incrementally
RandomizedSet	Map + array	Swap-with-last delete
TimeMap	Map + append-only lists	Binary search timestamps

Mental Trigger

O(1) requirement + one weak operation = bolt a second structure onto the first.

Decision Guide

Need O(1) lookup?
        ↓
   Hashmap (always the anchor)

Also need ordering / recency / frequency?
        ├─ recency   → linked list nodes in the map
        ├─ frequency → bucket per frequency
        └─ ordered   → TreeMap / sorted container

Need uniform random?
        ↓
   Dense array + swap-delete