Advanced Data Structures

Every other article here is about an algorithm you apply to data you were given. This one is the opposite: the input is a specification — these operations, at these speeds — and the answer is a structure you assemble.

Two things live in this category. One genuinely new structure, the trie. And the design skill that the rest of these problems test, which is combining structures you already know so that each one covers the other’s weakness.

Tries#

A trie stores strings by their shared prefixes. Each edge is a character, each node is the prefix spelled by the path from the root, and words that begin alike share that path until they diverge.

node = { children: map from character to node, is_word: false }

function insert(word):
    cur = root
    for ch in word:
        if ch not in cur.children:
            cur.children[ch] = new node
        cur = cur.children[ch]
    cur.is_word = true          // the flag, not the node, is what marks a word

function search(word):
    cur = walk down from root following word's characters
    return cur exists and cur.is_word

function starts_with(prefix):
    return walking down from root following prefix's characters succeeds

The is_word flag is the detail that matters. Inserting "apple" creates a node for "app" along the way, so without the flag, search("app") would return true for a word that was never inserted. search checks the flag; starts_with only checks that the path exists — and that one-line difference is the entire distinction between the two operations.

The interactive trie snippet builds insert and search in Go, line by line, with a fixed 26-slot array instead of a map.

What it is actually for#

Insert and search both cost O(L) in the length of the word, independent of how many words are stored. That sounds like the pitch, but a hash set gives you the same O(L) — hashing a string reads all of it too. So:

A trie is not a faster hash set. It is the structure that answers prefix questions, which a hash set cannot answer at all.

Autocomplete, startsWith, “does any stored word match this pattern”, counting words with a given prefix — those need the tree. Exact membership does not, and reaching for a trie when a set would do is a real over-engineering trap.

Word Break is the useful middle case: the dictionary can live in a trie so that, walking forward from position i, you find every word that starts there in one descent — instead of testing every candidate substring against the whole dictionary. The DP around it is unchanged; the trie only makes the inner lookup cheap.

On memory: a fixed array of 26 child pointers per node is fast and wasteful, since most nodes use two or three of them. A map per node is denser and slightly slower. Either way the total is O(total characters inserted), which is the honest number to quote.

Composite design#

The rest of this category is one skill. The problem names some operations and a target complexity, and no single structure hits all of them — so you use two, and pay a little on every write to keep them in step.

The method is three questions, in order:

1. What operations are required, and how fast must each be? Write them down. This is the step people skip, and it is the one that makes the answer obvious.
2. Which structure gives each operation on its own? Usually a hash map for “find it without scanning” and something ordered for “know what comes next”.
3. What does it cost to keep them consistent? If that cost is O(1) per write, the design works.

LRU Cache#

The specification is get and put, both O(1), evicting the least recently used entry when full. Neither half of that is hard alone, and neither structure can do both.

• A hash map finds any key instantly, but has no idea which entry was used longest ago.
• A list keeps the usage order, but finding a particular entry means scanning it.

So use both, pointing at the same nodes.

Follow the two rows together. The map never reorders anything and the list is never searched; each does the one thing it is good at, and every operation touches both. Eviction is free because the answer to “which is least recently used” has been sitting at the back of the list the whole time — nothing has to be computed when the moment arrives.

Two implementation details decide whether this actually works:

• The list must be doubly linked. To unlink a node in O(1) you need its predecessor, and a singly linked list will only give you that by walking from the head — which puts the scan straight back in. See linked lists for why the previous pointer is never free.
• Use dummy head and tail nodes. Every insert and removal then has a real node on both sides, so there are no null checks and no special case for the first or last entry. The same trick, for the same reason, as the dummy head when building a list.

Most languages also ship this: Python’s OrderedDict with move_to_end, or Java’s LinkedHashMap with access order. Say that you know — then build it by hand, because that is what is being asked.

The other composites#

Once you have seen the move, the rest of the category is recognisable:

• Min Stack — report the minimum in O(1). You cannot recompute it on demand, so store it alongside: each entry carries the minimum of everything at or below it. Popping restores the previous minimum for free, because it was never overwritten. Covered in stacks.
• Implement Queue using Stacks — an in-stack takes pushes, an out-stack serves pops, and the in-stack is tipped into the out-stack only when the out-stack empties. Each element moves at most once, so the cost is O(1) amortised despite the occasional expensive transfer.
• Find Median from Data Stream — two heaps facing each other, so the median is always sitting at one or both of their roots.
• Time Based Key-Value Store — a map from key to a list of (timestamp, value). Because timestamps arrive in increasing order, each list is already sorted, so get is a binary search for the largest timestamp at or below the query. Map for the key, ordering for the time: the same shape as the LRU cache.

Serialisation is a design problem too#

Serialize and Deserialize Binary Tree fits here for a different reason: there is no clever structure, but the format you choose is the answer.

Pre-order DFS with an explicit marker for every null child is the standard choice, and the reason is worth understanding. The markers make the string unambiguous — you no longer need a second traversal to disambiguate shape, which is why in-order alone cannot work. And because pre-order emits a node before its children, deserialisation is a single pass that consumes tokens in exactly the order it needs them, rebuilding the tree with the same recursion that wrote it.

The bug to avoid is a delimiter that can appear inside a value. Negative numbers and multi-digit values need a separator that is not a minus sign or a digit.

The recurring moves#

Across all of these, four ideas keep reappearing:

• Precompute at write time what a read needs. Min Stack carries the minimum; the LRU list carries the order. Both make an O(n) read into an O(1) one by doing a constant amount of extra work on every write.
• Pair a map with something ordered. The map answers where is it, the ordered structure answers what comes next. LRU and Time Based KV are the same design with a different ordering.
• Use sentinels to delete special cases. Dummy head and tail nodes, explicit null markers in a serialised string — both replace a branch with a value.
• Amortise. A rare expensive operation is fine if it pays for many cheap ones. Two-stack queues and dynamic arrays both rely on it, and saying “O(1) amortised” precisely is worth more than claiming plain O(1).

Talking through the design#

These are interview problems about communication as much as code, and the order in which you say things matters more here than anywhere else:

1. State the operations and the target complexity back to the interviewer.
2. Say why one structure is not enough — name the operation it cannot do.
3. Propose the pair, and say which operation each half handles.
4. Then work out the invariant that keeps them consistent, and only then write code.

Getting to step 3 out loud is most of the mark. Starting to type before step 1 is how people end up with a design that cannot meet the requirement they were given.

Recognising it#

You are in this category when:

• The problem says “design”, “implement”, or “class” rather than describing an input and an output.
• A complexity target is stated in the problem — “each operation in O(1)”, “better than O(n) per query”. That number is the specification, and it is telling you which structures are allowed.
• Two required operations pull in opposite directions — fast lookup versus maintained order is the classic pair.
• The input is a set of strings sharing prefixes, and the query is about prefixes rather than whole words. That is a trie.

Summary#

The trie is one structure worth learning properly, and worth using only when the question is about prefixes — otherwise a set is smaller and simpler. Everything else in this category is composition: read the required operations, notice that no single structure gives all of them, and pair a map with whatever maintains the order you need. Then do the small amount of extra work on every write that keeps the two halves agreeing, and the reads come out free.