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
Solution
from typing import List, Tuple
def can_block_river(width: int, stones: List[Tuple[int, int, int]]) -> bool:
n = len(stones)
if n == 0:
return False
# Disjoint Set Union (Union-Find)
parent = list(range(n + 2))
rank = [0] * (n + 2)
TOP = n # virtual node for top bank
BOTTOM = n+1 # virtual node for bottom bank
def find(a: int) -> int:
while parent[a] != a:
parent[a] = parent[parent[a]]
a = parent[a]
return a
def union(a: int, b: int) -> None:
ra, rb = find(a), find(b)
if ra == rb:
return
if rank[ra] < rank[rb]:
parent[ra] = rb
elif rank[ra] > rank[rb]:
parent[rb] = ra
else:
parent[rb] = ra
rank[ra] += 1
# Connect stones to banks if they touch
for i, (x, y, r) in enumerate(stones):
if y - r <= 0:
union(i, BOTTOM)
if y + r >= width:
union(i, TOP)
# Connect overlapping/touching stones
for i in range(n):
x1, y1, r1 = stones[i]
for j in range(i + 1, n):
x2, y2, r2 = stones[j]
dx = x1 - x2
dy = y1 - y2
rsum = r1 + r2
if dx*dx + dy*dy <= rsum*rsum:
union(i, j)
return find(TOP) == find(BOTTOM)
Explanation
Build an undirected graph where each stone is a node. Two stones are connected if their discs overlap or touch, determined via squared distance comparison. Add two virtual nodes representing the bottom (y=0) and top (y=W) banks; connect stones that touch these banks. The river is blocked if and only if there exists a connected component that intersects both banks, which reduces to checking connectivity between the two virtual nodes using Union-Find.
Time complexity: O(n^2). Space complexity: O(n).
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.