Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Composing Data Structures Into One System

5 min read

You'll learn to

-Match each structure in this tier to the question it answers best
-See why real systems combine several structures, with a small cache as the example
-Spot a design flaw in a composition: a FIFO order is not an LRU order

Across this tier you built a stack, a circular-buffer queue, a hashmap, a linked list, a rotated-array binary search, a memoized recursive function and a min-heap, plus a set of two-pointer and sliding-window array techniques. Each exists because it answers one question especially well. Real software rarely needs just one of those questions answered. It usually needs several at once, working together.

An Analogy: A Kitchen's Stations

A restaurant kitchen has stations: a grill, a salad bar, a pastry counter. Each is excellent at its job, and a real order uses several in sequence. Nobody tries to make every dish on the grill. Data structures are stations. A real program is a dish that needs more than one.

One Tier, One Data Structure Per Problem

-Stack: "what happened most recently?" LIFO (last in, first out) order, used for undo history, matching brackets and depth-first search.
-Queue (circular buffer): "what arrived first?" FIFO (first in, first out) order with O(1) at both ends, used for task scheduling and breadth-first search.
-HashMap: "does this exact key exist, and what is attached to it?" Average-case O(1) lookup through hashing and chaining.
-Linked List: "how do I insert or remove cheaply without shifting everything?" O(1) at the ends, at the cost of random access.
-Binary Search: "where is this, in sorted or rotated-sorted data?" O(log n) by halving the search space at each step.
-Recursion and Memoization: "how do I avoid recomputing the same subproblem?" Caching turns exponential branching into linear work.
-Heap: "what is currently smallest or largest, right now, as things change?" O(log n) insert and remove, O(1) peek.
-Two Pointers and Sliding Window: "can this be answered over a sorted array or a contiguous range without a nested loop?" O(n) instead of O(n²).

Why Real Systems Combine Them

An LRU (least-recently-used) cache is a favorite example because it needs two structures at once. A hashmap gives O(1) "does this key exist, and where". A linked list, specifically a doubly linked one, which is a small step past what was built in this tier, tracks access order so the least recently used entry can be evicted in O(1) too. Neither structure alone gets there, but together they do. A task scheduler might combine a heap (what is the next highest-priority job), a hashmap (look up a job's status by id) and a queue (a fair FIFO fallback for jobs sharing a priority). A rate limiter might combine a queue of recent request timestamps with the arithmetic from this tier's sliding-window chapter.

Press Run: two structures wired together, and a small design flaw that the run exposes

class SimpleFIFOCache:
    """A tiny cache: a HashMap for O(1) lookup, a Queue for FIFO eviction order."""

    def __init__(self, capacity):
        self._capacity = capacity
        self._store = {}      # HashMap piece: key -> value, O(1) lookup
        self._order = []       # Queue piece: tracks insertion order for eviction

    def get(self, key):
        return self._store.get(key)

    def put(self, key, value):
        if key not in self._store and len(self._store) >= self._capacity:
            oldest_key = self._order.pop(0)   # evict the first-in key
            del self._store[oldest_key]
        if key not in self._store:
            self._order.append(key)
        self._store[key] = value

cache = SimpleFIFOCache(2)
cache.put("a", 1)
cache.put("b", 2)
print("read a:", cache.get("a"), "(a was just used)")
cache.put("c", 3)                              # the cache is full: something must go
print("a still cached?", cache.get("a") is not None, "| b still cached?", cache.get("b") is not None)
print("this FIFO cache evicted the oldest INSERT, even though a was read a moment ago.")
print("an LRU cache would track USE, and would have evicted b instead.")

class SimpleFIFOCache:
    """A tiny cache: a HashMap for O(1) lookup, a Queue for FIFO eviction order."""

def __init__(self, capacity):
        self._capacity = capacity
        self._store = {}      # HashMap piece: key -> value, O(1) lookup
        self._order = []       # Queue piece: tracks insertion order for eviction

def get(self, key):
        return self._store.get(key)

def put(self, key, value):
        if key not in self._store and len(self._store) >= self._capacity:
            oldest_key = self._order.pop(0)   # evict the first-in key
            del self._store[oldest_key]
        if key not in self._store:
            self._order.append(key)
        self._store[key] = value

cache = SimpleFIFOCache(2)
cache.put("a", 1)
cache.put("b", 2)
print("read a:", cache.get("a"), "(a was just used)")
cache.put("c", 3)                              # the cache is full: something must go
print("a still cached?", cache.get("a") is not None, "| b still cached?", cache.get("b") is not None)
print("this FIFO cache evicted the oldest INSERT, even though a was read a moment ago.")
print("an LRU cache would track USE, and would have evicted b instead.")

The toy version's self._order.pop(0) is the same O(n) shift flagged back in the stacks-and-queues module. A production version would swap it for the circular buffer from that module, or more commonly a doubly linked list, to get true O(1) eviction. The run exposes a second, subtler point. This cache evicts the oldest insert, not the least recently used entry. Reading a did not protect it. The point is not the toy code, but the shape: identify what question the system really needs answered, then pick the structure from this tier built to answer it fast.

When a Forge Algorithm Lab level, or an interview prompt, feels like it needs "a bit of everything", that is usually a sign to decompose it. Write down the questions the system needs answered, then match each one to the structure from this tier built to answer it fast.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Ready to Build This?

The Tier 1 Boss, DataStructure Toolkit, is a composite challenge combining multiple data structures from this tier into one design, everything built this tier, stacks, queues, hashmaps, linked lists, binary search, memoized recursion, heaps, and two-pointer/sliding-window techniques, brought together.

Prefix Sums & In-Place Array Tricks From Hashing to LRU Caches

Discussion0

Join the Discussion

No comments yet. Be the first to start the thread!