Stateful Systems

What is this?

Give someone the wrong structure and a simple operation becomes a scan. Give them the right one and it becomes a pop. These three problems are chosen because in each, the obvious structure makes one operation quadratic and a different structure makes every operation constant — and the gap between them is entirely about matching shape to access pattern.

A snake game is the clearest case. The body is a list, so checking whether the head hit the body is a scan of that list — until you keep a set alongside it and the check becomes one lookup.

💡 Fun fact: Design Twitter's feed is a k-way merge, not a sort. Pulling the ten most recent tweets from everyone a user follows does not require collecting and sorting all their tweets — put each followee's most recent tweet in a heap, pop the newest, and push that person's next one. The heap never exceeds the number of followees, and you stop after ten pops. This is the same machinery as merging sorted lists, which is worth recognising because it means the design scales to users who follow thousands of accounts.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: pick the structure whose natural cheap operation is the one the system performs most — a heap when you repeatedly need the best, paired stacks when edits happen at a moving point, a deque when only the ends change — and add a parallel index when one structure cannot answer everything.

1. Two stacks around a cursor

Represent abc|def as a left stack holding a, b, c and a right stack holding f, e, d (top is d):

addText("X")     push X onto left        → abcX|def
deleteText(2)    pop 2 from left         → ab|def
cursorLeft(1)    pop from left,
                 push onto right         → a|bdef
cursorRight(3)   pop from right,
                 push onto left three times

Every operation touches only the tops of the two stacks, so all are O(1) per character moved. The position that an array makes expensive — the middle — is exactly where this structure is cheapest, because the cursor is the boundary between the two stacks.

2. A parallel index

The snake's body is a deque: it grows at the head and shrinks at the tail, which is exactly what a deque does cheaply. But "did the head hit the body?" is a membership question, and a deque answers that in O(n). Keep a set with the same contents:

body = deque([(0, 0)])
occupied = {(0, 0)}

def move(direction):
    head = next_cell(body[0], direction)
    if not eating:
        tail = body.pop(); occupied.discard(tail)   # remove BEFORE the check
    if head in occupied or out_of_bounds(head):
        return -1                                    # game over
    body.appendleft(head); occupied.add(head)

The ordering is the subtlety: the tail must be removed before testing the head, because moving into the cell the tail is vacating is legal. Testing first reports a false collision on exactly the input designed to catch it.

3. Bounded merging

For the feed, each user's tweets are stored newest-first. Push the head of each followee's list into a heap keyed by tweet id (which encodes recency), pop ten times, and refill from the popped tweet's own list after each pop.

4. A 30-second worked example (the tail-vacate case)

snake body: (0,0) (0,1) (0,2)     head at (0,0), tail at (0,2)
move down then right then up      ... eventually the head targets (0,2)

WRONG order:  head (0,2) in occupied? yes → game over  ✗
RIGHT order:  pop tail (0,2), discard from set
              head (0,2) in occupied? no  → legal move ✓

The snake is allowed to follow its own tail, and this ordering is the only thing that permits it.

5. Where you'll actually meet this

• Social feeds. Timeline generation by merging ranked sources is exactly the Twitter design, at scale.
• Text editors and terminals. The gap buffer used by real editors is the two-stacks idea with one array.
• Undo/redo. A pair of stacks, with the same "move an item across" mechanic as the cursor.
• Game state. Any moving body with ends-only mutation plus fast collision checks.
• Rate limiters and sliding windows. A deque of timestamps with a parallel aggregate.

6. Problems in this chapter

▶ Design Twitter

postTweet, getNewsFeed, follow, unfollow. Per-user tweet lists plus a k-way merge over followees for the ten most recent.
Pattern: heap-based bounded merge. Target: O(k log k) per feed for k followees.

▶ Design a Text Editor

Cursor movement, insertion and deletion at the caret. Two stacks meeting at the cursor.
Pattern: paired stacks. Target: O(1) per character moved or edited.

▶ Design Snake Game

Move the snake, grow on food, detect collisions. A deque for the body plus a set for O(1) membership.
Pattern: deque with a parallel index. Target: O(1) per move.

7. Common pitfalls 🚫

• Checking the head before removing the tail. The snake may legally move into the cell its tail is leaving.
• Scanning the body for collisions. O(n) per move; the parallel set exists precisely to avoid it.
• Letting the set and the deque drift apart. Every mutation must touch both, or the index lies.
• Sorting all tweets for the feed. A heap bounded by the number of followees is the point.
• Forgetting that a user sees their own tweets, and that following yourself must not duplicate them.
• Using a string or array for the editor. Insertion in the middle is O(n) and the whole exercise is avoiding that.
• Returning more characters than exist — cursorLeft and the "last ten characters" query must clamp to what is available.

8. Key takeaways

1. Match the structure to the operation performed most. That is the entire design step.
2. A parallel index fixes what one structure cannot answer — a set beside a deque for membership.
3. Keep the index in sync on every mutation, without exception.
4. Two stacks make a cursor free, which is why real editors use a gap buffer.
5. Merging beats sorting when you only need the top few from many sources.
6. Ordering within an operation matters. Remove the tail before testing the head.
7. Why interviewers like it: these are miniature system designs. The follow-ups — what if a user follows a million people, what if the document is enormous — probe whether your choice was deliberate.

Order: Design Twitter → Design a Text Editor → Design Snake Game.