Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
@suvrokroy : there are two problems if we in your approach ..
1) we can not increase the size of int array dynamically , so we can not put all the content to big array ...
2)If we want to use bubble sort we need to create a new array with content of both array , the complexity will be
N: length of first array
M length of second array
time : O((N+M)2) = O(n2)
space : O(M+N) = O(n)
The complexity of my solution is
time : O(M+N) = O(n)
space : O(M+N) = O(n)
@Jayanth : i have copied the executing code , it is working .
The code in link u have pointed is not proper , there are some differences between codes have a look at it .
I am assuming the initial two arrays are also sorted:
private static int merge(int[] longArray, int[] shortArray, int longUsed) {
int longTail = longUsed - 1;
int shortTail = shortArray.length - 1;
while (longTail >= 0 && shortTail >= 0) {
if (longArray[longTail] > shortArray[shortTail]) {
longArray[longTail + shortTail + 1] = longArray[longTail];
longTail--;
} else {
longArray[longTail + shortTail + 1] = shortArray[shortTail];
shortTail--;
}
}
while (shortTail >= 0) {
longArray[shortTail] = shortArray[shortTail];
shortTail--;
}
return shortArray.length + longUsed;
}
yes two sorted arrays merge to get sorted array
int[] merge(int[] a, int[] b){
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}
return answer;
}
and runtime complexity is o(m+n) m, n are array sizes
Array merge(Array A1, Array A2) {
int size = A1.size+A2.size, i=0, a1i=0, a2i=0;
Array MA(size);
A1.sort();
A2.sort();
whiile(a1i<A1.size && a2i<A2.size){
if(A1[a1i]<=A2[a21])
MA[i++] = A1[a1i++];
else
MA[i++] = A1[a2i++];
}
if(a1i<A1.size){
while(i<size){
MA[i++] = A1[a1i++];
}
} else if(a2i<A2.size){
while(i<size){
MA[i++] = A1[a2i++];
}
}
return MA;
}
Can anyone Explain why we are using:
if(array1.length -1 != i){
while(i<array1.length){
output[k++]=array1[i++];
}
}
if(array2.length -1 != j){
while(j<array2.length){
output[k++]=array2[j++];
}
}
import java.util.Collections;
import java.util.ArrayList;
import java.util.Arrays;
class MergeArrays {
public static void main(String[] args) {
int[] array1 = {10,9,8,7,6};
int[] array2 = {3,4,5,9};
ArrayList<Integer> arrayList = new ArrayList<Integer>(array1.length + array2.length);
for(int i=0; i< array1.length; i++) {
arrayList.add(Integer.valueOf(array1[i]));
}
for(int i=0; i< array2.length; i++) {
arrayList.add(Integer.valueOf(array2[i]));
}
Collections.sort(arrayList);
int[] mergedSortedArray = new int[arrayList.size()];
for (int i=0; i<arrayList.size(); i++) {
mergedSortedArray[i] = arrayList.get(i).intValue();
}
System.out.println("Resulting array: " + Arrays.toString(mergedSortedArray));
}
}
private static int[] mergeArray(int[] array1, int[] array2) {
- MVVSK December 12, 2012// TODO Auto-generated method stub
int[] output = new int[array1.length+array2.length];
int i=0,j=0 ,k=0;
while(i< array1.length && j<array2.length )
{
if(array1[i]<array2[j]){
output[k++]=array1[i++];
}
else{
output[k++]=array2[j++];
}
}
if(array1.length -1 != i){
while(i<array1.length){
output[k++]=array1[i++];
}
}
if(array2.length -1 != j){
while(j<array2.length){
output[k++]=array2[j++];
}
}
return output;
}