Katkat
Back

Determine blockage and parse HTML tokens

SnapchatSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.