Question 1

Explain Dijkstra's algorithm — without code.

Accepted Answer

A good answer follows mechanism → invariant → complexity → limitation and fits in 90 seconds. Mechanism: "For each node I keep the cheapest known distance from the source; initially all infinite, the source 0. From a priority queue I always pop the node with the smallest distance and relax its neighbours — if dist[u] + weight beats the current dist[v], I update it and push it. This repeats until the queue empties." Invariant — the single most important sentence: "The distance of a popped node is final. Because every remaining candidate starts from a larger distance and, with non-negative weights, a path cannot shrink." Complexity: O((V + E) log V) with a binary heap, O(V) memory. Limitation: with negative weights it returns a wrong answer — and does so silently. If they ask "how does it differ from BFS?", keep one sentence ready: "Dijkstra is BFS with the queue replaced by a priority queue; BFS orders by step count, Dijkstra by accumulated cost." That analogy lands well because it ties the two algorithms into one system.

Question 2

Why do negative weights break Dijkstra? Give an example.

Accepted Answer

Structure it as cause → counter-example → fix; the most commonly skipped part is the counter-example, which is precisely the part that proves real understanding. Cause: Dijkstra is greedy — the moment it pops a node it says "this is final" and never looks at it again. That decision is only safe if every edge added to a path increases the distance. A negative edge violates that: a longer path found later can lower the distance, but the node is already closed. Counter-example (keep it small, three nodes suffice): A → B = 5, A → C = 2, C → B = −4. Dijkstra finalises C at 2, then B at 5; the true answer is 2 − 4 = −2. Fix: Bellman-Ford — relax every edge V − 1 times, O(V × E). Bonus: if any improvement remains on the V-th pass, there is a negative cycle. With a negative cycle "shortest path" doesn't exist at all, since each lap drives the cost down without bound. Practical note — this sentence ties the answer to real work: "So in a system where negative weights are possible (discount/bonus models, currency arbitrage) you must check the data constraints before picking the algorithm — a wrong answer throws nothing and can hide for a long time."

Question 3

You are building a navigation app. What would you choose for shortest paths, and what would you ask?

Accepted Answer

This is a design question — the expected order is questions first, decision second. Clarifying questions: what does "shortest" mean — distance, time or fuel? Is traffic involved (are weights dynamic)? One destination, or distances to everything? How large is the graph — a city (10⁵ nodes) or a country (10⁷+)? What latency must a response meet? Decision: weights (time/distance) cannot be negative, so Dijkstra is the right base. But since there is one specific target, A\ is better: the same logic plus a "straight-line distance to the target" heuristic that steers the search the right way and sharply cuts the nodes explored. The heuristic must never overestimate the real distance, or the result stops being optimal. Scale: at country scale neither Dijkstra nor A\ is fast enough in real time. In practice preprocessing-based approaches are used — highway hierarchies, precomputed segments. You may not be expected to know these, but saying "plain Dijkstra doesn't hold at this scale, you need preprocessing" is a strong signal. Traffic: when weights change you cannot cache results; typically each road segment's weight is stored per time window and the value at query time is used. Close like this: "For a prototype I'd start with Dijkstra because it's simple and correct; after measuring I'd move to A\*, and only go to hierarchical preprocessing if the numbers actually demand it." Avoiding premature optimisation is separately valued here.

Question 4

What changes if you must return the path itself, not just its length?

Accepted Answer

The answer is short, but say it precisely, because many candidates answer "I'd store all the paths", which is a poor solution memory-wise. The right solution: keep a prev (or parent) table. Every time you update dist[v] you also write prev[v] = u — "the cheapest way into v comes from u". At the end you start at the target, walk the prev chain back to the source and reverse the list. Cost: an extra O(V) memory and O(path length) to reconstruct. The algorithm's own complexity is unchanged. Why "store the full path per node" is bad: you copy an array at every node → memory rises toward O(V²) and updates get expensive. The prev table holds the same information in O(V). Bonus detail (if probed): several paths can tie on distance. prev keeps only one. If you need all optimal paths, prev[v] becomes a list that you append to whenever an equal distance is found. The same technique works for BFS — it isn't a Dijkstra-specific trick but a general traversal pattern. Pointing that out shows your knowledge is systematic rather than isolated.

Question 5

What happens if, instead of a priority queue, you scan an array for the minimum each time in Dijkstra?

Accepted Answer

This question checks whether you understand how a data structure drives an algorithm's complexity — answer with numbers. What changes: finding the minimum-distance node means scanning all nodes → O(V). That repeats V times → O(V²). Relaxations total O(E), so overall O(V² + E) = O(V²). Versus a binary heap: O((V + E) log V). On a sparse graph (E ≈ V) that is O(V log V), vastly better than O(V²): at 10⁵ nodes the gap is roughly 17,000×. An important detail very few candidates mention: on a dense graph it can flip. With E ≈ V² the heap version is O(V² log V) while the array version is O(V²) — so the plain array wins. The heap also carries a constant factor and extra memory traffic. The closing sentence: "So the question isn't 'which structure is better' but 'is the graph sparse or dense'. Since most real problems are sparse, I default to a heap." This answer is strong because it doesn't stop at reciting complexities — it ties them to the shape of the input.

Algorithm	When it is used	Complexity	Limitation
BFS	No weights (or all equal)	O(V + E)	Gives a wrong answer with weights
Dijkstra	Non-negative weights, single source to all	O((V + E) log V) — with a binary heap	Silently incorrect with negative weights
Bellman-Ford	Negative weights present; need negative-cycle detection	O(V × E)	Considerably slower
Floyd-Warshall	All-pairs distances on a small graph	O(V³)	Not applicable as V grows
A*	One specific target plus a good heuristic (maps, games)	Faster than Dijkstra in practice	The heuristic must be admissible or the result isn't optimal

Shortest path: Dijkstra