Amazon Interview Question
Software Engineer / DevelopersCountry: India
Its mentioned that we cant use extra space ... merge sort uses extra space ..while merging...
just look...
MERGE (A, p, q, r )
1. n1 ← q − p + 1
2. n2 ← r − q
3. Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4. FOR i ← 1 TO n1
5. DO L[i] ← A[p + i − 1]
6. FOR j ← 1 TO n2
7. DO R[j] ← A[q + j ]
8. L[n1 + 1] ← ∞
9. R[n2 + 1] ← ∞
10. i ← 1
11. j ← 1
12. FOR k ← p TO r
13. DO IF L[i ] ≤ R[ j]
14. THEN A[k] ← L[i]
15. i ← i + 1
16. ELSE A[k] ← R[j]
17. j ← j + 1
@Anonymous is right... you see that the second array already has 3 blank spaces that can be used to record the final sorted array... you can merge sort each array in-place... and then merge the sorted arrays into the bigger array... this will be in-place and without using extra space
this approach may take lot of shifting but does not require any additional space
1-Sort the two array individually.
2-Then Merge both array in one by simple Comparing and shifting the element of 2nd Array
in worst case time complexity O(n2)
I think this is same as the last step of merge sort where we have two sorted arrays and then we just need to merge those.
public static void main(String[] args) {
int[] a = { 5, 4, 6 };
int[] b = new int[7];
b[0] = 13;
b[1] = 2;
b[2] = 1;
b[3] = 18;
b[4] = Integer.MIN_VALUE;
b[5] = Integer.MIN_VALUE;
b[6] = Integer.MIN_VALUE;
sortArray(a);
sortArray(b);
mergeArrays(a, b);
}
private static void mergeArrays(int[] array1, int[] array2) {
// TODO Auto-generated method stub
int j = 0, k = array1.length,i=0;
while(j<array1.length && k<array2.length) {
if (array1[j] > array2[k]) {
array2[i] = array2[k];
array2[k] = Integer.MIN_VALUE;
k++;
} else {
array2[i] = array1[j];
j++;
}
i++;
}
for(int i1=0;i1<array2.length;i1++)
{
System.out.println(array2[i1]);
}
}
private static void sortArray(int[] array) {
// TODO Auto-generated method stub
for (int i = 0; i < array.length; i++) {
for (int j = i+1; j < array.length; j++) {
if (array[i] > array[j]) {
array[i] = array[i] + array[j];
array[j] = array[i] - array[j];
array[i] = array[i] - array[j];
}
}
}
}
Hi All,
How about adding the elements of Array1 into array2 and then sort the Array2 using quicksort..
Is this something good..?
1)Sort the arrays
- Ramrott October 06, 20122)Merge them both,starting from the right end with the highest element,
by this way we avoid the shifting.