How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

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.

Input: (0, [])

Expected Output: []

Explanation: No tasks; the (empty) order is returned as an empty array.

Input: (1, [])

Expected Output: [0]

Explanation: A single task with no prerequisites.

Input: (3, [])

Expected Output: [0, 1, 2]

Explanation: No prerequisites; all in-degree 0, emitted in ascending label order.

Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])

Expected Output: [0, 1, 2, 3]

Explanation: Diamond DAG: 0 first, then 1 and 2, then 3 which depends on both.

Input: (3, [[0, 1], [1, 2], [2, 0]])

Expected Output: []

Explanation: A 3-node cycle 0->1->2->0 makes any ordering impossible.

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.

Input: ("(1 + 2) * 3",)

Expected Output: 9

Explanation: Parentheses force the addition first: 3 * 3 = 9.

Input: ("-(3 + 4)",)

Expected Output: -7

Explanation: Unary minus applied to a parenthesized sub-expression.

Input: ("-2 ^ 2",)

Expected Output: -4

Explanation: ^ outranks unary minus, so this is -(2 ^ 2) = -4.

Input: ("7 / 2",)

Expected Output: 3

Explanation: Integer division truncates toward zero.

Input: ("-7 / 2",)

Expected Output: -3

Explanation: Truncate toward zero: -3 (not floor -4).

Input: ("7 % 3",)

Expected Output: 1

Explanation: Standard remainder.

Input: ("-7 % 3",)

Expected Output: -1

Explanation: Remainder takes the sign of the dividend: -7 - (-2)*3 = -1.

Input: ("10 - 2 - 3",)

Expected Output: 5

Explanation: Subtraction is left-associative: (10 - 2) - 3 = 5.

Input: ("2 * (3 + (4 - 1)) % 5",)

Expected Output: 2

Explanation: Nested parentheses: 2 * 6 = 12, then 12 % 5 = 2 (* and % are left-to-right).

Input: ("42",)

Expected Output: 42

Explanation: A bare integer evaluates to itself.

Input: ("- -5",)

Expected Output: 5

Explanation: Two stacked unary minuses cancel: -(-5) = 5.

Input: ("3 + -4 * 2",)

Expected Output: -5

Explanation: Unary minus before 4, then * binds before +: 3 + ((-4) * 2) = -5.

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 %.

Solve build ordering and expression evaluation

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Dependency Ordering (Topological Sort)

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.

Input: (0, [])

Expected Output: []

Explanation: No tasks; the (empty) order is returned as an empty array.

Input: (1, [])

Expected Output: [0]

Explanation: A single task with no prerequisites.

Input: (3, [])

Expected Output: [0, 1, 2]

Explanation: No prerequisites; all in-degree 0, emitted in ascending label order.

Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])

Expected Output: [0, 1, 2, 3]

Explanation: Diamond DAG: 0 first, then 1 and 2, then 3 which depends on both.

Input: (3, [[0, 1], [1, 2], [2, 0]])

Expected Output: []

Explanation: A 3-node cycle 0->1->2->0 makes any ordering impossible.

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

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.

Input: ("(1 + 2) * 3",)

Expected Output: 9

Explanation: Parentheses force the addition first: 3 * 3 = 9.

Input: ("-(3 + 4)",)

Expected Output: -7

Explanation: Unary minus applied to a parenthesized sub-expression.

Input: ("-2 ^ 2",)

Expected Output: -4

Explanation: ^ outranks unary minus, so this is -(2 ^ 2) = -4.

Input: ("7 / 2",)

Expected Output: 3

Explanation: Integer division truncates toward zero.

Input: ("-7 / 2",)

Expected Output: -3

Explanation: Truncate toward zero: -3 (not floor -4).

Input: ("7 % 3",)

Expected Output: 1

Explanation: Standard remainder.

Input: ("-7 % 3",)

Expected Output: -1

Explanation: Remainder takes the sign of the dividend: -7 - (-2)*3 = -1.

Input: ("10 - 2 - 3",)

Expected Output: 5

Explanation: Subtraction is left-associative: (10 - 2) - 3 = 5.

Input: ("2 * (3 + (4 - 1)) % 5",)

Expected Output: 2

Explanation: Nested parentheses: 2 * 6 = 12, then 12 % 5 = 2 (* and % are left-to-right).

Input: ("42",)

Expected Output: 42

Explanation: A bare integer evaluates to itself.

Input: ("- -5",)

Expected Output: 5

Explanation: Two stacked unary minuses cancel: -(-5) = 5.

Input: ("3 + -4 * 2",)

Expected Output: -5

Explanation: Unary minus before 4, then * binds before +: 3 + ((-4) * 2) = -5.

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 %.

Quick Overview

Quick Overview