How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: ([0, 0], [5, 5], 10, [], [])

Expected Output: True

Explanation: No stations, but the direct Manhattan walk is 10 <= 10, so option (b) succeeds.

Input: ([0, 0], [100, 100], 5, [], [])

Expected Output: False

Explanation: No stations and direct walk = 200 > 5, so unreachable.

Input: ([0, 0], [20, 20], 4, [[1, 1], [9, 9], [19, 19]], [[0, 1]])

Expected Output: False

Explanation: Components are {0,1} and {2}. {0,1}: entry 2 (station0) + exit min(38,22)=22 = 24. {2}: 38 + 2 = 40. Direct = 40. All > 4, so False (the far station 19,19 is in its own component, not bridged).

Input: ([0, 0], [20, 20], 4, [[1, 1], [9, 9], [19, 19]], [[0, 1], [1, 2]])

Expected Output: True

Explanation: Now all three stations are one component. Best entry = 2 (station0), best exit = 2 (station 19,19). Total = 4 <= 4, so True.

Input: ([0, 0], [0, 0], 0, [[5, 5]], [])

Expected Output: True

Explanation: start == end, direct walk = 0 <= 0, so True with no walking needed.

Input: ([-3, -3], [3, 3], 4, [[-2, -2], [2, 2]], [[0, 1]])

Expected Output: True

Explanation: Negative coordinates. Direct walk = 12 > 4. Stations connected: entry = 2 (to (-2,-2)), exit = 2 (from (2,2)), total = 4 <= 4, so True.

Input: ([0, 0], [10, 0], 1, [[5, 0]], [])

Expected Output: False

Explanation: Single isolated station: entry 5 + exit 5 = 10; direct = 10; both > 1, so False.

Input: ([0, 0], [10, 0], 10, [[5, 0]], [])

Expected Output: True

Explanation: Direct walk = 10 <= 10, so reachable via option (b) (the lone station offers no improvement here).

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.

Quick Overview

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.