Decide reachability with buses and limited walking
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given:
(
1) a start point (xs, ys),
(
2) an end point (xe, ye),
(
3) an integer K, and
(
4) an undirected graph of bus stations where each node has integer coordinates (xi, yi) and edges indicate bidirectional bus routes. Walking uses Manhattan distance d((x1, y
1), (x2, y
2)) = |x1 − x2| + |y1 − y2|. Riding a bus along any sequence of connected stations costs zero walking distance. You may:
(a) walk from the start to any station
(s), ride buses across the graph, then walk from some station to the end; or
(b) walk directly from start to end. Determine whether there exists a strategy whose total walking distance is ≤ K. Design an algorithm, state and justify its correctness, analyze time/space complexity, and implement a function returning true/false.
Quick Answer: This question evaluates the ability to combine graph reachability with geometric distance constraints, testing competencies in graph algorithms, Manhattan-distance reasoning, and constrained-path modeling within the Coding & Algorithms domain.
You are given a start point `start = [xs, ys]`, an end point `end = [xe, ye]`, an integer `k`, and an undirected graph of bus stations. `stations[i] = [xi, yi]` gives the integer coordinates of station `i`, and `edges` is a list of `[u, v]` pairs indicating a bidirectional bus route between station `u` and station `v` (0-indexed into `stations`).
Walking between two points costs Manhattan distance: `d((x1,y1),(x2,y2)) = |x1-x2| + |y1-y2|`. Riding buses along any sequence of connected stations costs **zero** walking distance (you may ride freely between any two stations in the same connected component).
You may either:
(a) walk from `start` to some station, ride buses across the graph, then walk from some (possibly different) station to `end`; or
(b) walk directly from `start` to `end`.
Return `true` if there exists a strategy whose **total walking distance** is `<= k`, otherwise `false`.
Key insight: because riding within a connected component is free, for each component you only pay `min over stations s in C of d(start, s)` to enter, plus `min over stations t in C of d(t, end)` to exit. Compute components with union-find (or BFS/DFS), take the best entry+exit per component, and compare against `k`; also consider the direct walk.
Constraints
- 0 <= len(stations) <= 10^5
- 0 <= len(edges) <= 2 * 10^5
- Coordinates and k may be negative or non-negative integers within 64-bit range
- edges reference valid 0-indexed positions in stations; routes are bidirectional
- Riding between any two stations in the same connected component is free
Examples
Input: ([0, 0], [10, 10], 6, [[1, 1], [8, 8]], [[0, 1]])
Expected Output: True
Explanation: Direct walk = 20 > 6. Stations 0 and 1 are connected. Walk start->station0 (cost 2), ride free to station1, walk station1->end (cost |8-10|+|8-10|=4). Total walking = 6 <= 6, so True.
Input: ([0, 0], [10, 10], 3, [[1, 1], [8, 8]], [[0, 1]])
Expected Output: False
Explanation: Best bus plan costs 2 + 4 = 6 and direct walk is 20; both exceed k=3, so False.
Hints
- Riding is free within a connected component, so the only costs are the walk from start into a component and the walk out of a component to end. Group stations into components first (union-find or BFS/DFS).
- For each component C, the cheapest plan that uses it is min_{s in C} d(start, s) + min_{t in C} d(t, end) — the best entry plus the best exit, since s and t may differ.
- Don't forget the no-bus option: a direct walk d(start, end) <= k. Take the minimum over the direct walk and every component's entry+exit, then compare to k.