Determine blockage and parse HTML tokens
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
Given a set of 2-D circular stones, determine whether they can completely block the width of a river. You may define the input format. Given a sequence of HTML-like tokens (e.g., "open" "paragraph", "raw text" "ABC", "close" "paragraph"), build and print the corresponding DOM tree. Follow-up: support insertion and deletion of nodes.
Quick Answer: This question evaluates computational geometry and graph connectivity for the circular-stones subproblem and parsing plus tree data-structure manipulation for the HTML-like token subproblem, measuring skills in modeling spatial overlap, graph traversal/union operations, hierarchical DOM construction, and dynamic node insertion/deletion.
You are given the width of a river (an integer W) with banks at y = 0 and y = W, and a list of circular stones in 2D given as (x, y, r) with integer coordinates and radius. Two stones are considered connected if their discs overlap or touch: (xi - xj)^2 + (yi - yj)^2 <= (ri + rj)^2. A stone touches the bottom bank if y - r <= 0 and touches the top bank if y + r >= W. Determine if there exists a connected chain of stones that touches both banks, i.e., the union of discs forms a continuous barrier from y = 0 to y = W. Return True if the river is completely blocked, otherwise False.
Constraints
- 0 <= n <= 2000, where n is the number of stones
- 1 <= width <= 10^9
- -10^9 <= xi, yi <= 10^9
- 0 <= ri <= 10^9
- Two stones connect if (xi - xj)^2 + (yi - yj)^2 <= (ri + rj)^2
- A chain blocks the river if it connects y <= 0 to y >= width via overlaps/touches
- Use integer arithmetic (squared distances) to avoid floating-point errors
Hints
- Model stones as nodes in an undirected graph; connect nodes whose discs overlap or touch.
- Add two virtual nodes representing the bottom and top banks; connect stones that touch these banks.
- Use Disjoint Set Union (Union-Find) to efficiently track connectivity.
- Compare squared distances to avoid computing square roots.