Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

1. Make M1 as a maxheap
2. Make M3 as a minheap
3. Do a while loop if min(M3) < max(M1):
3.1. Exchange min(M3) and max(M1)
3.2. Maxify M1 and minify M3 respectively
4. Loop for each number - say N - in M2:
4.1. If N < max(M1), exchange N and max(M1), maxify M1 and continue loop
4.2. If N > min(M3), exchange N and min(M3), minify M3 and continue loop


Then we finish it if the question does not ask the data in M1/M2/M3 to be sorted, otherwise do a sort on 3 parts respectively.

- Wang Yuanzhi February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

smart choice dude, M2 will not need to sort right ?

- kinsonljc February 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@kinsonljc, M1/M2/M3 are all no needs to be sorted in step 1 ~ 4.

- Wang Yuanzhi February 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, Thanks for sharing your idea. I'm not very clear on the while loop you have at step 3. Could you please explain the intuitive idea behind it?

- Deepi February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution isn't really minimizing the number of transfer operations (and no, calling it "exchange" doesn't make it better.

Here's pseudo code of the direction I've been thinking about:

void sort_machines(m1, m2, m3)
{
	sort m1; 
	sort m2; 
	sort m3;
	partition(m2, m3); // now m2.max <= m3.min 
	partition(m1,m2); // now m1 is in its final state
	partition(m2, m3); // now all machines are in their final state
}

// after this procedure it is guaranteed that both machines are sorted and ma.max <= mb.min
void partition(ma, mb)
{
	// maybe u can make this loop more efficient by transferring 20% at a time.
	repeat 9 times (for a total 90% capacity of each machine)
	{
		transfer top 10% of ma to mb;
		transfer bottom 10% of mb to ma;
		sort ma;
		sort mb;
	}
}

Total cost is 3+3*9*4 = 111 sort and transfer operations.

- Omri.Bashari May 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

First thing we can conclude that the size of all the machines are equal since the question itself asks 1/3 of the total be put in each of them. Hence, let us assume the size of each machine to be 100 ints.


step 0, copy first 9 ints from M1 to M2, and next 9ints from M1 to M3.

step 1, as most of them pointed out, bubble sort individual machines.

step 2 is merge sort the three machines from the top into M1 until it's available space becomes 1%.

step 3 is merge sort from the end of M1 M2 M3 into M3 until it's space becomes 1%

repeat step 2 and step 3 until both M1 and M3 have 1% space available.

If there is more to sort, then obviously at this point, you will have 28% space in M2. so, copy 27 ints from the end of M1 into M2 using bubble sort and go to step 2.

eventually, we will get first 1/3 into M1, and last 1/3 into M3. Hence, the middle 1/3 would be in M2.

- Subbu February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

sort M1;
sort M2;
sort M3;
find number of elements in M2 less than max of M1 and call this n;
find number of elements in M1 greater than min of M2 and call this m;
lesser of n and m is p;
transfer elements from M1 index M1.length - 1 - p to M1.length -1 to M2 i.e. max p elements
transfer elements from M2 --> index 0 to p - 1 i.e. min p elements
sort M1;
sort M2;
find number of elements in M3 less than max of M1 and call it x;
transfer x elements from M1 index M1.length - 1 - x till M1.length - 1 to M3
transfer x elements from M1 index 0 till index x - 1 to M1
sort M1;
sort M3;
find number of elements in M3 less than max of M2 and call it y
transfer y elements from M2 index M2.length - 1 - y to M2.length -1 to M3
transfer y elements from M3 index 0 to index y - 1 to M2
sort M2;
sort M3;
you now have all machines having values in order;

- Anonymous February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

quick pseudo code idea:

intsort(M1);
intsort(M2);
intsort(M3);

M1=crop(M1,1,M1.length/3);
M2=crop(M2,M2.length/3,2*M2.length/3);
M3=crop(M3,2*M3.length/3,M3.length/3);

if M1.last > M2.first
new = append(M1,M2);
elif M1.first < M2.last
new = append(M2,M1);
else
new = overlpappend(M1,M2);

