Snapchat·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Snapchat SWE interview with a geometry/graph problem that looks like a straightforward coordinate check until you realize the real trick is modeling circle overlap as a blocking chain. Not the hardest problem I've seen but the insight required to get there cleanly was non-trivial.

Questions Asked (1)

Given a rectangle from the origin to (X, Y) and a list of circles each defined by a center and radius, determine whether a path exists from the bottom-left corner to the top-right corner that stays inside the rectangle, never touches or enters any circle, and only contacts the rectangle boundary at the two corner endpoints.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I spent the first few minutes trying to think about this as some kind of BFS on a grid which was completely the wrong direction.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a connectivity question on a graph where nodes represent circles plus the two relevant boundaries (left/bottom and right/top). Determine if there is a chain of overlapping circles that connects the two boundary sets, which would block any path. Use union-find or BFS to check connectivity efficiently.

Pro tip: Clarify the boundary condition: the path may only touch the rectangle at the start and end corners, so any circle intersecting the left or bottom edge (excluding the start corner) or the right or top edge (excluding the end corner) should be considered as connected to that boundary. This subtlety often trips up candidates.

1. Clarify constraints and edge cases

Confirm that the path must stay strictly inside the rectangle except at the two corners, and that circles may overlap or touch each other and the boundaries. Discuss how to handle circles that contain the start or end point.

2. Model as a graph connectivity problem

Represent each circle as a node. Add edges between circles if they intersect or touch. Also add edges from circles to two super-nodes: one representing the left+bottom boundaries (excluding the start corner) and one representing the right+top boundaries (excluding the end corner).

3. Check for blocking chain

Use union-find or BFS/DFS to determine if the two super-nodes are connected. If they are, then a continuous barrier of circles blocks all paths, so the answer is false. Otherwise, a path exists.

4. Handle special cases

Check if the start or end point lies inside any circle; if so, return false immediately. Also consider if a single circle alone connects the two boundaries.

5. Analyze complexity and trade-offs

Discuss time complexity: O(n^2) for building edges, O(n α(n)) with union-find. Mention alternative approaches like geometric path planning (e.g., visibility graph) and their trade-offs.

Key Points to Mention

Graph connectivity approach: circles as nodes, boundaries as super-nodes.
Union-Find (Disjoint Set Union) for efficient connectivity checks.
Geometric intersection condition: distance between centers ≤ sum of radii.
Boundary conditions: only left+bottom and right+top boundaries matter, excluding corners.
Special cases: start/end inside a circle, single circle blocking.
Time and space complexity: O(n^2) time, O(n) space.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.