Implement calculator and graph connectivity
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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
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.
Input: ('14-3/2',)
Expected Output: 13
Explanation: Division truncates toward zero.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Union Find Connected Components
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.