Zoox Software Engineer Onsite Coding Questions

## Problem You are given a list of variable definitions of the form `"name = expr"` where `expr` is an arithmetic expression involving integer literals, `+`, `-`, `*`, `/`, parentheses, and previously defined variable names. Evaluate each definition in order and return the final value of a queried variable. ```python def evaluate_formula(definitions: list[str], query: str) -> float: """ definitions: ["x = 3", "y = x + 2", "z = (x * y) - 1"] query: "z" """ pass ``` ``` Input: definitions = ["a = 4", "b = a * 2", "c = (a + b) / 3"] query = "c" Output: 4.0 # a=4, b=8, c=(4+8)/3=4.0 Input: definitions = ["n = 10", "m = n - 3", "r = m * m"] query = "r" Output: 49.0 ``` ## Follow-ups 1. How would you build a recursive descent parser for arithmetic expressions with operator precedence? 2. What data structure holds the evaluated variable context during parsing? 3. How do you detect and report undefined variable references? 4. Extend to support built-in functions like `sqrt(x)` and `abs(x)` in expressions.

## Problem Compute the H-index of a researcher given an array of citation counts. ## Likely LeetCode equivalent LeetCode 274 - H-Index ## Tags coding, sorting, math, onsite

## Problem You are given a list of `2n` players each with a skill rating. Split them into two teams of exactly `n` players such that the absolute difference in total skill between the two teams is minimized. Return the minimum possible difference. ```python def min_team_difference(ratings: list[int]) -> int: """len(ratings) is always even. Return min |sum(team1) - sum(team2)|.""" pass ``` ``` Input: ratings = [3, 1, 4, 2] Output: 0 # Team1=[3,2]=5, Team2=[1,4]=5 -> diff=0 Input: ratings = [1, 2, 3, 4, 5, 6] Output: 1 # Total=21, need each team close to 10.5 # Team1=[1,4,6]=11, Team2=[2,3,5]=10 -> diff=1 Input: ratings = [10, 1, 1, 1] Output: 7 # Team1=[10,1]=11, Team2=[1,1]=2 -> diff=9 # Team1=[1,1]=2, Team2=[10,1]=11 -> diff=9 # Optimal: same. ``` ## Follow-ups 1. Is this NP-hard in general? What constraint makes a DP solution tractable here? 2. Describe the DP state and transition for solving this exactly. 3. If teams don't have to be equal size, how does the problem simplify or change? 4. Extend: each player has two attributes (skill, cost) and you want to minimize skill difference subject to total cost <= budget.