Interview Question


Country: United States
Interview Type: In-Person




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

I would solve it using BFS starting from both friends simultaneously instead of just from one friend.

Further I would ask if it's allowed to stop if, e.g. there is no connection of 4th or 5th grade. Let's assume everybody has 80 new friends in average:
- After expanding the frontier 4 times, starting at one friend there are ~40 Mio people covered.
- If expanding 2 times, starting at both friends, there are roughly 13 tousand people and it has the same effect.
If not terminating after a certain search depth, it eventually ends up hitting a lot of people.

Further accelleration for the positive case may be possible by using some heuristic to expand the frontier asymetrically towards the expexted other person (this how ever will then no guarantee to find the shortest path in the sense of # of hops and from here it starts to get philosophical)

- Chris December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Chris is right, of course. A potential fix on this can be assumed ( due to the connectivity problem : two nodes might reside in two unconnected components, albeit chance of it is extremely low, unless you are a free node, and have no friends (much like me) ). Some empirical theory suggests that 6 hops generally are good enough to connect any person to another.

Another nice way out is what he said - start at both ends. Check intersection of the nodes of the frontiers. If any time the intersection returns non empty, you have at least a solution.

- NoOne December 04, 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