Designing data structures
Overview
The process of combining primitive data structures (like arrays, hash maps, and linked lists) into a composite structure to achieve specific time complexity goals for various operations.
No single built-in data structure is perfectly fast at everything. To build a system that can quickly insert, delete, and fetch the minimum element, you must weave multiple structures together.
Where used: LRU Caches (Hash Map + Doubly Linked List), Rate Limiters, Task Schedulers
Why learn this
- It tests your deep understanding of the tradeoffs of every primitive structure.
- 'Design X' is one of the most common formats for senior-level coding interviews.
- It mirrors real-world object-oriented class design.
Common mistakes
- Ignoring state synchronization: When using two structures (e.g., a Hash Map and an Array), inserting or deleting an item must update BOTH structures. Forgetting to keep them perfectly in sync leads to dangling pointers or ghost data.
- Not starting from the constraints: If a problem asks for O(1) retrieval, you almost certainly need a Hash Map. If it asks for O(1) removal of the oldest item, you need a Queue or Linked List. Not mapping constraints to primitives first is a planning failure.
Recall questions
- If you need O(1) lookups and O(1) deletion from the middle of a sequence, what composite structure should you use?
- Why is an array poor for O(1) arbitrary deletion, and how can a Hash Map help if order doesn't matter?
Understanding checks
You need a data structure that supports `insert(val)`, `remove(val)`, and `getRandom()` all in O(1) average time. Which composition of structures should you use?
A Hash Map and an Array (Dynamic Array / List).
`getRandom()` in O(1) requires an Array for contiguous indexing. `insert` and `remove` in O(1) require a Hash Map to find elements in the array to swap-and-pop.
In an LRU Cache made of a Hash Map and Doubly Linked List, what happens to the Linked List when an existing key is accessed?
The node representing that key is unlinked from its current position and moved to the 'most recently used' end (usually the head or tail, depending on convention).
Accessing an item refreshes its status, pushing it as far away from eviction as possible.
Practice tasks
Design LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Continue learning
Previous: Hash Tables
Previous: Queue & deque