Clean Power Research Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Assume that both arrays are integers in ascending order. A self documenting code example for array merge is given below:
public int[] merge(int[] a, int[] b) {
int N = a.length+b.length;
int [] c = new int[N];
for (int k=0, i=0, j=0; k < N; k++) {
if (i == a.length) c[k] = b[j++];
else if (j == b.length) c[k] = a[i++];
else if (a[i] > b[j]) c[k] = b[j++];
else c[k] = a[i++];
}
return c;
}
Can be used for any comparables.
class arraymerge
{
public int[] merg(int[] arr1, int[] arr2)
{
int[] arr3 = new int[arr1.Length + arr2.Length-1];
int i=0;
int j=0;
int k=0;
for ( i = 0, j = 0, k = 0; i < arr1.Length - 1 && j < arr2.Length - 1; k++)
{
if (arr1[i] <= arr2[j])
{
arr3[k] = arr1[i];
i++;
}
else
{
arr3[k] = arr2[j];
j++;
}
}
while(i<arr1.Length)
{
arr3[k]=arr1[i];
k++;
i++;
}
while(j<arr2.Length-1)
{
arr3[k] = arr2[j];
j++;
k++;
}
return arr3;
}
}
public int[] merge(int[] a1, int[] a2) {
int[] tarr = new int[a1.length + a2.length];
for (int t = 0, i1 = 0, i2 = 0; t < tarr.length; t++) {
if(i1 < a1.length && i2 < a2.length){
if(a1[i1]<=a2[i2]){
tarr[t] = a1[i1++];
} else {
tarr[t] = a2[i2++];
}
} else if(i1 >= a1.length){
tarr[t] = a2[i2++];
} else if(i2 >= a2.length){
tarr[t] = a1[i1++];
}
}
return tarr;
}
Another way of implementing it to start comparing it from the back.
public int[] mergeArray(int [] arrayA, int [] arrayB){
if(arrayA.length < 1 || arrayB.length < 1)
return null;
int length_of_arrayA = arrayA.length;
int length_of_arrayB = arrayB.length;
int index_of_arrayA = length_of_arrayA - length_of_arrayB - 1;
/*get the index of last element in A, as array A has space to accommodate both so it will be having some empty elements.*/
int index_of_arrayB = length_of_arrayB - 1;
int index_of_merge = length_of_arrayA -1;
while(index_of_arrayB >=0){
if (arrayB[index_of_arrayB] > arrayA[index_of_arrayA]){
arrayA[index_of_merge] = arrayB[index_of_arrayB];
index_of_arrayB --;
} else{
arrayA[index_of_merge] = arrayA[index_of_arrayA];
index_of_arrayA --;
}
index_of_merge --;
}
return arrayA;
}
In case that array 2 is long enough to accommodate both of the arrays then its is filled its size minus array 1's size. (len2-len1 = biggest number on array 2)
int* mergeSort(int* arr1, int len1, int* arr2, int len2)
{
int* runner = arr2 + len2 -1; //will mark the cell we want to place the bigger number
int realLen2 = len2 - len1; //the actual length of array2- the values for the merge
int* endOfArr1 = arr1 + len1 -1; //the end of array1 which is the biggest number.
int* endOfArr2 = arr2 + realLen2 -1; //the biggest number on array2
//run until you reach the end of one of the arrays
//it will always be completely sorted by then.
while(len1 > 0 && realLen2 > 0)
{
if(*endOfArr1 >= *endOfArr2)
{
*runner = *endOfArr1;
endOfArr1--;
len1--;
}
else
{
*runner = *endOfArr2;
endOfArr2--;
realLen2--;
}
runner--;
}
//in case there are leftovers in array1 merge them (in case all array1 is smaller)
while(len1 > 0)
{
*runner = *endOfArr1;
endOfArr1--;
len1--;
runner--;
}
return arr2;
}
public static int[] mergeTwoSortedArraysWithoutAdditionalArray(int[] arr1, int[] arr2){
if((arr1 == null || arr1.length == 0 ) && (arr2 == null || arr2.length == 0)){
return null;
}
int a1Index = arr1.length-1;
int a2Index = arr2.length-1;
int a2mIndex = arr2.length-arr1.length-1;
while(a1Index >=0 && a2Index >=0 && a2mIndex >=0){
if(arr1[a1Index] > arr2[a2mIndex]){
arr2[a2Index] = arr1[a1Index];
a2Index--;
a1Index--;
}else{
arr2[a2Index] = arr2[a2mIndex];
a2Index--;
a2mIndex--;
}
}
while(a1Index > 0){
arr2[a2Index] = arr1[a1Index];
a2Index--;
a1Index--;
}
while(a2mIndex > 0){
arr2[a2Index] = arr2[a2mIndex];
a2Index--;
a2mIndex--;
}
return arr2;
}
class Solution{
public<T extends Comparable<T>> ArrayList<T> merge(ArrayList<T> first, ArrayList<T> second){
if (first == null || second == null){
throw new IllegalArgumentException();
}
ArrayList<T> result = new ArrayList<T>();
int fInd = 0 , sInd = 0;
T minElement;
while(fInd < first.size() && sInd < second.size()){
if (first.get(fInd).compareTo(second.get(sInd)) < 0){
minElement = first.get(fInd);
fInd++;
}
else{
minElement = second.get(sInd);
sInd++;
}
result.add(minElement);
}
copy(first , result , fInd);
copy(second , result , sInd);
return result;
}
private<T> void copy(ArrayList<T> from, ArrayList<T> to, int fromInd){
while(fromInd < from.size()){
to.add(from.get(fromInd++));
}
}
}
#include<iostream>
void swap(int* num1, int* num2)
{
int nTemp = *num1;
*num1 = *num2;
*num2 = nTemp;
}
void reverseArray(int* nArray, int nStart, int nEnd)
{
while(nStart < nEnd)
{
swap(nArray + nStart, nArray + nEnd);
nStart++;
nEnd--;
}
}
int main()
{
int nArray1[] = {1, 5, 8, 9, 15};
int nArray2[8] = {2, 4, 14};
int nLength1 = sizeof(nArray1) / sizeof(int);
int nLength2 = 3;
int i = 0;
int j = 0;
int k = nLength2;
while(i < nLength1 && j < nLength2)
{
if(nArray1[i] < nArray2[j])
{
nArray2[k] = nArray1[i];
i++;
}
else
{
nArray2[k] = nArray2[j];
j++;
}
k = (k + 1) % 8;
}
while(i < nLength1)
{
nArray2[k] = nArray1[i];
i++;
k = (k + 1) % 8;
}
while(j < nLength2)
{
nArray2[k] = nArray2[j];
j++;
k = (k + 1) % 8;
}
reverseArray(nArray2, 0, nLength2 - 1);
reverseArray(nArray2, nLength2, 7);
reverseArray(nArray2, 0, 7);
std::cout << "Array after merging\n";
for(int i = 0; i < 8; i++)
{
std::cout << nArray2[i] << std::endl;
}
return 0;
}
The trick is to store values into the empty end of the larger array inwards. This way you'll never store to a position whose value hasn't been evaluated. Assuming arrays are in ascending order and the empty end of the array A is at the right.
- Victor January 21, 2015void merge(int * restrict A, int nA, int * restrict B, int nB) { int k = nA - 1; int j = nB - 1; int i = nA - nB - 1; while (k >= 0) { if (i < 0) { A[k] = B[j]; --j; } else if (j < 0) { A[k] = A[i]; --i; } else if (A[i] > B[j]) { A[k] = A[i]; --i; } else { A[k] = B[j]; --j; } --k; } }