Border Security: Determine If a Path Crosses Any Border in a Grid-Based Region Map
Question Details
Problem
You are given an N x M grid where each cell is labeled with a region ID (integer). A path is given as a list of adjacent cell coordinates. Determine whether the path crosses any border (i.e., moves from one region to a different region at any step).
Return the list of crossing points.
python
def find_border_crossings(
grid: list[list[int]],
path: list[tuple[int,int]]
) -> list[tuple[tuple[int,int], tuple[int,int]]]:
**Returns** list of (from_cell, to_cell) pairs where region changes
pass
Example:
grid = [
[1, 1, 2],
[1, 2, 2],
[3, 3, 2]
]
path = [(0,0),(0,1),(0,2),(1,2)]
-> [((0,1),(0,2))] # region 1 -> 2 crossing
Follow-ups
- How would you extend this to count the total number of unique borders (edges between distinct regions) in the entire grid?
- If the path may jump non-adjacent cells, how do you validate that the path is geometrically continuous?
- How would you visualize the result -- what data would you return to allow rendering of crossing markers on a map?
- What graph algorithm would you use to find all connected components of a single region across the grid?
Full Details
Problem
You are given an N x M grid where each cell is labeled with a region ID (integer). A path is given as a list of adjacent cell coordinates. Determine whether the path crosses any border (i.e., moves from one region to a different region at any step).
Return the list of crossing points.
python
def find_border_crossings(
grid: list[list[int]],
path: list[tuple[int,int]]
) -> list[tuple[tuple[int,int], tuple[int,int]]]:
**Returns** list of (from_cell, to_cell) pairs where region changes
pass
Example:
grid = [
[1, 1, 2],
[1, 2, 2],
[3, 3, 2]
]
path = [(0,0),(0,1),(0,2),(1,2)]
-> [((0,1),(0,2))] # region 1 -> 2 crossing
Follow-ups
- How would you extend this to count the total number of unique borders (edges between distinct regions) in the entire grid?
- If the path may jump non-adjacent cells, how do you validate that the path is geometrically continuous?
- How would you visualize the result -- what data would you return to allow rendering of crossing markers on a map?
- What graph algorithm would you use to find all connected components of a single region across the grid?
About This Question
This is a reported interview question from a anduril interview during the phone round.
It covers the following topics: Phone, Graph, Coding, Onsite, Matrix .