Solve build ordering and expression evaluation
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Part A — Dependency ordering: You are given an integer n (0 ≤ n ≤
200000) representing tasks labeled 0..n-1 and a list of prerequisite pairs [a, b] meaning task a requires task b to be completed first. Return any valid completion order that finishes all tasks, or return an empty array if impossible. Implement plan(n, prereqs). Optimize for time and memory; outline both BFS (in-degree) and DFS approaches, explain cycle detection, complexity, and how you would stream edges or handle multiple valid orders.
Part B — Expression evaluator (calculator variant): Implement evaluate(s) that parses and computes an arithmetic expression string with integers, spaces, parentheses, unary minus, and operators +, -, *, /, %, ^. Precedence: ^ highest (right-associative), then *, /, % (left-associative), then +, - (left-associative). Division truncates toward zero. Use 64-bit signed integers; report an error on malformed input. Aim for O(n) time and O(n) space using stacks or a shunting-yard parser. Provide tests for nested parentheses, unary minus before parentheses, and large inputs.
Quick Answer: This question evaluates competency in graph algorithms (topological ordering and cycle detection) and in parsing/evaluating arithmetic expressions with correct operator precedence, associativity, unary operators, and 64-bit integer semantics.
Dependency Ordering (Topological Sort)
You are given an integer `n` (0 ≤ n ≤ 200000) representing tasks labeled `0..n-1`, and a list of prerequisite pairs `[a, b]` meaning task `a` requires task `b` to be completed first. Return any valid completion order that finishes all tasks, or return an empty array if it is impossible (i.e. the prerequisite graph contains a cycle).
Model each pair `[a, b]` as a directed edge `b -> a` (do `b` before `a`). Run Kahn's BFS: compute in-degrees, seed a queue with every task that has in-degree 0, then repeatedly pop a task, append it to the order, and decrement the in-degree of its successors, enqueueing any that reach 0. If the produced order does not contain all `n` tasks, a cycle exists, so return an empty array.
The reference implementation seeds and processes in-degree-0 tasks in ascending label order, which yields a single deterministic valid order. Complexity is O(n + E) time and O(n + E) space, where E is the number of prerequisite pairs. A DFS post-order (with a 3-color visited state for cycle detection) is an equivalent alternative.
Constraints
- 0 ≤ n ≤ 200000
- Each prereq pair is [a, b] with 0 ≤ a, b < n
- a requires b to be completed first (edge b -> a)
- Return [] if the graph has a cycle (no valid order exists)
- Any valid topological order is acceptable
Examples
Input: (2, [[1, 0]])
Expected Output: [0, 1]
Explanation: Task 1 requires task 0, so 0 must come before 1.
Input: (2, [[1, 0], [0, 1]])
Expected Output: []
Explanation: 0 and 1 depend on each other: a 2-node cycle, so no valid order exists.
Hints
- Build an adjacency list and an in-degree array. For pair [a, b], add edge b -> a and increment in-degree of a.
- Kahn's algorithm: start a queue with all tasks whose in-degree is 0, pop one at a time, append to the result, and decrement in-degrees of neighbors.
- If the final order's length is less than n, a cycle exists: return an empty array. Seeding/popping in ascending label order makes the output deterministic.
Arithmetic Expression Evaluator
Implement `evaluate(s)` that parses and computes an arithmetic expression string containing non-negative integers, spaces, parentheses, unary minus, and the binary operators `+ - * / % ^`.
Operator precedence, from highest to lowest:
1. `^` (exponentiation) — right-associative
2. unary minus
3. `*`, `/`, `%` — left-associative
4. `+`, `-` — left-associative
Semantics: integer arithmetic on 64-bit signed values. Division truncates toward zero (so `-7 / 2 == -3`), and `%` is the matching remainder with the sign of the dividend (`-7 % 3 == -1`, consistent with `a - (a/b)*b`). A leading `-` is unary when it appears at the start of the expression, right after another operator, or right after `(`. Malformed input (mismatched parentheses, an operator in the wrong place, division/modulo by zero, an unexpected character) should raise an error.
Use a single-pass tokenizer plus a shunting-yard / two-stack evaluator for O(n) time and O(n) space.
Constraints
- Operands are non-negative integers in the source string; unary minus produces negatives
- Operators: + - * / % ^ ; plus parentheses and spaces
- Precedence: ^ (right-assoc) > unary minus > * / % (left-assoc) > + - (left-assoc)
- Division truncates toward zero; % is the matching remainder (sign of dividend)
- Use 64-bit signed integers; raise an error on malformed input
Examples
Input: ("1 + 2 * 3",)
Expected Output: 7
Explanation: * binds tighter than +, so 1 + 6 = 7.
Input: ("2 ^ 3 ^ 2",)
Expected Output: 512
Explanation: ^ is right-associative: 2 ^ (3 ^ 2) = 2 ^ 9 = 512.
Hints
- Tokenize in one pass: collect digit runs into integer tokens and treat each operator/paren as its own token; reject any other character.
- A '-' is unary when it is the first token, follows another operator, or follows '('. Give unary minus precedence between ^ and the */% group.
- Use a shunting-yard loop with an operand stack and an operator stack. For ^ and unary minus (right-associative) pop only strictly-higher-precedence operators; for left-associative operators pop equal-or-higher. Implement truncate-toward-zero division and a matching remainder for %.