Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
#1> Create tree T with maximal vertices such that every edge is a friend edge.
#2> Observe any two nodes in this tree T have 0 magic portions between them.
#3> For remaining nodes , find minimum path to any vertices in this tree.
#3 is acheived by modified Djikstra, where in distance of nodes of tree T is set to 0 to get all pair shortest path
Visualize this as collapsing all nodes in tree T into one node and then running dijikstra.
It is a connected component graph question
Algo
1> Find all the components and color them black for enemy and red for friends.
2> Sort all the components based on the number of nodes with them.
3> Foreach each friend component, try to find minimum neighboring enemy nodes requires to reach its neighboring friend component. You can use any graphs algorithm say dijkstra for it using edge of unit 1 distance for min hops.
4> Exit this loop till all components are reachable.
It's either there is a path between two nodes s and t, which requires 0 magic potions, or there is no path which with 1 magic potion you turn the edge s-t to a friend.
So the answer is either 0 or 1. A simple bfs or dfs can determine if there's a path between source and destination. O(n+m)
@krbchd, why not just run a dijkstra for a graph where friend edge weighs 0 and enemy edge weighs 1?
- emb June 14, 2016upd: I've read "every two nodes are either friend, or enemy" so just check if there is a friend-path between src and dst, and if not, use a single magic potion to go from src to dst.