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.