Katkat
Back

Implement calculator and graph connectivity

SnapchatMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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:

  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.