## Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

The solution for this consist on applying topological sort.

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

Nice catch. I think you've got it. In the example, P1 wins P2, and P2 wins P3, can be thought as there are directed edges P1 -> P2, P2 -> P3 in the graph, and P1 and P3 won't be in a match so there is no possibility for us to have a P3 -> P1, so there is no cycle. And we just need to topological sort all players which will gives us the rank. The winner of the tournament is the player who loses to nobody (no incoming edge in the graph).

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

Topological sort is essential for the second part sorting problem but I'm still thinking how to get the winner with only O(1) space.
If the data is a HashMap<Winner, Loser> then it's easy but if it's just a list of tuples: list(winner, loser) then I don't know how. Any idea?

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

The winner part is trivial. Assuming that there is only one winner there will be only one node with no incoming edges. Just iterate through the nodes looking for that and you'll get your O(n) time and O(1) space.

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

That's actually O(n^2), not O(n) time if you don't have a hashmap :)

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

What information are you given? What if P1 beats P2, P2 beats P3, and P3 beats P1?

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

Look at the assumption: "The following condition always hold"

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

1. take a node, start comparing with other nodes one by one. When comparing, if A <- B, then take B, else A. The last node holding is the winner.

2. Divide the graph by group of 3 nodes. Find the ranking within the group. Merge groups. When merging, if these are two groups, a-> b-> c and 1 -> 2 -> 3, compare C and 3. If c -> 3, then compare 2 and c. Merging will be done in O(n) and there would be O(log n) steps.

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

Actually, IMO the question implies that each player faces every other player at least once. I think the transitive property refers to the scoring system that would be used for choosing a winner and ordering the participants.

Basically, I view this problem as an instance of a tournament graph, and generating a score sequence would give the solution.

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

I think this can be solved using max heap property. Create a max heap and add players into heap. The winner will always be at the root and all the other players will be after that in the order of their defeat. Creating a max heap from array takes 4n run time i.e. O(n). And heap sort is in place sorting algo so O(1) space. To find rank of players we just have to sort this heap which takes O(n.lg n) time.

Let me know if I am missing anything.

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

Consider players are in a array. Store the result of a match between 2 players in a hashtable with player pair as key and result as value. Now finding the winner is similar to finding maximum value in a array which is O(n) time and o(1) space since retrieving values from hashtable is o(1). And again sorting is nothing but sorting an array which is O(nlogn).
Let me know of any corrections

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

Considering all the players P1,P2....Pn. O(n) time and O(1) space:

Current=P1;
for(i=1 to n){
if(P(i)has defeated Current){
current =P(i); // at any state current has defeated all the P1 to Pi
}

}
return current; // for the winner from P1 to Pn

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

This is just a different type of sorting question, so if you provide your own comparison function: Pi > Pj if Pi won Pj then you are all set to use any of the classic sorting algorithm. Finding the winner is equivalent to finding the max of a list of numbers which can be done in 0(n), go over player and always keep the winner of the max (winner of the two players).

And sorting can be done O(NlogN) with any of the standard sorting algorithms.

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

it can be done with 0(n) .
lets suppose :(p1,p2,p3,p4,p5,p6...)
so the algorithm is :
index=p1;
winner=p1;
while(index!=pn){
if(!p1 won index){
swap(p1,index)
}
index++;//means p(i+1)
}
index=p2;
while(index!=pn){
if(!p1 won index){
return null;
}else{
return p1;
}

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.