Amazon Interview Question for Software Engineer / Developers


Country: UK
Interview Type: In-Person




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

Maintain LinkedIn Persons as GraphNode and a connection as an edge from one graph node to another.
Now Do a breadth first search and while enqueuing connection in queue store the level as well .. when you find the desired person you will know its level also

BASICALY BFS

- smarthbehl July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Consider each person as one node, and start from your self, keep one queue, which will keep the list of friends of friends.

Q <= Priority Queue which store lowest hop person on top
Insert me into the Q with hop = 0;
While(Q is not empty)
	Node current = take the top node from the queue.
	Search Node in Hierarchy and figure out its Friends, (We may even store that in the queue, but this increase queue size in case of large system
	Insert all its friend with hop one more then current.
	If any of the friend is the required person, we store the algorithm and report the hop.

Complexity : Depends upon friends count and search efficiency in the hierarchy.

- sonesh July 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

A bidirectional breadth first search will be more optimal optimal

- Sudhir V May 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To find the shortest amount of hoops you could implement Dijkstra's Algorithm.

- oreste.luci August 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bidirectional BFS, maintaining the a hash table of explored nodes for each and the hops to get to that node. Whenever the frontier node of either BFS touches a node that is in the explored set of explored nodes for the other, the total hops is the sum of from each BFS to the connecting node.

- rbrt.coleman October 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A* algorithm search for finding path from a start node(you) to a goal(another person) node in the smallest cost.

- angel.ramos October 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Wow. All these answers suck. Do you really believe they want you to implement a breadth first search each time someone of the million users visits a connection and see the "degree" of the connection? LOL. Disqualified.

The right approach must be somewhere around using Floyd-Warshal-Algorithm offline in a batch job and optimizing it a bit for sparse 2d-arrays with parallelization and reducing the maximum degree to something reasonable, like 3 or maybe 4, which will make Floyd-Warshal much faster than N^3 for all normal data sets.

Then you could go into the server setup to do this computation on a few hundred million profiles. You could argue to run it more often on "active" users and update inactive connections less frequently, etc..

YES, LinkedIn will very likely not use Floyd-Warshal because at that scale it is likely not efficient enough unless you have some sort of behemoth super computer... Still it is a good shot into an unknown problem domain (distributed graph theory) and offers you a good starting point for in-depth discussions.

- Woot June 13, 2017 | 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