## Microsoft Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

@krbchd, why not just run a dijkstra for a graph where friend edge weighs 0 and enemy edge weighs 1?
upd: 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use backtracking algorithm. consider enemy nodes as 0 and friend nodes as 1. Find a path between only nodes having 1's.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

perform a BFS? Turn the enemy paths into friendly paths and take note of number of magic potions. The minimum potion path is the result.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.