Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
It's not gonna work.
Imagine that you were given a start network (each host is connected with all others, so the length of path from each to each is 1). If you'll build MST, in the worst case you'll get one path with length equals to n-1 (n is number of hosts).
In general the given graph is unweighted, because the cost of each edge is 1. So we have to solve the problem of shortests path.
It's not clear for me from task's description how are we gonna send packets: "any to any" or "specific to any".
For "specific to any" case it can be solved with BFS with remembering of previous vertex in the best path for each vertex. I think that you may perform the same idea for "any to any".
You also may use Bellman–Ford or Dijkstra algorithm.
We need a bit more info, do we assume that Machine A sends a packet directly to Machine B without any intermediary devices? What does the network schema look like? How many routers/switches etc... are in between both machines? Does it cost $1.00 to send a packet to any one of these routers as well? A little bit more information on what we're dealing with would allow us to map out the network between the two machines and allow us to implement a cost minimizing algorithm.
Based on the initial question, I also believe that Djikstra or any other shortest-path algorithm is the way to go. MST won't work since all edges have the same weight.
Run Dijkstra from the edge of the network. So each node knows the cost from it to send packets to all the edge.
Run Dijkstra from the starting node. So each node knows the cost from the start to itself.
Find the node that has the least cost and send packet to it and then distribute from there.
Model the problem as a graph and compute the minimum spanning tree.
- Anonymous February 03, 2015