Amazon Interview Question
Applications DevelopersCountry: India
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.
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]);
}
}
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.
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.
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.
{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);
}
}
}
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’.
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
@bhupendra it looks like a sorting problem give an example when its not a sorting problem
Let assume three players: a,b,c..
a won b
b won c
c won a..
what is the expected output??
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
(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
@bhupendra : please give an example more than one solution ..
I think there is only unique soln
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).
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)
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.
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)
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
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).
O(n) solution is possible. Build a directed graph with the players as nodes and perform a topological sort.
- WarLord August 18, 2012It is a modified version of this problem: Retrieve alphabetic order from dictionary.
search for it in stackoverflow.