</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Reachability tree: UTF-8 stream self-declaration and Tic-Tac-Toe count constraints

Fun fact: Valid Tic-Tac-Toe State needs no search over game trees, even though 5,478 distinct boards are reachable. A few 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.


Core idea: "is this valid" usually means "could a legal process have produced this". 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

Each test shifts off exactly the bits of its pattern, so the patterns cannot overlap and the order is a matter of taste. A looser test ("starts with 11") would accept 1110xxxx as a 2-byte leader, so keep the masks exact. 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. The input is a list of integers whose low 8 bits are the byte, so mask each value with & 0xFF first. The snippet assumes that has been done.

This checks framing only. A full UTF-8 validator also rejects overlong encodings and surrogates, which the lesson covers as a follow-up.

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

A few comparisons decide every board. The counting rule comes first because it is cheap; the win rules then catch boards that count correctly but could not have finished that way. If X has three in a row and the counts are equal, X won and then O played, which the game forbids.

The lesson also writes the "both won" rejection as an explicit check. It is redundant here, since the two win rules demand different counts, but it is harmless and clearer to read.

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


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

data = [235, 140, 4]

Worked UTF-8 check of bytes 235, 140, 4 resolving to False

Compare [240, 162, 138, 147]: 240 = 11110000 declares four bytes, and 162, 138, 147 all begin with 10. Valid. The lesson's own examples are [206, 187, 65] (a 2-byte character then ASCII, True) and [226, 130, 4] (a 3-byte character whose last byte is 00000100, False).

For tic-tac-toe, ["XOX","OXO","OXO"] has X=4 and O=5, so O is ahead and it is False. The draw ["XOX","XOO","OXX"] has X=5, O=4 and no line, so it is True. If O has a line, countX == countO is required.

The whole UTF-8 problem is in the first byte: it tells you how many followers to demand, and the only work left is demanding them.


4. Where you'll actually meet this

  • Decoding text off the wire. JSON is required to be UTF-8 on the wire (RFC 8259), so a parser reading a body from a socket has to reject bytes that do not frame. Decoders usually report a bad sequence as the replacement character U+FFFD or an error.
  • Security filters. Overlong encodings (writing / as two bytes) have been used to slip characters past naive filters, which is why strict decoders reject them. The framing check in this chapter does not catch them by itself.
  • Game servers. A server that accepts a saved or client-reported board has to decide whether any legal game could have produced it. Mark counts and the winner are the cheap first checks.

5. Problems in this chapter

UTF-8 Validation

Decide whether a list of integers (low 8 bits of each) is a valid UTF-8 framing. Read each leading byte's pattern, then verify exactly that many 10-prefixed continuation bytes follow. The lesson walks a bit-string version and a direct bit-mask version, both O(n), and ends with overlong encodings, surrogates and chunked input as follow-ups.
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. Simulating every game (5,478 reachable boards) works as a test oracle only.
Pattern: reachability by counting. Target: O(1) time and space, since the board is a fixed 3x3.


6. Common pitfalls

  • Using loose bit tests. Testing only the top two bits would accept 1110xxxx as a 2-byte leader. Mask exactly the bits of each pattern.
  • Forgetting & 0xFF. Input integers can carry higher bits, so 321 is the byte 65.
  • 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.
  • Treating "X moves first" as a detail. It is the rule that makes the counting asymmetric: X == O or X == O + 1, never O > X.

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. Mask exactly the bits of each pattern, so the cases cannot overlap.
  4. The end of the input is a case, not an afterthought.
  5. Counting can replace simulation. A few 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.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.