if new.last > M3.first
new = append(new,M3);
elif new.first < M3.last
new = append(M3,new);
else
new = overlpappend(new,M3);

proc overlapappend (Ma,Mb) returns M:
determine interval where both Ma Mb overlap;
M = upper non-overlap part;
Mtemp = sort(append(overlap parts));
M = append(M,Mtemp);
M = append(M,lower non-overlap part);
return M;

This should use O(n log n) time for each sort and consider that arrays need not be same length. is there a better/more elegant solution?

- nils.muellner@googlemail.com February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One alternative to comparison based sorting is Counting sorts. Here, the complexity is O(n). But the requirement is that the integer values are bounded and not very sparse as the integers are used to "index into an array".

What are the properties of the input integers in the question?

- smallchallenges February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What are the properties of the input integers in the question?
Any sample input for M1, M2 and M3!

- zafar ziya February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is the m1,m2,m3 capacity equivalent so m1?

- Jay February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Initial step:
Each machine sort numbers.
Each machine send to the other two the count, min value and max value.

Everyone consistently determine that the machine with lowest min is "low", highest "high" and the third "mid". If they are equal, determine based on max. If max are equals based on lexicographical comparison of hostname.

From this moment and on each machine keeps track of its count, min and max in every iterative operation.
In addition, "mid" keep tracks of those stats at "low" and "high". also "low" keeps track of min at "mid" and "high" max at "mid". "low" and "high will not communicate with each other and will not keep track of each other.

Odd step:
If max of "low" greater than min of "mid", mid sends first part of its numbers in the amount of 10% memory to "low". "low" sorts them via no extra memory sorting algo.
If min of "high" less than max of "mid", mid sends last part of its numbers in the amount of 10% memory to "high". "high" sorts them via no extra memory sorting algo.
If none of those condition holds, go to final step.
Even Step is similar, but "low" and "high" send 15% of memory worth to "mid" and "mid" sort after getting from both. (Note that on the second time odd step also can use 15%)

Final step. "Low" and "high" know the grand size of array from init step so they know if they are less than 1/3 or more. So does "mid". So they can unambiguously determine who sends and how many to make up 1/3 at "low" and "high"

On coordination. Each player know when is even step or odd - if they received, now is their turn to send. In addition, a peer does not have to wait for the disjointment on the other side, it can proceed to the final step as soon as it determines disjointment.

- CT February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I can draw very detailed state diagram for individual machine (not the three for each of the three roles but one because at the begging we don't know so every player is equal, they may be in different states) but how would I share drawing.

However, let's see if anyone can come up with simpler solution.

- CT February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort M1;
sort M2;
sort M3;
find number of elements in M2 less than max of M1 and call this n;
find number of elements in M1 greater than min of M2 and call this m;
lesser of n and m is p;
transfer elements from M1 index M1.length - 1 - p to M1.length -1 to M2 i.e. max p elements
transfer elements from M2 --> index 0 to p - 1 i.e. min p elements
sort M1;
sort M2;
find number of elements in M3 less than max of M1 and call it x;
transfer x elements from M1 index M1.length - 1 - x till M1.length - 1 to M3
transfer x elements from M1 index 0 till index x - 1 to M1
sort M1;
sort M3;
find number of elements in M3 less than max of M2 and call it y
transfer y elements from M2 index M2.length - 1 - y to M2.length -1 to M3
transfer y elements from M3 index 0 to index y - 1 to M2
sort M2;
sort M3;
you now have all machines having values in order;

- Anonymous February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks pretty promising, but are you certain you will always have room for all of the transfers?

- CT February 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1)Merge the unsorted arrays from M1,M2,M3 into a temporary array.
2) Sort the temporary array.
3) Store 1/3 into each M1, M2 and M3 checking the length of each array.

public class ThreeMachineInsertionSorting {
	public static void main(String[] args) {
		int[] ar1 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,-10};
		int[] ar2 = { 20, 19, 18, 17, 16, 15, 14, 23, 12, 11, 10 };
		int[] ar3 = { 20, 19, 21, 122, 10, 9, 11, 12, 4, 13, 18, 17 };

