gamesblog

Data structures by hand

Push, pop, insert, probe: trace a stack, a queue, a search tree, a heap and a hash table by hand, and say what comes out or what the array holds.

  • Computing
  • Untimed
  • Endless levels

How it plays

A list of operations on a structure that starts empty. Say what comes out of a stack or a queue and in what order, what is on top, how a binary search tree lists its keys, what a min-heap's array looks like, or which slot a key lands in.

Levels go from stacks and queues to search trees (preorder, in-order, postorder, height) and heaps, then to popping a heap, hashing with collisions, and deleting a node with two children. The sequences grow longer as you climb.

Every answer is what the operations actually produce, run by minimal textbook versions of each structure; the prompt states the conventions (0-indexed heap, +1 probing, successor on delete). The wrong options are the same operations run with a real slip: a queue read as a stack, one sift step, the home slot taken as final.

Keys

Space starts and skips ahead · 1–9 pick · Enter submits · Esc stops. On a phone, tap.

What it trains

This makes tracing these data structures by hand quicker and surer. It claims nothing wider.

Learn

How to get better at data structures by hand: the method, the techniques, what each new level asks of you, and the traps the wrong answers are made of.

Your approach to each question

  1. Read the structure’s name and the conventions in the prompt before the operations: stack or queue, smaller keys left, 0-indexed heap, +1 probing, successor on delete. The conventions decide the answer as much as the keys do.
  2. Keep a written state, not a remembered one. Note the stack’s contents, sketch the tree, or write the array after every operation — a scrap of paper is part of the method.
  3. Look for the shortcut the structure allows before tracing every step: a queue’s output and a search tree’s in-order listing can be read straight off the input.
  4. Check your answer against the structure’s rule: the in-order of a search tree is sorted, every heap parent is no larger than its children, every probed key sits at or after its home slot, counting round the wrap.

Techniques and tricks

  • A queue gives back its input

    Dequeues come out in exactly the order things were enqueued. If there are k dequeues, the output is the first k keys enqueued, in order, and the front now is the next one after them.

    e.g. enqueue 4, 7 · dequeue · enqueue 2, 9 · dequeue · dequeue → out 4, 7, 2; front 9

  • Match each pop to the latest push

    For a stack, read left to right and pair every pop with the most recent push not yet paired, like matching brackets. The top now is the last push left unpaired.

    e.g. push 4, 7 · pop · push 2, 9 · pop · pop → out 7, 9, 2; top 4

  • In-order of a search tree is sorted

    However the keys were inserted, the in-order listing of a binary search tree is the keys from smallest to largest. You do not need to build the tree to answer it.

  • Root first, root last

    The first key inserted is the root. Preorder starts with it, postorder ends with it. That single fact rules out most wrong listings at once.

    e.g. insert 50, 30, 70, 20, 40, 60, 80: preorder 50, 30, 20, 40, 70, 60, 80; postorder 20, 40, 30, 60, 80, 70, 50

  • Heap insert: append, then climb

    Put the new key at the end of the array. While its parent, at index ⌊(i − 1) / 2⌋, is larger, swap them. Keep swapping all the way up — not just once.

    e.g. insert 5, 3, 8, 1: [5] → [3, 5] → [3, 5, 8] → [3, 5, 8, 1] → [3, 1, 8, 5] → [1, 3, 8, 5]

  • Heap pop: last to the root, then sink

    Remove the root, move the last element into its place, and swap it down with the smaller of its children (at 2i + 1 and 2i + 2) until both are larger.

    e.g. [1, 3, 8, 5] → 5 to the root: [5, 3, 8] → swap with 3: [3, 5, 8]

  • Hashing: home, then the next free slot

    Work out key mod m for every key first. Then place them in insertion order, each at its home slot or, if that is taken, the next free one, wrapping from the end to slot 0.

    e.g. 7 slots, insert 17, 24, 31, 9: homes 3, 3, 3, 2 → 17 in 3, 24 in 4, 31 in 5, 9 in 2

As the levels climb

  • The kinds unlock in this order: stacks and queues; then search trees (preorder, in-order, postorder or height) and building a min-heap; then popping a heap and hashing with linear probing; then deleting a node with two children. Four in ten questions come from the newest kind.
  • The sequences grow longer as you climb — more pushes and pops, more keys in a tree or a heap. Past a dozen operations, stop holding the state in your head and write it down after every step.
  • At the delete tier, the successor is the smallest key in the right subtree: step right once, then left as far as you can. It takes the deleted key’s place, and is removed from where it was.
  • Each step of size also adds 8% to the time, up to twelve steps, so the clock grows with the work rather than squeezing you.

Traps to avoid

  • A queue read as a stack, or a stack as a queue: the two wrong orders are always on offer. Say “first in, first out” or “last in, first out” before you start, and use the matching trick.
  • Preorder and postorder swapped: preorder puts the root first, postorder puts it last. Check where the first inserted key sits in the option.
  • One sift step: a new heap key swapped with its parent once and left there. Keep climbing until the parent is smaller or you reach the root; a pop sinks all the way down the same way.
  • Shifting the heap left on a pop: removing the root and closing the gap breaks every parent and child position. The last element goes to the root, then sinks.
  • The home slot taken as final: a key whose home is full moves on, and so may every key after it. Fill the table in order — a later key can be pushed on by an earlier one’s probing.

How to practise

  • In “Kinds of question”, drill “Min-heaps” and “Popping a heap” together until the sift-up and sift-down are automatic; they are the slowest steps by hand.
  • Switch “Answer by” to “Typing the answer” for heights, tops and hash slots; listings and arrays stay as options.
  • Raise “Options shown” towards 8 so the reversed order, the swapped traversal and the one-step sift sit side by side, and you must tell them apart rather than spot the outlier.
  • Read the working after a miss: it gives the state after each step, so you can find the exact operation where your trace went wrong.

Levels

It is untimed unless you turn the clock on. There is no last level: at least one dial turns without end. Your level is judged on your last ten answers, every ten: 90% moves you up, below 80% moves you down, which holds most people near four in five right.

All of it is in the settings beside Start — how many answers a judgement looks at and how often it recalibrates, the thresholds, the time, which questions, how many options, and whether you see each verdict at once or review them together at the judgement. You can also jump to any level.

More computing

All games →