Amazon Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
The idea is simple:
Since both arrays are sorted, simply loop through until one of the array is finished. Take which ever is smaller (if we are making ascending order. If not, reverse this step and take the larger) and put it at the new larger list. Add remaining items if there is any left.
Code in Java:
public int[] merge(int[] a, int[] b){
int[] result = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while(j < a.length && k <b.length) result[i++] = a[j] < b[k] ? a[j++] : b[k++];
if(j < a.length) System.arraycopy(a, j, result, i, a.length - j);
else if(k <b.length) System.arraycopy(b, k, result, i, b.length - k);
return result
}
The idea here is to show you are using System.arraycopy() instead of simply assigning values from one array to another. Java's System.arraycopy() will use native faster memory copy function such as "memmove()".
public class Merge2SortedArray {
public static void main(String[] args) {
int a [] = { 1, 2, 8, 10, 19, 22, 28, 30 } ;
int b [] = { 1, 2, 3, 7, 11, 18, 25, 40, 45, 50 } ;
int c [] = merge ( a, b ) ;
for ( int i = 0 ; i < c.length ; ++i )
{
System.out.println ( c[i] ) ;
}
}
public static int [] merge ( int a [], int b[] )
{
int lena = a.length ;
int lenb = b.length ;
int res [] = new int [ lena + lenb ] ;
int j = 0 , i = 0, k = 0 ;
for ( k = 0 ; k < lena + lenb ; ++k )
{
if ( i < lena && j < lenb )
{
if ( a[i] <= b[j] )
{
res[k] = a[i++] ;
}
else
{
res[k] = b[j++] ;
}
}
else
{
if ( i == lena )
{
res[k] = b[j++] ;
}
else
{
res[k] = a[i++] ;
}
}
}
return res ;
}
}
void mergeArray(int result[], int arr1[],int size1,int arr2[],int size2)
{
int length=size1+size2;
int c=0,c1=0,c2=0;
while (c1!=size1||c2!=size2)
{
if(c1==size1&&c2!=size2)
{
result[c++]=arr2[c2++];
}
if(c2==size2&&c1!=size1)
{
result[c++]=arr1[c1++];
}
if(c1!=size1&&c2!=size2)
{
if(arr1[c1]<arr2[c2])
result[c++]=arr1[c1++];
else
result[c++]=arr2[c2++];
}
}
}
int main(){
int n=SI;
vector<int> a(n);
FOR(i,0,n)a[i]=SI;
int m=SI;
VI b(m); //vector<int> b(m);
FOR(i,0,m)b[i]=SI; // for(int i=0;i<m;i++)scanf("%d",&b[i]);
VI c;
int p1=0,p2=0;
int mini=min(m,n);
while(p1!=n && p2!=m){
if(a[p1]>b[p2]){
c.pb(b[p2]);p2++;
}
else {c.pb(a[p1]);p1++;}
}
FOR(i,p1,n)c.pb(a[i]);
FOR(i,p2,m)c.pb(b[i]);
FOR(i,0,sz(c))cout<<c[i]<<" ";cout<<"\n";
return 0;
}
static void Main(string[] args)
{
int[] arr1 = new int[] { 1, 3, 5, 7 };
int[] arr2 = new int[] { 2, 4, 6, 8, 9, 10, 11, 13, 15 };
int i = 0, j = 0; int m = arr1.Length;
int n = arr2.Length;
int[] finalArray = new int[m + n];
while ((i + j) < (m + n))
{
if (i != m && arr1[i] < arr2[j])
{
finalArray[i + j] = arr1[i];
i++;
}
else
{
finalArray[i + j] = arr2[j];
j++;
}
}
}
Integer[] a = { 0, 3, 4, 5, 6, 7, 8, 12,19, 51 };
Integer[] b = { 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 58 };
List<Integer> finalArray = new ArrayList(Arrays.asList(b));
finalArray.add(0, Integer.MIN_VALUE);
finalArray.add(finalArray.size(), Integer.MAX_VALUE);
int progress = 0;
for (int i = 0; progress < a.length; i++) {
if (a[progress] < finalArray.get(i)) {
finalArray.add(i, a[progress++]);
}
}
finalArray.remove(0);
finalArray.remove(finalArray.size()-1);
any good?
void mergeArray(int[] arr1, int[] arr2){
int length1 = arr1.length;
int length2 = arr2.length;
System.out.println("arr1" + Arrays.toString(arr1) );
System.out.println("arr2" + Arrays.toString(arr2) );
System.out.println();
int lengthFinal = length2 + length1;
int[] arrMerged = new int[lengthFinal];
int pos = 0, pos1 = 0, pos2 = 0;;
while (pos1 <= length1 -1 && pos2 <= length2 -1){
if(arr1[pos1] <= arr2[pos2]){
arrMerged[pos] = arr1[pos1];
pos1++;
}else{
arrMerged[pos] = arr2[pos2];
pos2++;
}
pos++;
}
while( pos1 <= length1 -1){
arrMerged[pos] = arr1[pos1];
pos1++;
pos++;
}
while( pos2 <= length2 -1){
arrMerged[pos] = arr2[pos2];
pos2++;
pos++;
}
System.out.println("Megred Array =" + Arrays.toString(arrMerged) );
}
void mergeArray(int[] arr1, int[] arr2){
int length1 = arr1.length;
int length2 = arr2.length;
int lengthFinal = length2 + length1;
int[] arrMerged = new int[lengthFinal];
int pos = 0, pos1 = 0, pos2 = 0;;
while (pos1 < length1 || pos2 < length2){
if( pos1 != length1 && arr1[pos1] <= arr2[pos2] ){
arrMerged[pos] = arr1[pos1];
pos1++;
}else{
arrMerged[pos] = arr2[pos2];
pos2++;
}
pos++;
}
System.out.println("Megred Array =" + Arrays.toString(arrMerged) );
}
int [] a = {1,3,4, 5,6,7,8};
int [] b={4,6,7,8,9,10,11,12,13,14,15};
int c = a.length+b.length;
int num = 0;
int[] d = new int[c];
for(int i=0;i<a.length;i++){
d[num] = a[i];
num++;
}
for(int j=0;j<b.length;j++){
d[num] = b[j];
num++;
}
for(int j=0;j<d.length;j++){
System.out.print(d[j] + " ");
}
int temp = d[0];
for(int k=0;k<d.length;k++){
for(int l=0;l<d.length-1;l++){
if(d[l+1]<d[l]){
temp = d[l];
d[l] = d[l+1];
d[l+1] = temp;
}
}
}
System.out.println();
for(int m=0;m<d.length;m++){
System.out.print(d[m]+ " ");
}
}
import java.util.Set;
import java.util.TreeSet;
public class ArrayMergeSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 1, 3, 4, 5, 6, 7, 8 };
int[] b = { 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
Set<Integer> treeSet = new TreeSet<Integer>();
for (int i = 0; i < a.length; i++) {
treeSet.add(a[i]);
}
for (int i = 0; i < b.length; i++) {
treeSet.add(b[i]);
}
System.out.println(treeSet);
}
}
public static void main(String[] args){
int[] A={3, 6, 9, 13, 15, 20};
int la=A.length;
int [] B={1, 2, 3, 5, 6, 10, 11, 14, 17, 18, 21, 23};
int lb=B.length;
mergeArr(A, la, B, lb);
}
static void mergeArr(int []A, int la, int[]B, int lb){
int j=0, i=0, k=0;
int [] C=new int [la+lb];
while(i<la && j<lb){
if(A[i]<B[j]){
C[k]=min(A[i], B[j]);
i++;
} else if(A[i]>B[j]){
C[k]=min(A[i], B[j]);
j++;
} else {
C[k]=A[i];
System.out.print(C[k]+" ");
C[++k]=B[j];
i++; j++;
}
System.out.print(C[k]+" ");
k++;
}
while(i<la){
C[k]=A[i];
System.out.print(C[k]+" ");
i++;
}
while(j<lb){
C[k]=B[j];
System.out.print(C[k]+" ");
j++;
}
}
static int min(int a, int b){
return a<b?a:b;
}
}
output: 1 2 3 3 5 6 6 9 10 11 13 14 15 17 18 20 21 23
import java.util.*;
public class Sorted_array {
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the first Array Length");
int n1,n2;
n1=sc.nextInt();
int[] a1=new int[n1];
System.out.println("Enter the second Array Length");
n2=sc.nextInt();
int[] a2=new int[n2];
System.out.println("Enter the first arry elements:");
for(int i=0;i<n1;i++)
a1[i]=sc.nextInt();
for(int i=0;i<a1.length;i++)
for(int j=i+1;j<a1.length;j++)
if(a1[i]<a1[j]){
int temp=a1[i];
a1[i]=a1[j];
a1[j]=temp;
}
System.out.println("Enter the second Array Length");
for(int i=0;i<n2;i++)
a2[i]=sc.nextInt();
for(int i=0;i<a2.length;i++)
for(int j=i+1;j<a2.length;j++)
if(a2[i]<a2[j]){
int temp=a2[i];
a2[i]=a2[j];
a2[j]=temp;
}
int[] a3=new int[n1+n2];
for(int i=0;i<n1;i++)
a3[i]=a1[i];
for(int i=0;i<n2;i++)
a3[n1+i]=a2[i];
for(int i=0;i<a3.length;i++)
for(int j=i+1;j<a3.length;j++)
if(a3[i]<a3[j]){
int temp=a3[i];
a3[i]=a3[j];
a3[j]=temp;
}
System.out.println("Sorted array:");
for(int i=n1+n2-1;i>=0;i--)
{
System.out.print(a3[i]+",");
}
}
}
static int[] MergeSortedArrays(int[] destination, int[] left, int[] right)
{
int leftInd = 0, rightInd = 0, destInd = 0;
while (leftInd < left.Length && rightInd < right.Length)
{
if (left[leftInd] <= right[rightInd])
destination[destInd++] = left[leftInd++];
else
destination[destInd++] = right[rightInd++];
}
while (leftInd < left.Length)
destination[destInd++] = left[leftInd++];
while (rightInd < right.Length)
destination[destInd++] = right[rightInd++];
return destination;
}
Code in PHP
function merge_arrays(array $input1, array $input2)
{
$input_index1 = $input_index2 = 0;
$merge_array = array();
while ($input_index1 < count($input1) && $input_index2 < count($input2)) {
if ($input1[$input_index1] <= $input2[$input_index2])
{
$merge_array[] = $input1[$input_index1];
$input_index1++;
} else {
$merge_array[] = $input2[$input_index2];
$input_index2++;
}
}
return $merge_array;
}
public class MergeArray{
/**
@Param arr1 sorted arr
@Param arr2 sorted arr
*/
public static <T extends Comparable<? super T>> T[] merge(T[] arr1, T[] arr2){
@SuppressWarnings("unchecked")
T[] merged = (T[])(Array.newInstance(arr1.getClass().getComponentType(), arr1.length+arr2.length));
int index1 = 0;
int index2 = 0;
for(int i = 0; i < merged.length ; i++){
if(index1 == arr1.length){
System.arraycopy(arr2, index2, merged, i, merged.length - i);
break;
}
if(index2 == arr2.length){
System.arraycopy(arr1, index1, merged, i, merged.length - i);
break;
}
T t1 = arr1[index1];
T t2 = arr2[index2];
if(t1.compareTo(t2) <= 0){
merged[i] = t1;
index1++;
}else{
merged[i] = t2;
index2++;
}
}
return merged ;
}
public static void main(String[] args){
Integer [] a = {1,3,4, 5,6,7,8};
Integer [] b={4,6,7,8,9,10,11,12,13,14,15};
Integer [] merged = MergeArray.merge(a, b);
System.out.println(Arrays.toString(merged));
}
}
import java.util.Arrays;
- Anonymous May 31, 2013public class MergingArrays {
public static void main(String arg[]) {
int [] a = {1,3,4, 5,6,7,8};
int [] b={4,6,7,8,9,10,11,12,13,14,15};
int [] c= 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]) {
c[k] = a[i];
i++;
k++;
} else {
c[k] = b[j];
j++;
k++;
}
}
while (i < a.length)
{
c[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
c[k] = b[j];
j++;
k++;
}
System.out.print(Arrays.toString(c));
}
}