Evaluate arithmetic expression with precedence
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Evaluate a string arithmetic expression containing non-negative integers, '+', '-', '*', '/', parentheses '(', ')', and spaces. Respect operator precedence and associativity, support unary minus, and perform integer division truncating toward zero. Return the 64-bit integer result or an error for invalid inputs (e.g., mismatched parentheses). Describe and implement your approach (e.g., two-stack method or shunting-yard) and analyze time/space complexity.
Quick Answer: This question evaluates expression parsing and evaluation skills, covering operator precedence and associativity, unary operators, integer division truncating toward zero, tokenization, and robust error handling for malformed input.