		performInsertionSort(ar1, ar2, ar3);
	}

	private static void performInsertionSort(int[] ar1, int[] ar2, int[] ar3) {
		int[][] arrayOfArrays = { ar1, ar2, ar3 };
		
		int [] unSortedArray= mergeArrays(ar1,ar2,ar3,arrayOfArrays);
		
		 int i,j,key;
		for(i=1;i<unSortedArray.length;i++){
			key= unSortedArray[i];
			j=i-1;
			while(j>=0 && key<unSortedArray[j]){
				unSortedArray[j+1] = unSortedArray[j];
				j--;
			}
			unSortedArray[j+1] = key;
		}
		
		System.out.println("Size of the unSorted array is :=" + unSortedArray.length);
		
		
		shareLoad(unSortedArray, arrayOfArrays);
		

	}

	private static void shareLoad(int[] sortedArray, int[][] arrayOfArrays) {
		int loadFactor = sortedArray.length/3;
		int index=0;
		
		while(index<sortedArray.length){
			for(int [] ar : arrayOfArrays){
				for(int i=0; i<ar.length;i++){
					if(i<=loadFactor){
						ar[i] = sortedArray[index];
						index++;
					}
				}
			}
		}
		
		for(int [] ar : arrayOfArrays){
			System.out.println("******************************************array properties**************************************");
			System.out.println("Size of array::" + ar.length);
			for(int i=0; i<ar.length;i++){
				System.out.print(ar[i]+" ");
			}
			System.out.println("\n******************************************************************");
		}
		
		
	}

	private static int[] mergeArrays(int[] ar1, int[] ar2, int[] ar3,int[][] arrayOfArrays ) {
	
		int[] colaboratedArray = new int[ar1.length + ar2.length + ar3.length];
		System.out.println("Length of multi-dimensional array :-"
				+ arrayOfArrays.length);

		int i = 0;

		while (i < colaboratedArray.length) {
			for (int[] ar : arrayOfArrays) {
				for (int j = 0; j < ar.length; j++) {
					colaboratedArray[i++] = ar[j];
				}
			}

		}
		
		return colaboratedArray;
	}
}

- Ankit February 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class ThreeMachineInsertionSorting {
public static void main(String[] args) {
int[] ar1 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,-10};
int[] ar2 = { 20, 19, 18, 17, 16, 15, 14, 23, 12, 11, 10 };
int[] ar3 = { 20, 19, 21, 122, 10, 9, 11, 12, 4, 13, 18, 17 };

performInsertionSort(ar1, ar2, ar3);
}

private static void performInsertionSort(int[] ar1, int[] ar2, int[] ar3) {
int[][] arrayOfArrays = { ar1, ar2, ar3 };

int [] unSortedArray= mergeArrays(ar1,ar2,ar3,arrayOfArrays);

int i,j,key;
for(i=1;i<unSortedArray.length;i++){
key= unSortedArray[i];
j=i-1;
while(j>=0 && key<unSortedArray[j]){
unSortedArray[j+1] = unSortedArray[j];
j--;
}
unSortedArray[j+1] = key;
}

System.out.println("Size of the unSorted array is :=" + unSortedArray.length);


shareLoad(unSortedArray, arrayOfArrays);


}

private static void shareLoad(int[] sortedArray, int[][] arrayOfArrays) {
int loadFactor = sortedArray.length/3;
int index=0;

while(index<sortedArray.length){
for(int [] ar : arrayOfArrays){
for(int i=0; i<ar.length;i++){
if(i<=loadFactor){
ar[i] = sortedArray[index];
index++;
}
}
}
}

for(int [] ar : arrayOfArrays){
System.out.println("******************************************array properties**************************************");
System.out.println("Size of array::" + ar.length);
for(int i=0; i<ar.length;i++){
System.out.print(ar[i]+" ");
}
System.out.println("\n******************************************************************");
}


}

