Amazon Interview Question
Country: India
Interview Type: In-Person
This is true in the most general case, and Hamiltonian path is NP-complete. There are no known sub-exponential time algorithms that detect Hamiltonian paths exactly.
However, if the orderings are transitive -- in other words, victories accurately reflect the skill of the players in such a way that if A beat B and B beat C, then A beat C for all triplets A, B, C, then this problem simplifies to a topological sort, an algorithm that can be done in time proportional to the number of edges. There are N(N-1)/2 edges if there are N players, and so the time would be O(N^2).
Interesting. I had not heard of tournament graphs before and just ignored the term because I thought you used it only because we were discussing a tournament. I see now that it is fairly trivial to prove (by induction) that every tournament graph has a Hamiltonian path, and that an O(N^2) algorithm for this task can be obtained directly from this proof.
@eugene if we do it the topological sorting way how is the complexity O(n^2). We should choose a combination from all possible outputs (from topology sort) that has all nodes which makes it O(n^3)
One Aprroach :- I believe it is an insertion sort so the time complexity is O(n^2).
Second Approach:- If transitive behaviour is given then it becomes a sorting algorithm where we have to sort in ascending order of number of matches won. Time Complexity O(nlogn).
I think, sorting does not solve the problem.
A,B,C,D 4 players
A own 2 , B own 2 , c own 1 D own 1 matches
sorting gives ABCD answer but this answer may not be right.
B might have won to C
Yup we can insert any one of the candidates in an array then when we take another candidate and check with current one and place him accordingly. Then we take the next one and place him in this array by finding a suitable position for this candidate and so on.
@Free Bird: surprisingly, it so happens that your solution is correct. However, no offense or anything, but I'm inclined to think you just got very lucky. It so happens that there's always a suitable position for the next competitor to be placed, but did you actually prove this before you decided this was a legitimate solution? Without some reasoning about it, it's not immediately clear that every ordered sequence of K candidates has a place into which the K+1st candidate can be inserted without otherwise rearranging the sequence.
It is topological sort.
Also, in this problem is given that graph constructed out of player statistic, does not contain directed cycle (meaning a lost to b, b lost to c, c lost to a, for such case there is ordering possible)
Lets consider each node to be a player. It also keeps track of player which it has defeated. i.e. A -> B means A has defeated B. Then perform a topological sorting or topological ordering on that graph. You should be able to get the players in the order what has explained above. Still graph printing take O(n^2).
After thinking on this question over an hour, and coming up with same conclusions as all the other commentors (topological sort, restricted to no cycle). I decided to try and solve with the dumbest, simplest solution first (my usual approach). It appeared that the question is much more simpler then we all thought.
We are all assuming that we need to implement a real-world sports ranking system; this is not the case. The way the question is phrased is actually not restrictive at all, you only need to satisfy two condition; player i must win against i-1, and player i must lose to i + 1. No where does it say that i + 2 must win against player i, nor does it say that we cannot print the same player more than once. I also realized that this solution may cycle, re-reading the condition "To print out a combination 1,2,3, .. , i-1, i, i+1,....n" means we only have to print up to n times. :P
I forgot to describe the actual algorithm. Step 1) arbitrarily pick a player, it is now player i. Step 2) print a player i + 1 who won against i. Step 3) Player i + 1 is now player i, repeat step 2) until we reached n prints. Complexity is n.
I'll give a more specific example. Consider this case of 5 players:
Player 1 won against every other player except player 5
Player 2 lost to player 1 but won against every other player
Player 5 won against player 1 but lost against every other player.
If I pick player 1, the output of my algorithm would be
1 5 2 1 5
No, I think that's cheating. I do think the intent of the problem is probably to print every player exactly once. The correct answer is to have read the wiki article on "tournament graphs". There is a simple O(N^2) algo that will solve this problem. It uses an inductive approach: first construct a path for just 2 players, then incorporate a third player into that path (you can show there's always a way to do that), then incorporate a fourth...but all the players can be unique.
I do not think it is cheating. A good software engineer designs simple and efficient algorithm that meets the specification; to presume more or to do less can lead to real-life disaster.
You are making assumptions that are not stated in the original problem. You assume the ordering of the series must imply transitive wins (if p1->p2, p2->p3, than p1->p3). However, since every player played against each other, it is possible for 1->2, 2->3, 3->1 to occur, creating a cycle. This causes a paradox in the "ranking" concept.
You can still use your algorithm to just print a list, and avoid cycling since the list is finite; but would this not be "cheating" as well?
What eugene is saying is correct, the intent of the original problem was to print out a combination of all players (with no players repeated). I was stuck at the point thinking whether a solution to this always exists or not. Also normal sorting algorithms won't work in this case, as i+1 has relation to only i, and no relation to i-1, so there is no global sorting parameter here.
"I do not think it is cheating. A good software engineer designs simple and efficient algorithm that meets the specification; to presume more or to do less can lead to real-life disaster."
_
I must disagree. I would say a good software engineer does not believe the specification when it doesn't make sense, goes back to the person providing the specification, and resolves any doubts about the spec with all the stakeholders. I would screw up so many things every day if I always listened to what a document told me I should do. People writing the specs make mistakes.
_
I would have asked the interviewer whether your approach is cheating or not, and designed accordingly.
can anyone explain question please. i could not understand this que even??
- Anonymous April 29, 2012thanx