## Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: UK
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 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

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.

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

A bidirectional breadth first search will be more optimal optimal

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.

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.

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.

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.

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.