Evaluate arithmetic expression using DFS
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: HR Screen
Given a string representing an arithmetic expression with non-negative integers, +, -, *, /, parentheses, and optional spaces, evaluate its value. Use depth-first traversal (recursive descent or a stack-based DFS simulation). Support unary minus and operator precedence. Return a 64-bit integer with division truncating toward zero. Analyze time and space complexity and discuss recursion depth limits and an iterative alternative.
Quick Answer: This question evaluates a candidate's understanding of expression parsing and evaluation using depth-first traversal, covering competencies in recursive descent or stack-based DFS, operator precedence, unary operators, and 64-bit integer division semantics with truncation toward zero.