## Amazon Interview Question

Software Engineer / Developers**Country:**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.