## Clean Power Research Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

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.

``````void 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;
}
}``````

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

Typical question from cracking the code interview

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

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.

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

If I undestood it correctly, the question doesn't allow using a new array.

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

Ok, in that case instead of c[] use b[] and start putting elements from the back.

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

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

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

int* merge(int* a, int la, int* b, int lb) {
//la, lb - length of array a and b
int* o = new int[la + lb];

for (int i = 0, ia = 0, ib = 0; i < la + lb; i++) {
o[i] = (ia == la
? b[ib++] : (ib == lb
? a[ia++] : (a[ia] > b[ib]
? a[ia++] : b[ib++])));
}

return o;
}

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

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

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

How about just copying the first array in 2nd & using normal merge sort on 2nd.

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

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;

}``````

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

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

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

``````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;

}``````

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

``````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++;
}
}
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()){
}
}
}``````

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

``````#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;
}``````

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.