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.

- Anonymous February 02, 2015 | Flag Reply
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).

- dchen215 February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- gameboy1024 February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gameboy1024 February 03, 2015 | Flag
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?

- Skor February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gameboy1024 February 02, 2015 | Flag
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.

- aaa February 02, 2015 | Flag Reply
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.

- sk3l February 05, 2015 | Flag Reply
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.

- Chetan February 11, 2015 | Flag Reply
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

- Naveen February 20, 2015 | Flag Reply
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

- RTLabs February 21, 2015 | Flag Reply
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.

- inki March 12, 2016 | Flag Reply
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;
}

- Abdelillah Faddaoui September 27, 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