Data Structure Design

Composing maps, heaps, queues, and linked lists into custom structures under performance constraints, LRU caches, time-based key-value stores.

12 min readUpdated 2026-08-06

Data structure design tests whether you can compose primitives — maps, heaps, queues, linked lists — into custom structures that satisfy specific performance constraints: LRU caches, time-based key-value stores, leaderboards, that sort of thing.

What it solves

Problems where a stock data structure alone can't meet the constraints, so you compose several. The signature is almost always explicit performance requirements: "get and put both in O(1)", "retrieve by time", "top-k by score", "recent items first".

Recognition signals

Explicit complexity targets: "O(1) for both operations", "O(log n) worst case"
"Cache", "evict", "least recently used", "expiring keys", "top k", "most recent"
A key-value store with ordering behavior layered on top
"Design a … that supports … and …"

The approach

The classic moves:

Requirement	Composition
LRU eviction	Hash map (key → node) + doubly linked list (recency order). O(1) lookup, O(1) move-to-front, O(1) evict-tail
Time-based keys	Sorted structure by timestamp (heap or sorted list) + map for lookup; sweep expired lazily
Top-k by score	Heap of size k, or a sorted structure with rank queries
Frequency / recency	Frequency-of-use + per-frequency buckets

The design decision is which primitive pays for which requirement. For an LRU cache: the map pays for get O(1), the list pays for "which to evict" O(1). If you only use a map, eviction becomes O(n) — the classic failure.

What to tell the AI

Decide the composition and the public API, then direct:

Prompt — good

Implement an LRUCache class: a capacity constructor, get(key) and put(key, value), both O(1). Use a Map from key to doubly-linked-list node plus a head/tail sentinel list. On get, move the node to the tail. On put of a new key at capacity, evict the head's next node. No built-in ordering tricks.

You specify the composition and the operations; the AI implements it.

What to verify

The O(1) claims — watch for a hidden O(n): scanning for eviction, indexOf on a list, rebuilding a map. Verify with an n=100k test if you can.
Node management — updating the map pointer when a node is touched; stale pointers after eviction.
Edge cases — capacity 0/1, put existing key (should update value and recency), get of missing key.
Sentinel correctness — off-by-one with head/tail sentinels breaks both insertion and eviction.
API surface — did the AI add public methods that leak internals? You defined the interface; keep it clean.
Thread-safety claims — if the AI mentions locking it didn't add, call it out.

Worked micro-example

LRUCache(2). put(1,1), put(2,2) → order [1,2]. get(1) → moves 1 to tail → [2,1]. put(3,3) → at capacity, evict head (2) → [1,3]. get(2) → -1. That move-to-front on every get is exactly what the doubly linked list enables in O(1).

Practice problems

Try these: LRU Cache (the canonical composition), LinkLock (shortener with expiry and analytics), Battleship (board state with fast lookups), Card Game (deck + hand structure), Word Container (trie-backed word storage).

Quick check · Why does an LRU cache need a linked list at all — can't a map alone track recency?

Premium

Unlock the rest of this guide

Premium unlocks every pattern deep-dive, every problem breakdown and solution, the practice sandbox, and verdict feedback on your practice runs.

These problems grade your API design and complexity reasoning as much as the code.
LRU cache = hash map + doubly linked list; the map gives O(1) lookup, the list gives O(1) eviction order.
Define the public interface yourself and have the AI implement it.
Verify amortized guarantees — the AI often slides in an O(n) operation.

The full article, complete and uninterrupted
All pattern deep-dives and problem breakdowns
Practice sandbox and verdict feedback