Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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?
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.
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.
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;
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?
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.
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.
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;
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;
}
}
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;
}
}
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.
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.
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.
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
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).
1. Make M1 as a maxheap
- Wang Yuanzhi February 04, 20152. 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.