Implement calculator and graph connectivity
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Answer the following coding problems:
1. Implement an arithmetic expression evaluator. Given a string containing non-negative integers, spaces, `+`, `-`, `*`, `/`, and parentheses, return the integer result. Multiplication and division have higher precedence than addition and subtraction. Parentheses may be nested. Division should truncate toward zero.
2. Implement a graph connectivity routine using Union-Find. Given `n` nodes labeled `0` to `n - 1` and a list of undirected edges, merge connected nodes and return all connected components. Each component should be returned as a sorted list of node ids, and the overall list may be in any order.
Quick Answer: This question evaluates proficiency in parsing and arithmetic expression evaluation (including operator precedence and nested parentheses) alongside implementation of disjoint-set (Union-Find) data structures for computing graph connected components.
Arithmetic Expression Evaluator
Evaluate non-negative integer expressions with +, -, *, /, spaces, and parentheses; division truncates toward zero.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('3+2*2',)
Expected Output: 7
Explanation: Multiplication has precedence.
Input: ('(2+3)*4',)
Expected Output: 20
Explanation: Parentheses override precedence.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Union Find Connected Components
Return connected components of an undirected graph as sorted node lists.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (5, [[0,1],[1,2],[3,4]])
Expected Output: [[0, 1, 2], [3, 4]]
Explanation: Return sorted connected components.
Input: (3, [])
Expected Output: [[0], [1], [2]]
Explanation: Every node is isolated.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.