Amazon Interview Question for Software Engineer / Developers


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.

- Ramrott October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good Solution.

- pradegup October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dontulakapil November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Use Merge Sort .

- Anonymous October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kavita.123green October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- JustCoding October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@justcoding, merge sort needs extra space...

- Anonymous October 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JustCoding October 07, 2012 | Flag
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)

- kuldeep October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- aka October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kuldeep October 06, 2012 | Flag
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];
}
}
}

}

- kavita.123green October 06, 2012 | Flag Reply
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..?

- gdsrinivasan October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)?

- freeninza October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use Heap sort.

- Yuvaraj October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dontulakapil November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Follow this link:
geeksforgeeks.org/archives/1355

- Aashish October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gdsrinivasan October 07, 2012 | Flag
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.

- Anonymous October 07, 2012 | 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