Shortest Path and Pathfinding Algorithms Questions

Algorithms for finding shortest or optimal paths in graphs and grids, with emphasis on algorithm selection, correctness, and complexity. Include Dijkstra for non negative weighted graphs, Bellman Ford for graphs with possible negative edges and negative cycle detection, A Star search with admissible heuristics for informed pathfinding in grids and game maps, bidirectional search for speed improvements, and path reconstruction techniques. Cover differences between shortest path in unweighted versus weighted graphs, trade offs of heuristic design in A Star, typical grid and maze problem formulations, and practical applications such as game pathfinding, routing, and navigation.

MediumTechnical

65 practiced

Explain the A* search algorithm for informed pathfinding. Define open and closed sets, g, h, and f values. Carefully explain admissible and consistent heuristics, and give concrete admissible heuristics for 2D grids (Manhattan and Euclidean). Discuss how heuristic quality affects optimality and performance.

HardTechnical

60 practiced

Implement bidirectional Dijkstra in Python for weighted graphs with non-negative weights. Your implementation must return the shortest path and total cost, correctly detect the meeting point, and explain why the stopping condition differs from the unweighted bidirectional BFS case. Discuss edge cases and complexity.

EasyTechnical

57 practiced

Explain the Bellman-Ford algorithm and how it detects negative-weight cycles. Discuss the algorithm's complexity and scenarios where Bellman-Ford is preferred over Dijkstra in ML systems or feature computations.

EasyTechnical

63 practiced

Write Dijkstra's algorithm in Python. Input: graph as adjacency list dict where graph[u] = [(v, weight), ...], plus start and goal nodes. Return a tuple (path_list, total_cost). Include path reconstruction and ensure O(E log V) expected time. Handle unreachable target gracefully.

HardSystem Design

63 practiced

Design a scalable route planning service that handles 1B route requests per day, supports live traffic updates and multi-modal routing, and keeps average latency under 100 ms. Describe the architecture, graph storage, preprocessing choices, ML components for ETA and personalization, caching strategy, and deployment considerations including multi-region failover.

Unlock Full Question Bank

Get access to hundreds of Shortest Path and Pathfinding Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.