Simulation and Parsing

What is this?

There is nothing to discover in these problems. The rules are printed in the question, and the entire task is implementing them exactly — which turns out to be harder than it sounds, because each one contains a case that is easy to overlook and produces an answer that is almost right.

Version 1.0 versus 1.0.0. A snapshot update where a cell must not see its neighbour's new value. A read that must remember characters left over from last time. In every case, enumerating the cases before writing is what separates a clean answer from a patched one.

What makes the rule awkward

💡 Fun fact: Read N Characters Given Read4 II is the version with multiple calls, and it is a genuinely different problem from the single-call one. read4 always fetches four characters, so a call asking for 5 will over-read by 3 — and those 3 characters belong to the next call. The buffer holding them must therefore live in the object, not the function. Anyone who has written a network or file reader has met this exact bug, which is why the problem is asked at all.

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

The one-line idea: find the awkward part of the specification and choose a representation that dissolves it — two bits per cell for a simultaneous update, implicit zeros for missing segments, a persistent buffer for leftover input.

1. Encode two states in one value

Game of Life updates every cell simultaneously, so a cell must see its neighbours' old values. Rather than copying the grid, keep the old state in bit 0 and write the new state into bit 1:

for r in range(m):
    for c in range(n):
        live = count_live_neighbours(board, r, c)      # reads bit 0 only
        if board[r][c] & 1:                            # currently alive
            if live in (2, 3):
                board[r][c] |= 2                       # stays alive
        elif live == 3:
            board[r][c] |= 2                           # becomes alive

for r in range(m):
    for c in range(n):
        board[r][c] >>= 1                              # new state becomes current

Counting neighbours with & 1 always reads the old value, whether or not that neighbour has been processed. The second pass is a shift. No second grid, and the rule stays readable.

2. Missing means zero

def compare_version(v1, v2):
    a, b = v1.split('.'), v2.split('.')
    for i in range(max(len(a), len(b))):
        x = int(a[i]) if i < len(a) else 0             # missing segment = 0
        y = int(b[i]) if i < len(b) else 0
        if x != y:
            return 1 if x > y else -1
    return 0

Iterating to the longer length and defaulting to zero is what makes 1.0 equal 1.0.0. And int() handles leading zeros for free, which is why comparing the strings directly would be wrong.

3. Build backwards when alignment is from the right

Licence key reformatting groups characters from the end, so the first group may be short. Building the result in reverse and reversing at the end avoids computing where the short group starts:

cleaned = s.replace('-', '').upper()
out = []
for i, ch in enumerate(reversed(cleaned)):
    if i and i % k == 0:
        out.append('-')
    out.append(ch)
return ''.join(reversed(out))

4. A 30-second worked example (Buddy Strings)

Can s become goal with exactly one swap?

Buddy Strings worked example

The third case is the one that catches people. Equal strings are only buddies if some character appears twice, because the swap must actually happen and must leave the string unchanged.

5. Where you'll actually meet this

Release and dependency tooling. Semantic version comparison with unequal segment counts, in every package manager.
Payment and identifier display. Right-aligned grouping of card numbers, licence keys and IBANs.
Cellular automata and simulation. Any simultaneous-update rule on a grid, from Conway to physics steps.
I/O and network layers. Buffered reads where a fixed-size fetch over-reads and the remainder must persist.
Diff and comparison tools. Character-level difference detection with precise case handling.

6. Problems in this chapter

▶ Game of Life

Update a grid in place under simultaneous-update rules. Two bits per cell, then a shift pass.
Pattern: in-place state encoding. Target: O(mn) time, O(1) extra space.

▶ Compare Version Numbers

Compare dotted version strings. Split, iterate to the longer length, treat missing segments as zero.
Pattern: defensive parsing. Target: O(n) time.

▶ License Key Formatting

Regroup a key into blocks of k from the right, uppercased. Build backwards and reverse.
Pattern: right-aligned grouping. Target: O(n) time.

