Decide reachability with buses and limited walking

Q: Decide reachability with buses and limited walking

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given: (

a start point (xs, ys), (
an end point (xe, ye), (
an integer K, and (
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.

Decide reachability with buses and limited walking

Overview

Comments (0)