Parsing, Serialization, And Deserialization

What's being tested

These problems test stack-based parsing, robust tokenization, and unambiguous serialization/deserialization design under adversarial inputs. Interviewers are probing linear-time parsing patterns, correct handling of nesting/precedence, and safe encoding choices that preserve arbitrary bytes/characters.

Patterns & templates

• Stack-based bracket matching — push opening, on closing pop and compare; linear O(n) time, O(n) worst-case space, handle multiple bracket types.

• Shunting-yard / operator-precedence — convert infix to RPN for safe evaluation; implement precedence and left/right associativity explicitly.

• Recursive descent parser — small, readable parser for expressions with unary +/-, parentheses; good when grammar is simple and deterministic.

• Length-prefix (size + data) serialization — encode each string as <len>#<data> or binary 4-byte length, avoids escape complexities and preserves empties.

• Escape-based encoding — use only when stable delimiter sets; require robust escape rules and validate during decode to avoid ambiguity.

• DFS/BFS crawler with visited set — domain-filtered traversal, cycle avoidance via visited, respect polite limits (depth, rate).

• Tokenization first, parse second — separate lexical analysis from parsing to simplify unary vs binary operator resolution and variable substitution.

Common pitfalls

Pitfall: Treating unary - as binary; always detect operand absence left of operator and handle as unary with correct precedence.

Pitfall: Using simple delimiter split for serialization; strings may contain delimiter or be empty—prefer length-prefix.

Pitfall: Forgetting cycle detection in web crawl — omit a visited set and the crawler can loop indefinitely.