Solve build ordering and expression evaluation

Q: Solve build ordering and expression evaluation

This is a Coding & Algorithms interview question from Snowflake for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Solve build ordering and expression evaluation

Comments (0)