private static int[] mergeArrays(int[] ar1, int[] ar2, int[] ar3,int[][] arrayOfArrays ) {

int[] colaboratedArray = new int[ar1.length + ar2.length + ar3.length];
System.out.println("Length of multi-dimensional array :-"
+ arrayOfArrays.length);

int i = 0;

while (i < colaboratedArray.length) {
for (int[] ar : arrayOfArrays) {
for (int j = 0; j < ar.length; j++) {
colaboratedArray[i++] = ar[j];
}
}

}

return colaboratedArray;
}
}

- Ankit Gupta February 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Solution is complex so, please bear with me till the end.
There are 3 machines with capacity 100 and filled with 90 values(let's call percentages as one unit value).

Initial Condition:
M1: 90 (Unsorted)
M2: 90 (Unsorted)
M3: 90 (Unsorted)

Step 1:

Sort all 3 individual machines: 3 sort operations
Now, follow the process below:
1. Transfer top 30 from each machine to M1 (2 transfer operations as top 30 of M1 is already in M1)
2. Transfer bottom 30 from each machine to M3 (2 transfer operations)
3. Transfer middle 30 from each machine to M2 (2 transfer operations)

Current Status:
M1: top 30 values rest 60 unknown
M2: 90 unknown
M3: bottom 30 values rest 60 unknown 

Operations so far: 3S + 6T (3 sorts and 6 transfer) (Every step will take exactly 9 operations until specified otherwise)

Now next time on wards we won't touch the known value only transfer unknown values.

Step 2:

Repeat Step 1 for value 20 instead of 30

Current Status:
M1: top 50 values rest 40 unknown
M2: 90 unknown
M3: bottom 50 values rest 40 unknown

Step 3:

Repeat Step 2 for value 10 instead of 20

Current Status:
M1: top 60 values rest 30 unknown
M2: 90 unknown
M3: bottom 60 values rest 30 unknown

Step 4:

Repeat Step 3 once more.

Current Status:
M1: top 70 values rest 20 unknown
M2: 90 unknown
M3: bottom 70 values rest 20 unknown

Step 5:

Repeat Step 4 for value 5 instead of 10

Current Status:
M1: top 75 values rest 15 unknown
M2: 90 unknown
M3: bottom 75 values rest 15 unknown

Step 6:

Repeat Step 5 once again

Current Status:
M1: top 80 values rest 10 unknown
M2: 90 unknown
M3: bottom 80 values rest 10 unknown

Step 7:

Repeat Step 5 once again

Current Status:
M1: top 85 values rest 10 unknown
M2: 80 unknown
M3: bottom 85 values rest 10 unknown

Operations so far: 7 * 9 = 63 (7 Steps, each took 9 operations)

Step 8:

1. Transfer 10 unknown from M1 and M3 to M2 (2T)
2. Sort M2.
3. Transfer top 5 to M1 and bottom 5 to M3(2T)

Total Operations: 63 + 5 = 68

I know it is hard to follow. Please let me know if there is any better solution or is there any thing I can amend in it.

- deepanshu February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I see. In my solution I was not thinking when it should converge, but it should in static amoun of time since we are dealing with percentails.

- CT February 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the 3 ranges are not overlapping, it will take 3 sorts and 6 transfers for 3 machines to discover this. I think minimize does not mean to minimize worst case scenario but to minimize in a given situation. I thought to count number of operations in my algorithm and realized it will be different in different situation, but it should be because it can take different minimum amount of steps in every situation.

- CT February 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As in starting u r right we can sort M1,M2 and M3 after that can we use minHeap data structure to store all the data from all three machine and then , i can read MinHeap to store 1st 1/3rd record in M1 and then 2nd 1/3rd to M2 and then rest M3..please correct me if i am wrong.

Thanks u

- sumit.polite February 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem with minheap data structure is "to store all the data". I think the only reason two operations are allowed is because we can do them in place(don't require additional storage).

- deepanshu February 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I fail to see how you can do the first step in 6 transfer operation. every machine has space only for 10 items at the beginning hence you cannot move there 30 items in one transfer..

- JB February 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Step1- take the m1count, m2count,m3count
Step2- copy M1,M2,M3 to M4
Step4 - sort M4
Step5 - store one third of count/3 in M1
sTEP6 - store second one third in M2
step7 - store rest in M3

- Mak February 03, 2015 | 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