Adobe Interview Question MTSs SDE1s
Country: India
Interview Type: In-Person
Pretty smart solution. It can perform worst case O(n^2) if we keep choosing winner/loser teams.
It's just like quicksort in that respect. It's possible that we can find a way to guarantee that we don't choose these edge cases, similarly to how we can apply the median of medians algorithm on quicksort to guarantee that quicksort performs in deterministic O(NlogN).
It wont work.On the right side,there can be a team which might have lost to pivot team..On the left side,there can be a team which might have won to pivot team.
@code_guru: No, there can't, by construction. The left side is defined as the teams that lost to the pivot team, and the right side is defined as the teams that won against the pivot team.
@eugene, @vikas
Sorry, but none of the ideas of partitioning and topological sort can work here, thanks to an imprecise question. The reason being the given relation 'lost to' that is determined by calling the function: displayResult(Team T1, Team T2), is not a "total order".
Let '< 'denote the relation 'lost to' and consider the following outcome of the matches between 3 teams t1, t2 and t3 as returned by the function displayResult(TeamA, TeamB)
t1 < t2.(meaning t1 lost to t2)
t2 < t3 (meaning t2 lost to t3)
t3 < t1 (meaning t3 lost to t1) [Clearly, transitivity(t1<t2<t3) is broken here and hence the outcome is not a total order]
Now all of the following 6 permutations are wrong
t1 < t2 < t3 (violates t3 < t1)
t1 < t3 < t2 (violates both t3 < t1 & t2 < t3)
t3 < t1 < t2 (violates t2 < t3)
t3 < t2 < t1 (violates both t2 < t3 & t1 < t2)
t2 < t3 < t1 (violates t1 < t2)
t2 < t1 < t3 (violates both t1 < t2 & t3 < t1)
Hence no such ordering is possible. In other words, the goal is unreachable and hence no algorithm can exist. If only by a chance we get a linear ordering of the outcomes, we can linearly order the set in finite time. Otherwise, the program would run in an infinite loop and never halt.
Here, the question itself is not very clear. Had the ordering relation been defined as something like the 'number' of other teams the given team has won against, it was still possible to linearly order the team as the set of natural numbers, even if duplicates are present, with the relation "is greater than or equal to", form a total order.
@eugene
Even if we assume that we luckily got a linearly ordered set, I doubt, how your algorithm with the following logic would ever terminate
team t = pickRandomElementFrom(S)
When are you going to stop the process of randomly picking the element and partitioning it? With repeated random selections over the same set, whose size is unchanged, how would you ensure that each of the teams T1 to Tn gets picked as a pivot point so it is placed in its correct position?
Alternatively, if you get a random sequence of elements from a total order set as input, you can simply reduce your solution to sorting as sorting can perform linear ordering on that set.
@Dumbo
We can assume that only the neighboring elements should be in order then this solution is correct since it will produce the 't1 < t2 < t3' output.
@Anonymous
Ah!, My bad, I just read the second half of the question below. Thanks for the pointer.
>> It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order.
If we assume that only the neighboring elements should be in order, then the original quicksort algorithm itself, with modified comparison logic, will work.
The recursive implementation defined by eugene, with randomized selection of the pivot and no reduction in the size of the input set in each step, just provoked my curiosity about the correctness and termination of the algorithm.
Otherwise, it is an excellent idea to use the partition routine. Thumbs up! I see that insertion sort with modified comparison method is also good to solve this problem, though merge sort is unlikely to work.
As we need to take binary decisions...what if we create a tree based on the output of the function API provided.
a.) start with any element as root.
b.) if next team lost the match with the root team, insert it into the left of the root
c.) if next team won the match with the root team, insert it into the right of the root
d.) keep inserting the teams with the above scheme(for root->left or root->right)
Print the in-order traversal of the tree !!
Question continued :-
For example if in a particular order, the teams appeared as T1, T2, T3, T4 … then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to T4… It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order. Only the neighboring elements should be such that the element on the left has lost to the element on the right.
How will you write the teams in this order? Write a code for it
Make all the necessary assumptions you need to solve the problem.
Create a directed graph. Each team becomes a node in the graph. Create an edge between Ti and Tj if Ti beats Tj. Run topological sort on this graph. The list of nodes returned is the desired ordering. Complexity = O(E+V) = O(n^2)
That doesn't mean we can run the topological sort algorithm on it. If you encounter an edge u->v, that completes a cycle during DFS, just ignore it because v has already been 'seen' so it will be included in the final ordering.
I suppose this modified topological sort is correct. But if you're going to achieve O(N^2), you might as well use a simpler algorithm. For instance, take the first element, and declare it to be a chain. Now for each additional element, try inserting it somewhere into this chain (it's not hard to show that given any element E not in the chain and any chain, E can be inserted somewhere into the chain).
We may use a divide and conquer technique very similar to that of merge sort.
The key idea is for the merge subroutine to maintain the invariant that T[i] beat its preceeding elements and lost to its succeeding elements. This will ensure a complexity of O(NlogN) but will require extra space.
A rough code is given below:
MergeSort(A,start,end)
{
if(start == end) return;
else
{
mid = (start+end)/2;
MergeSort(A,start,mid);
MergeSort(A,mid,end);
Merge(A,start,mid,end);
}
}
Merge(A,start,mid,end)
{
int i = start;
int j = mid+1;
int k = start;
int aux[];
while(k<=end)
{
if(i>mid) A[j++];
if(j>end) A[i++];
if(displayResult(A[i],A[j]) == A[i]) aux[k++] = A[j++];
else aux[k++] = A[i++];
}
for(int i=start; i<=end; ++i) A[i] = aux[i];
}
Call MergeSort(T,0,N-1)
Complexity can be higher if the midpoints that you choose tend to mostly winners or losers. In that case, you will not divide the array in 2 equal halves.
"The key idea is for the merge subroutine to maintain the invariant that T[i] beat its preceeding elements and lost to its succeeding elements. "
This invariant cannot possibly always be maintained because wins are not acyclic. It could be that T[1] loses to T[2] and T[2] to T[3], but T[1] wins against T[3].
As I think we can use it like Insertion Sort with Linked List.
Just take 2 teams first, say T1 and T2 in their order of winning. Then take T3. There are 3 cases for positioning it starting from left.
1. It has lost the game with T1, then sequence would be T3,T1,T2.
2. Won with T1 and lost with T2, then sequence would be T1,T3,T2.
3. Won with T1 and T2, then sequence would be T1,T2,T3.
In similar manner we can check for other teams and position those.
I have chosen linked list so as to make positioning easy in case new team is to be positioned in between.
Also, I believe that in some scenarios depending on teams, there can be multiple solutions depending on the order in which we start traversing the teams.
You can use an algo that gets its idea from quicksort. Pick a team, and partition the other teams into a set of teams that lost to that team and a set of teams that won against that team.
def order (list S) { team t = pickRandomElementFrom(S) // + here on a list means append return order (all x in S such that x lost to t) + t + order (all x in S such that t lost to x) }The expected time complexity is O(n log n) for n teams. The analysis is the same as for quicksort.
- eugene.yarovoi October 05, 2012