## Adobe Interview Question for MTSs SDE1s

Country: India
Interview Type: In-Person

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

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.

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

Good Solution.

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

Pretty smart solution. It can perform worst case O(n^2) if we keep choosing winner/loser teams.

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

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).

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

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.

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

@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.

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

@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.

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

@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.

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

@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.

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

As we need to take binary decisions...what if we create a tree based on the output of the function API provided.

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 !!

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

Nice idea!

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

That makes sense. This solution does the same thing as the quicksort-based approach in my answer but in a different way. If you additionally permute the input randomly before starting, you get all the same characteristics as if you used my approach with random pivot selection.

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

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.

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

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)

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

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.

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

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).

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

I agree.

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

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)``````

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

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.

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

"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].

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

Expected time O(nlogn), worst O(n^2):

take each node(we can take it random to escape worst case complexity n^2) and add it to a tree. While inserting we check if new node won over the current node goes right, else left. The needed result is the inorder traversal of the tree.

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

Duplicate: question?id=14804702

Check out @eugene.yarovoi's solution!

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

yesss...thanx...one more soln with tree was good....how can i remove my ques?

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

Since you're the submitter, maybe there is an option to delete the question. If that doesn't work, click on "Report Duplicate" and provide the question ID.

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

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.

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.