Command Parsing And Predicate Evaluation

What's being tested

This tests command parsing, in-memory relational modeling, and predicate evaluation under clean coding constraints. The interviewer is looking for a small database engine: tokenize commands, store rows/columns efficiently, evaluate WHERE-style comparisons, and compose predicates without hard-coding one-off cases.

Patterns & templates

• Tokenizer + parser split — separate parse(command) from execute(ast); avoid mixing string handling with table mutation logic.

• Row-oriented storage — use dict[str, list[dict[str, Any]]] for simple queries; O(rows) scans are acceptable unless indexing is requested.

• Schema validation — track column names/types per table; reject unknown columns, wrong arity, and malformed commands before execution.

• Predicate interface — model filters as Predicate.evaluate(row) -> bool; implement ComparisonPredicate, AndPredicate, OrPredicate, and NotPredicate.

• Operator dispatch table — map strings like =, !=, <, <=, >, >= to functions from operator; centralizes type and comparison behavior.

• Recursive descent parsing — for compound expressions, parse precedence as OR -> AND -> NOT -> comparison; parentheses require a token cursor.

• Complexity accounting — simple SELECT ... WHERE is O(n * p) for n rows and p predicate nodes; memory is O(tables + rows).

Common pitfalls

Pitfall: Treating parsing as ad hoc split(" ") logic breaks quoted strings, parentheses, negative numbers, and compound predicates.

Pitfall: Evaluating predicates while parsing makes the code brittle; build an expression tree first, then execute it against each row.

Pitfall: Forgetting edge cases like missing tables, duplicate columns, NULL-like values, empty result sets, and string-vs-number comparisons.

Practice these

The practice card below covers the canonical variant — solve it end-to-end, then time yourself while adding compound predicates and validation.