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.

- emb June 14, 2016 | Flag Reply
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.

- krbchd June 14, 2016 | Flag Reply
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.

- hprem991 June 16, 2016 | Flag Reply
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.

- shraddha bhise June 20, 2016 | Flag Reply
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)

- Anonymous October 09, 2016 | Flag Reply
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.

- Sibendu Dey June 15, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More