Coding interviews
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
var graph=new Dictionary<string,string[]>(StringComparer.Ordinal) { ["S"]=new[]{"T","A"}, ["A"]=new[]{"T"}, ["T"]=Array.Empty<string>() };
var queue=new Queue<(string Node,int Hops)>(); var seen=new HashSet<string>(StringComparer.Ordinal){"S"}; queue.Enqueue(("S",0));
int hops=-1; while(queue.Count>0) { var item=queue.Dequeue(); if(item.Node=="T") { hops=item.Hops; break; } foreach(string next in graph[item.Node]) if(seen.Add(next)) queue.Enqueue((next,item.Hops+1)); }
Console.WriteLine("fewest hops:"+hops);
Console.WriteLine("direct cost:"+10);
Console.WriteLine("via A cost:"+(1+1));
Reveal answer and reasoning
The output lines, in order, are “fewest hops:1”; “direct cost:10”; “via A cost:2”. BFS enqueues T and A from S and reaches T at one hop. The separate cost calculations show ten for the direct route and two through A. Those weighted values are explicit fixture facts, not costs discovered by BFS. The graph is finite, includes an adjacency entry for every node and uses exact ordinal node names.
Marking a node seen when it is enqueued avoids repeated BFS expansion and preserves the first-discovered minimum hop count for unit edges. The explicit weighted arithmetic below the traversal is a counterexample to changing metrics without changing the algorithm. It should never be presented as a weighted distance computed by that queue.
BFS uses O(V+E) time and O(V) discovered-state storage for the reachable graph, assuming ordinary set operations. Nonnegative weighted costs require an appropriate weighted algorithm such as Dijkstra; negative edges require different assumptions. No priority queue can repair a missing definition of the path objective. Adding weights to an input record while retaining first-discovery BFS distances does not preserve minimum-total-cost correctness.
Reusing the word shortest for both outputs conceals that contract change. The example also does not validate dangling adjacency names or handle an unbounded externally supplied graph.
What a strong answer covers
- Exact output: fewest hops:1 | direct cost:10 | via A cost:2
- BFS enqueues T and A from S and reaches T at one hop.
- Adding weights to an input record while retaining first-discovery BFS distances does not preserve minimum-total-cost correctness.
Common pitfall
Adding weights to an input record while retaining first-discovery BFS distances does not preserve minimum-total-cost correctness. Reusing the word shortest for both outputs conceals that contract change. The example also does not validate dangling adjacency names or handle an unbounded externally supplied graph.
Follow-up questions
- Change the direct cost to two and explain the remaining tie between one-hop and two-hop routes. Hint: equal total cost still leaves an output tie policy if the API returns a path rather than only a distance.
- How would negative edge weights or a reachable negative cycle change the route contract?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.