A strong answer
Dijkstra orders its priority queue by g(v), the distance from the start, so it expands in a circle around the start. A* orders by f(v) = g(v) + h(v), where h(v) estimates the remaining distance to the goal, so it expands vertices that look promising for this particular goal first. With h = 0 it is exactly Dijkstra.
A* returns an optimal path if h is admissible: it never overestimates the true remaining distance. Then when the goal is popped, every vertex still in the queue has g + h at least as large, which is a lower bound on any route through it, so none can be better. If h is also consistent, h(u) ≤ w(u, v) + h(v) for every edge, each vertex is expanded at most once, like Dijkstra. The closer an admissible h is to the true distance, the fewer vertices A* expands.
Heuristics must match the movement model: Manhattan distance for four-way grids, octile distance for eight-way grids with diagonals costing √2, straight-line distance for maps. An overestimating heuristic can return suboptimal paths; weighted A* does this deliberately, multiplying h by w > 1 to explore less, with a result at most w times optimal, a common trade in games.
A*'s main weakness is memory, since it stores every discovered vertex; variants like IDA* trade time for memory. Continental route planners precompute structures such as landmark distances (ALT) or contraction hierarchies that give far better guidance than geometry alone.
What the interviewer is listening for
- The f = g + h ordering and its relation to Dijkstra.
- Admissibility and consistency with correct consequences.
- Concrete heuristic choices and the weighted trade-off.
Common mistakes
- Using Manhattan distance when diagonal moves are allowed.
- Ordering only by h, which is greedy best-first search and isn't optimal.
- Claiming A* is always faster regardless of the heuristic.