Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,227 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Nov 1, 2011
You have a n number of cities. Lets say city 1 has some information that needs to be sent to all other n-1 cities using minimal cost. Cost between each pair of cities is given. any number of cities can transmit the information once they receive the information but the overall total cost should be minimum
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (5)
4 of 6 people found this helpful
Nov 16, 2011
Dijkstra's tells you the shortest path from city 1 to any other city, but instead it is looking for a minimum spanning tree (MST). Prim's and Kruskal's algorithms would work.
Helpful Answer?
Yes |
No
Inappropriate?
Mar 11, 2012
I doubt an MST would work. Look at the constraint " any number of cities can transmit the information once .. ". What we need is a path from point 1 to point N that covers every other vertex with a minimum cost - A little bit like the TSP. I believe this is NP Complete..
Helpful Answer?
Yes |
No
Inappropriate?
Apr 20, 2012
If the costs are all >0 we can use a modified DFS in which the nodes are explored in decreasing order of cost. Not 100% sure this would work though. Any counter example?
Helpful Answer?
Yes |
No
Inappropriate?
Apr 20, 2012
Actually this does sound like a MST.
@Anonymous: "any number of cities can transmit the information once they receive the information but the overall total cost should be minimum"
that doesn't mean they can transmit the information once, they can transmit it once they receive it!
The fact that the total cost should be minimum definitely point to an MST.
@Anonymous: "any number of cities can transmit the information once they receive the information but the overall total cost should be minimum"
that doesn't mean they can transmit the information once, they can transmit it once they receive it!
The fact that the total cost should be minimum definitely point to an MST.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
1 of 5 people found this helpful
by candidate: