## Amazon Interview Question for Applications Developers

Country: India

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

O(n) solution is possible. Build a directed graph with the players as nodes and perform a topological sort.
It is a modified version of this problem: Retrieve alphabetic order from dictionary.
search for it in stackoverflow.

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

What is the condition to construct edges? How to find whether an edge exist from one node to another node, where each node represents a player.

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

we can solve this in nlogn time using quicksort approach.
while partitioning we will use the API function as the > or < key as to compare the two players.

Ex:
a vs b a
a vs c c
b vs c b

suppose the array was arranged as cba.
take c as pivot and partition the array , it will become acb which is a correct solution..
this method can give different answer depending on the choice of pivot.

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

Intuitively this doesn't seem correct, because in this case if a>b, and b>c, it's not necessarily true that a>c, yet quicksort (or any sort) will build on the assumption that ">" is transitive.

I couldn't come up have a counter-example yet. I did write the following code to help generate all possible arrangements between 5 players and report which of them is valid. Initialize the won[i][j] matrix if you want player i to win player j.

``````import java.util.*;

class Test {
static boolean won[][] = new boolean[5][5];

static void printValid(int[] arr, int p, boolean[] used) {
if(p>=arr.length) {
System.out.println();
for(int i : arr)
System.out.print((char)(i+'a'));

for(int i=1; i<=3; i++) {
if(invalid(arr[i-1], arr[i]) || invalid(arr[i], arr[i+1]))
return;
}
System.out.print(" -> VALID");
} else {
for(int i=0; i<5; i++) {
if(used[i])
continue;
arr[p] = i;
used[i] = true;
printValid(arr, p+1, used);
used[i] = false;
}
}
}

static boolean invalid(int prev, int curr) {
return (prev == curr || won[curr][prev]);
}

public static void main(String[] args) {
// set won[i][j] if you want player #i to win player #j

printValid(new int[5], 0, new boolean[5]);
}
}``````

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

take a multi-dimension array of mXn : players[m][n] and make a matrix of the players matches as below ( i hope the formatting remains)

a b c d e f
a X 1 0 1 0 0
b 0 X 1 0 1 0
c 1 0 X 0 0 1
d 0 1 1 X 1 1
e 1 0 1 0 X 1
f 1 1 1 0 0 X

1 denotes victory
0 denotes defeat
X = denotes no match

now form a single dimension array or to be precise take a Queue using the first row of this matrix in "such a way that all the winners will come on left and all the loosers will come on right(take a queue for this)" - I will name this operation as sort. :

this will give this sequence :

c e f a b d
Now A is at the correct position , consider it to be pivot and now take the sub arrays cef (3X3 matrix) and bd (2 X 2 matrix) and perform the operation sort on it do it recursively till the size of array becomes 2
.
We will finally get an array with the above condition.

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

Sorting on the basis of number of wins will give a solution. But this problem can have multiple solutions i.e , not unique. So we just need to build one such solution out of the given input. And I was told linear time is possible.

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

Linear time is asking for a lot. I'm not even sure that's possible. There is a quadratic time algorithm, and I've heard something about there being an nlogn algorithm that's quite complex.

I could definitely be wrong about there not being a linear time approach, but interviews make tons of mistakes too.

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

*interviewers

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

{class PlayerArrange{
public static void main(String st[]){
Player[] playerArray=Player.getPlayerArray();
arrange(playerArray,0,playerArray.length());
}
private boolean Player.a_won_b(Player a,Player b){
return (a win b?true:false);
}
private arrange(Player[] playerArray,int startIndex,int lastIndex){
if(2>(lastIndex-startIndex)){
if(Player.a_won_b(playerArray[startIndex],playerArray[lastIndex])){
Player tem=playerArray[startIndex];
playerArray[startIndex]=playerArray[lastIndex];
playerArray[lastIndex]=tem;}
return;
}
int divValue=startIndex;
for(int i=startIndex+1;i<=lastIndex;i++){
if(Player.a_won_b(playerArray[divValue],playerArray[i])){
Player tem=playerArray[startIndex];
playerArray[startIndex]=playerArray[i];
playerArray[i]=playerArray[startIndex+1];
playerArray[startIndex+1]=tem;
divValue=i;
}
}
arrange(playerArray,startIndex,divValue-1);
arrange(playerArray,divValue+1,lastIndex);
}
}
}

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

Can you explain a bit!

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

plz xplain ur code....

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

We can use Quick Sort, At every time we place a player such that who lost goes to left side and all who won, go to right side we can do it recursively.. Complexity O(nlogn).
Note we cannot use Merge Sort or any other Sort as in this situation is a1>a2 and a2>a3, it does NOT mean a1>a3.

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