▶ Buddy Strings

Decide whether one swap makes the strings equal. Enumerate: unequal lengths, zero differences with a repeat, exactly two cross-matching differences.
Pattern: exhaustive case analysis. Target: O(n) time, O(1) space.

▶ Read N Characters Given Read4 II

Read n characters using a read4 primitive, across multiple calls. Keep the over-read characters in a persistent buffer.
Pattern: buffered I/O with retained state. Target: O(n) per call.

7. Common pitfalls 🚫

Copying the grid in Game of Life. Correct, and it fails the stated in-place requirement.
Reading neighbours without masking. & 1 is what keeps the count reading pre-update values.
Comparing version strings lexicographically. "10" < "9" as text; parse to integers.
Iterating only to the shorter version's length. 1.0 and 1.0.0 must compare equal.
Forgetting the repeated-character case in Buddy Strings when the strings are already equal.
Making the leftover buffer local in the read problem. It must persist across calls, which is the entire point of part II.
Assuming read4 fills the buffer. A short read means end of file, and the loop must stop.

8. Key takeaways

Find the awkward clause and design around it. Simultaneous updates, unequal lengths, retained state.
Two bits per cell turn an in-place simultaneous update into two clean passes.
Missing means zero, not shorter-therefore-smaller.
Build backwards when alignment is from the right, then reverse once.
State that must survive calls belongs to the object, not the function.
Enumerate cases before coding. On Buddy Strings that list is the solution.
Why interviewers use these: no insight can rescue a sloppy implementation, so they show your actual habits — which is precisely what they want to see.

Order: Game of Life → Compare Version Numbers → License Key Formatting → Buddy Strings → Read N Characters Given Read4 II.

Buddy Strings

Core idea: You're allowed exactly one swap of two letters in s (you must swap — no skipping). Whether that single swap can turn s into goal collapses into three crisp cases. First, the lengths must match — a swap never changes length, so len(s) != len(goal) is an instant False. Second, if s and goal are already equal, a swap can only "do nothing" if some letter appears twice in s (swap the two copies and nothing changes); with all-distinct letters, every swap breaks the equality, so you need a duplicate. Third, when they differ, line them up and collect the positions where they disagree: there must be exactly two mismatch positions i, j, and the crossed letters must match — s[i] == goal[j] and s[j] == goal[i] — so that swapping s[i] and s[j] repairs both at once. Any other mismatch count fails. The whole thing is one linear scan, O(n).

Problem, rephrased

Two name tags come out of a label maker: s is the tag you printed, goal is the tag you meant to print. The machine has exactly one swap operation left in its buffer — it will pick two letter slots and exchange whatever is in them — and it must fire once before it powers off; you can't decline it. You're given the two strings s and goal.

Return True if you can choose the two slots so that after the single forced swap the tag reads exactly goal, and False otherwise. The swap is mandatory even when s already equals goal — you'd have to burn it on two identical letters to leave the tag unchanged — and a swap never changes length, so tags of different lengths are beyond repair.

Strip the story away and this is the classic Buddy Strings check: given strings s and goal, return True iff you can swap the letters at two indices i != j of s so that the result equals goal.

A worked input/output

`s`	`goal`	Output	Why
`"ab"`	`"ba"`	`True`	Exactly two crossed mismatches — swap `a` and `b`.
`"ab"`	`"ab"`	`False`	Already equal, but all letters distinct — no harmless swap.
`"aa"`	`"aa"`	`True`	Already equal and a duplicate `a` exists — swap the two `a`s.
`"abcd"`	`"badc"`	`False`	Four mismatch positions — one swap can't fix four.
`"abc"`	`"ab"`	`False`	Different lengths — a swap never changes length.

Notice the answer depends only on the count and shape of the mismatches (plus a duplicate check when there are none) — never on the specific letters beyond those few positions.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Intermediate