Quick Overview

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.

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

  1. Model stones as nodes in an undirected graph; connect nodes whose discs overlap or touch.
  2. Add two virtual nodes representing the bottom and top banks; connect stones that touch these banks.
  3. Use Disjoint Set Union (Union-Find) to efficiently track connectivity.
  4. Compare squared distances to avoid computing square roots.

Loading coding console...