Construct a BST with the following requirement.
Do inorder traversal and you would get the sorted array.

The API can function as the > or < key as to compare the two players.

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

This problem is nothing but to sort the Array.This Array contains the players name, but we have to sort the array on the basis of their ability for which we have to use the given API(a,b).

So we can use Selection sort, and while comparing two players we will use the give API(a,b).
This way we will find the location of best player first time,(swap to first location as we do in selection sort) then in second iteration we will find second best player and so on.

Finally we will have sorted array according to their ability , fulfilling the give condition at position ‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’.

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

Its not a sorting problem. What you are suggesting is ranking player in order of number of wins. This is not ranking constraint is
with the element only next to it(before and after ). Infact it can have more than one solution , to say that , the result is not unique. You have to just build one solution out of the given order.
PS : To be done in linear time

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

@bhupendra it looks like a sorting problem give an example when its not a sorting problem

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

assume ranks of the players are {3,4,5,6,7,1}
the only it can be arranged such that player [i] wins with i+1 and looses to i-1 for all i
is {7,6,5,4,3,2,1}

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

Can you explain what will be the output in the following case? Three players, a, b and c, each of them has won one game each, i.e a wins from b, b from c and c from a.

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

Let assume three players: a,b,c..

a won b
b won c
c won a..

what is the expected output??

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

Cba

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

cab

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

By a won b , I guess you mean a defeated b
Possible solutions in this case are:
cab , abc , bca

cba is not the solution as c lost to b so cannot be before

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

i think there is no solution for this problem and it is not a sorting problem...

anyone having suggestions regarding this?

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

Let assume three players: a,b,c..

a won b
b won c
c won a..

what is the expected output??

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

Nlgn, I doubt it has o(n) solution.

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

(nlgn) is pretty straight forward.
Clearly this can have more than one solution set.
We need just one so there should be better than O(nlogn)
approach

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

@bhupendra : please give an example more than one solution ..
I think there is only unique soln

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

Match b/w Winner
a vs b a
a vs c c
b vs c b

Possible solutions cab , bca or abc

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

What's the NlogN solution? BST is only expected NlogN, and RB/AVL-tree style rotations aren't valid unless the comparisons are transitive (which they're not).

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

@log... Thanks for pin pointing. Sorting on the basis of rank can give one solution. But ranking itself will be O(n2)

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

let us say if a defeated b then a>b

insert (a,[ ]) = [a]
| insert( a , h::t) = if a > h then a :: h :: t else h :: insert(a,t)

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

I can't understand this!
Can you just explain this or give a code in c!

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

insert is a function that takes a player and a stack of players following the rule and returns a new stack of players. It is inductively defined here.

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

Can you give the pseudo code!
I still can't understand the expression!

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

QuickSort should work. I doubt there is O(n) solution.

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

1) initially, take any two players, and compare them with the API, and place them according to the result, let's say we have a < b
2) take any another player, c. Compare c with a and b:
2.1) if c < a, we have a valid arrangement c < a < b
2.2) if c > b, we have a valid arrangement a < b < c
2.3) if c > a and c < b, we have a valid arrangement a < c < b
3) repeat step 2 until we go through all remaining players

Note: the < and > is not the tradition symbol of 'less than' and 'bigger than' but just stands for a kind of relation between two players, so in step 2, it is possible that c < a and c > b but c < a < b is still a valid arrangement according to the description
Time: O(n)

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

this is not O(n) at each point of time you are comparing to rest of elements so for last element u'll compare with n-1 elements

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

Sorry I didn't make it clear, but in step 2, you don't have to compare c with every possible pair (a, b), you can take any two players that have been compared and insert c into them, their relationship will fall into the 3 possible scenarios I listed above, and there are multiple solutions to this problem and you will find one of the solution using the method above in O(n).

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

I was wondering whether can we build a Max heap out of those elements and instead of comparison we use API to compare two players...Will it work? Please comment....

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

I was wondering whether can we build a Max heap out of those elements and instead of comparison we use API to compare two players...Will it work? Please comment....

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

A better solution is to form a BST out of the given graph. The check condition of the BST will be based on whether or not a person won with another person. Do an inorder traversal after creating the tree. O(nlogn) for creating tree. O(n) for traversal.

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

A better solution is to form a BST out of the given graph. The check condition of the BST will be based on whether or not a person won with another person. Do an inorder traversal after creating the tree. O(nlogn) for creating tree. O(n) for traversal.

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.