Implement an expression evaluator
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Implement an arithmetic expression evaluator that takes a string containing non-negative integers, '+', '-', '*', '/', parentheses, and whitespace, and returns the integer result. Support unary minus (e.g., '-3+5'), 64-bit intermediate results, and integer division truncating toward zero. Aim for O(n) time and O(n) space; describe your approach and edge cases.
Quick Answer: This question evaluates parsing and expression-evaluation skills, including operator precedence, parentheses, unary operators, integer arithmetic semantics (64-bit intermediates and truncating integer division), and robust edge-case handling.