Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
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).
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?
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.
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.
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.
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.
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
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.
The solution for this consist on applying topological sort.
- Anonymous February 02, 2015