## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India

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

1)Sort the arrays
2)Merge them both,starting from the right end with the highest element,
by this way we avoid the shifting.

Comment hidden because of low score. Click to expand.
0

Good Solution.

Comment hidden because of low score. Click to expand.
0

Sort the arrays using heap sort, as it takes no extra space. Heap sort is better than quick sort as worst case of heap sort is O(nlogn), where as quick sort has worst case O(n2).

Comment hidden because of low score. Click to expand.
1
of 3 vote

Use Merge Sort .

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

@justcoding, merge sort needs extra space...

Comment hidden because of low score. Click to expand.
0

yes but you can do it in-place as well...

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

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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

but here we r not using extra array... merge sort requires extra space here we r using shifting op to merge within given space

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

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

}

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

Hi All,

How about adding the elements of Array1 into array2 and then sort the Array2 using quicksort..

Is this something good..?

Comment hidden because of low score. Click to expand.
0

I am not clear about the proposed solutions :
merge_sort and quicksort both have some space complexity.

May be we should add the 2 arrays (as mentioned in your solution) and do insertion sort (0(1) space complexity)?

Comment hidden because of low score. Click to expand.
0
of 2 vote

Use Heap sort.

Comment hidden because of low score. Click to expand.
0

Yes we can add array1 to array 2 and do a heap sort with order (m+n)log(m+n).

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

geeksforgeeks.org/archives/1355

Comment hidden because of low score. Click to expand.
0

Hi... As per the input, the given arrays are not sorted.

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

you just need to know how to swap 2 number without using extra space. Here is the algorithm:
int a = 2;
int b = 3;

int a = a + b; (now a == 5 , b == 3)
int b = a - b; (now a == 5 , b == 5-3 == 2)
int a = a - b; (now a == 5-2 == 3 , b == 2)

Then just quick sort it.

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.

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