Coding questions · Snapchat

Implement calculator and graph connectivity

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.

Answer the following coding problems:

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.
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.

Arithmetic Expression Evaluator

Evaluate non-negative integer expressions with +, -, *, /, spaces, and parentheses; division truncates toward zero.

Examples

Example 1

Input: ('3+2*2',)
Output: 7

Explanation: Multiplication has precedence.

Example 2

Input: ('(2+3)*4',)
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.

Examples

Example 1

Input: (5, [[0,1],[1,2],[3,4]])
Output: [[0, 1, 2], [3, 4]]

Explanation: Return sorted connected components.

Example 2

Input: (3, [])
Output: [[0], [1], [2]]

Explanation: Every node is isolated.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.