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.

- WarLord August 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- MJ November 09, 2012 | Flag
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.

- kunal.id89 July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]);
	}
}

- Sunny December 22, 2012 | Flag
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.

- softy July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- words&lyrics July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

*interviewers

- Anonymous July 13, 2012 | Flag
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);
}
}
}

- achillesh July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain a bit!

- words&lyrics July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

plz xplain ur code....

- Abhijit October 05, 2012 | Flag
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.

- loveCoding July 12, 2012 | Flag Reply
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.

- nerd July 12, 2012 | Flag Reply
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’.

- apandey846 July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- words&lyrics July 13, 2012 | Flag
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

- kol July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- kol July 13, 2012 | Flag
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.

- Anonymous July 13, 2012 | Flag Reply
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??

- cobra July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cba

- naga ka baap July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cab

- naga ka dada July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- words&lyrics July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

anyone having suggestions regarding this?

- cobra July 13, 2012 | Flag
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??

- cobra July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

(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

- words&lyrics July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

Possible solutions cab , bca or abc

- words&lyrics July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- logloglogn July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- words&lyrics July 18, 2012 | Flag
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)

- Himanshu July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- words&lyrics July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Himanshu July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- words&lyrics July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jiangok2006 July 14, 2012 | Flag Reply
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)

- nybon July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nybon July 20, 2012 | Flag
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....

- Anonymous July 18, 2012 | Flag Reply
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....

- Anonymous July 18, 2012 | Flag Reply
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.

- Navin July 23, 2012 | Flag Reply
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.

- Navin July 23, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More