Microsoft Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

Can a city have multiple paths to different cities or just one path to a city? I would assume based on the question it only has one path, else we need more information because if city1 goes to city3, and city2 goes to city1 and city3, then how do we know which path user chooses to get to city3 from city2, since it can be (city2->city1->city3) or (city2->city3)?

With that said I think the question basically describes a directed graph with only one outgoing edge and multiple incoming edges and no cycle.

If the above assumptions are correct then we basically have visit each node and its children summing up the incoming people count.

- Assume a node has three property: {city:String, nPeople:Integer, totalVisitor: Integer}

- for each node in tree
 - currentSum: node.nPeople
 - visitChildren( node, currentSum)

- visitChildren( node, currentSum )
 - var current = node;
 - while current != null
  - currentSum += current.nPeople;
  - current.totalVisitor += currentSum;
  - current.children.forEach child
   - visitChildren( child, currentSum );

- tnutty2k8 August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

foreach src_node in tree:
do_mod_dijkstra(src_node, dst_node);
// in our do_mod_dijkstra: hash[visited_node] += src_node.population;

You will have the result in hash[node]

- Daniel October 13, 2017 | Flag Reply

Add a Comment

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


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


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