Solve Two Coding Interview Problems
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are asked to solve two independent coding problems.
### Problem 1: Evaluate Nested Math Expressions
Implement a function that evaluates a string expression containing nested function-style arithmetic calls.
Supported operations:
- `add(a, b)`: returns `a + b`
- `sub(a, b)`: returns `a - b`
Operands may be integers or nested expressions. Whitespace may appear anywhere and should be ignored.
Examples:
```text
Input: "add(1, sub(1, 0))"
Output: 2
Input: "sub(add(3, 4), sub(10, 6))"
Output: 3
```
Requirements:
- Parse and evaluate the expression correctly.
- Support nested expressions of arbitrary depth within reasonable stack limits.
- Handle multi-digit and negative integers if they appear.
### Problem 2: Compute Maximum Chain Reaction
You are given a list of bombs. Each bomb is represented as `[x, y, r]`, where `(x, y)` is its position on a 2D plane and `r` is its blast radius.
If bomb `i` explodes, it will trigger bomb `j` if the Euclidean distance between their centers is less than or equal to `i`'s radius. Triggered bombs explode immediately and may trigger more bombs.
Return the maximum number of bombs that can explode if you choose exactly one bomb to detonate initially.
Example:
```text
Input: bombs = [[0,0,2], [2,0,2], [5,0,1]]
Output: 2
Explanation: Detonating bomb 0 triggers bomb 1, but neither bomb can trigger bomb 2.
```
Requirements:
- Model the chain reactions correctly.
- Avoid floating-point precision issues when comparing distances.
- Return the largest number of bombs reachable from any starting bomb.
Quick Answer: This question evaluates proficiency in parsing and expression evaluation, recursion/stack management, and string-processing for nested function-style arithmetic, alongside graph modeling, geometric distance reasoning, and traversal algorithms for the bomb chain-reaction scenario; the category is Coding & Algorithms.
Part 1: Evaluate Nested Math Expressions
Given a string expression, evaluate its value. The expression may be a single integer or a nested function-style arithmetic call using add(a, b) and sub(a, b). Operands can be integers or other nested expressions. Whitespace may appear anywhere and must be ignored. Support multi-digit and negative integers.
Constraints
- 1 <= len(expression) <= 100000
- The input expression is syntactically valid
- Integers may be negative and may contain multiple digits
- All intermediate and final results fit in a signed 64-bit integer
Examples
Input: "add(1, sub(1, 0))"
Expected Output:
Explanation: sub(1, 0) = 1, then add(1, 1) = 2.
Input: "sub(add(3, 4), sub(10, 6))"
Expected Output:
Explanation: add(3, 4) = 7 and sub(10, 6) = 4, so 7 - 4 = 3.
Hints
- Think of the expression as a simple grammar: an expression is either an integer or an operator followed by two expressions inside parentheses.
- Use a shared index while parsing so each character is processed only once.
Part 2: Compute Maximum Chain Reaction
You are given a list of bombs, where each bomb is [x, y, r]. If bomb i explodes, it triggers bomb j when the Euclidean distance between their centers is less than or equal to bomb i's radius. Triggered bombs explode immediately and may trigger more bombs. Return the maximum number of bombs that can explode if you choose exactly one bomb to detonate first.
Constraints
- 0 <= len(bombs) <= 100
- -10^9 <= x, y <= 10^9
- 0 <= r <= 10^9
- Use integer arithmetic when comparing distances to avoid floating-point precision issues
Examples
Input: [[0, 0, 2], [2, 0, 2], [5, 0, 1]]
Expected Output:
Explanation: Bomb 0 can trigger bomb 1, but bomb 2 is too far away from both.
Input: [[0, 0, 4], [3, 0, 3], [6, 0, 3], [9, 0, 1]]
Expected Output:
Explanation: Starting from bomb 0 or bomb 1 can trigger the entire chain of four bombs.
Hints
- Treat each bomb as a node in a directed graph, with an edge from i to j if i can directly trigger j.
- Compare squared distances with squared radii so you never need to use square roots.