Parse and Validate

What is this?

Both problems hand you a value and ask whether it could exist. UTF-8 is self-describing — the first byte declares how many follow — so validating it means checking that the declaration and the reality agree. Tic-tac-toe is subtler: a board can look perfectly sensible and still be unreachable, because no sequence of alternating moves could have produced it.

Neither needs an algorithm. Both need the complete list of rules, written down before any code.

💡 Fun fact: Valid Tic-Tac-Toe State needs no search over game trees — three counting rules decide every board. If X won, X must have played the winning move last, so count(X) == count(O) + 1. If O won, O played last, so the counts are equal. Both winning at once is impossible, and it falls out of those two rules without a separate check: X winning demands one more X than O, O winning demands equality, and no board satisfies both. A problem that looks like it needs simulation collapses into three comparisons.

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

The one-line idea: "is this valid" almost always means "could a legal process have produced this" — so enumerate what the process can do, and check the input against that, not against your intuition.

1. Read the declaration, then verify it

i = 0
while i < len(data):
    b = data[i]
    if   b >> 7 == 0b0:    n = 0                  # 0xxxxxxx
    elif b >> 5 == 0b110:  n = 1                  # 110xxxxx
    elif b >> 4 == 0b1110: n = 2                  # 1110xxxx
    elif b >> 3 == 0b11110: n = 3                 # 11110xxx
    else: return False                            # 10xxxxxx here, or 5+ leading ones
    for j in range(i + 1, i + 1 + n):
        if j >= len(data) or data[j] >> 6 != 0b10: return False
    i += n + 1
return True

The order of the tests matters: check the shortest pattern first, because 0b110 and 0b1110 share a prefix and a looser test would swallow a longer form. The else branch is doing two jobs — rejecting a continuation byte that appears where a leading byte should be, and rejecting five or more leading ones, which no valid UTF-8 has.

Running off the end is the case people forget. A three-byte leader at the last position is invalid, and the j >= len(data) guard is what says so. Only the low 8 bits of each integer are meaningful, which the problem states and which the shifts above already assume.

2. Count, then check who won

x, o = count('X'), count('O')
if o > x or x > o + 1: return False                # alternating play, X first
if wins('X') and x != o + 1: return False          # X's win must have been the last move
if wins('O') and x != o:     return False          # likewise for O
return True

Four lines and every board is decided. The counting rule comes first because it is cheap and rejects most invalid boards; the win rules then catch the ones that count correctly but could not have finished that way — a board where X has three in a row and the counts are equal means X won and then O played, which the game forbids.

wins must check all eight lines: three rows, three columns, two diagonals.

3. A 30-second worked example (UTF-8)

data = [235, 140, 4]

235 = 11101011      three leading ones → a 3-byte sequence, 2 followers expected
140 = 10001100      starts with 10 ✓   valid continuation
  4 = 00000100      starts with 00 ✗   NOT a continuation byte

→ False

Compare [240, 162, 138, 147]: 240 = 11110000 declares four bytes, and 162, 138, 147 all begin with 10. Valid. The whole problem is in that first byte — it tells you exactly how many followers to demand, and the only work left is demanding them.

4. Where you'll actually meet this

• Network and file parsers. Rejecting malformed encodings at a trust boundary is a security requirement, not a nicety.
• Text editors and terminals. Detecting whether a file is UTF-8 or something else is this check, run over a sample.
• Anti-cheat and server validation. "Could the client have legitimately reached this state" is the tic-tac-toe question at scale.
• Save-file and replay integrity. Verifying a stored game state against the rules that generated it.
• Protocol fuzzing. Length-prefixed and self-describing formats are where parser bugs and CVEs live.

5. Problems in this chapter

▶ UTF-8 Validation

Decide whether a list of integers is a valid UTF-8 encoding. Read each leading byte's pattern, then verify exactly that many 10-prefixed continuation bytes follow.
Pattern: self-describing stream validation. Target: O(n) time, O(1) space.

▶ Valid Tic-Tac-Toe State

Decide whether a board is reachable by legal alternating play. Compare the counts of X and O, then check that any win is consistent with who moved last.
Pattern: reachability by counting. Target: O(1) — the board is fixed size.

6. Common pitfalls 🚫

• Testing the bit patterns from longest to shortest, so a shorter prefix matches the wrong case.
• Not guarding against the end of the array when a leading byte declares more followers than remain.
• Accepting a continuation byte as a leader. 10xxxxxx in the leading position is invalid.
• Allowing five or more leading ones, which no UTF-8 sequence has.
• Checking only rows and columns for a tic-tac-toe win. Both diagonals count.
• Adding a separate "both won" check. It is already impossible under the two win rules.
• Assuming X always moves first is a detail. It is the rule that makes the counting asymmetric.

7. Key takeaways

1. "Valid" means "reachable" — check the input against the process that would generate it.
2. A self-describing format tells you what to demand. Read the declaration first.
3. Order your pattern tests shortest-prefix first, or they overlap.
4. The end of the input is a case, not an afterthought.
5. Counting can replace simulation — three comparisons decide every tic-tac-toe board.
6. Some impossible cases fall out for free once the real rules are stated correctly.
7. Why interviewers like it: there is nothing clever to say, so completeness is the only thing on display.

Order: UTF-8 Validation → Valid Tic-Tac-Toe State.