Given a map represented as a graph of nodes (semantic map nodes) with weighted edges representing distances or travel times between nodes, calculate the shortest path (and/or estimated time of arrival, ETA) between a given start node and one or more target nodes.
Given a map represented as a graph of nodes (semantic map nodes) with weighted edges representing distances or travel times between nodes, calculate the shortest path (and/or estimated time of arrival, ETA) between a given start node and one or more target nodes. The problem is intentionally left somewhat vague — candidates are expected to clarify requirements (e.g., directed vs. undirected graph, edge weight semantics, single vs. multiple targets) before implementing. Similar to LeetCode 743 (Network Delay Time).
What clarifying questions would you ask before coding? (e.g., directed or undirected? negative weights possible? single or multiple targets?)
What is the time and space complexity of your solution?
How would you modify your approach if there are multiple target nodes and you need the shortest path to all of them?
| Approach | Notes |
|---|---|
| Bellman-Ford | Handles negative edge weights but runs in O(VE), much slower than Dijkstra for typical non-negative map edge weights. |
| A* Search | Uses a heuristic (e.g., Euclidean distance) to guide search toward a single target faster than Dijkstra, but more complex to implement and heuristic must be admissible. |
| BFS (unweighted graph) | Optimal and simpler if all edges have equal weight, but inapplicable when edges have varying distances/times. |
Common mistakes: One candidate passed the phone screen but was downleveled, suggesting the implementation or communication met the bar but not at the expected seniority.
Interviewer hints: The interviewer deliberately leaves the problem vague (directed vs. undirected, weight semantics, single vs. multiple targets) and expects the candidate to ask clarifying questions to make it concrete.
What passers do: Candidates who did well communicated with the interviewer upfront to concretize the vague problem statement before writing any code.; Implementing Dijkstra's algorithm was the expected and accepted solution; the interviewer in at least one report explicitly expressed agreement with that approach.