~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Iterators & parsers

Parsers and interpreters

Tokenize, recursive descent, S-expressions, evaluation and type inference.

Quiz (10) Spot the pattern
Notes

Recognise it when: you evaluate expressions (calculators, spreadsheet formulas), parse S-expressions or a toy language, build trees from text, or infer types.

def parse(tokens):             # S-expression: (a (b c) d)
    tok = tokens.pop(0)        # use an index or deque in real code
    if tok == "(":
        node = []
        while tokens[0] != ")":
            node.append(parse(tokens))
        tokens.pop(0)          # ")"
        return node
    return tok
  • Pipeline: tokenize, then parse into an AST, then evaluate. Keep the stages separate.
  • Recursive descent for precedence: expr := term (('+'|'-') term)* and term := factor (('*'|'/') factor)*.
  • Spreadsheets: formulas form a dependency graph. Detect cycles and recompute dependents in topological order.
  • Type inference: type variables plus unification (bind variables, occurs-check), and substitute generics per call site (clone the generic signature first).

Gotchas: unary minus, whitespace, integer division rules, deep recursion on long input, and error messages for malformed input.

8 problems

Practical systems

Iterators & parsers Lazy sequences, tokenizers and tiny interpreters.

Parsers and interpreters

esc