Solve build ordering and expression evaluation
Overview
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.
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.