Expedia Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
def merge_in_place(A, B):
"""Given two sorted array. A is of length 6 and B is 3. Both they contain 3 elements.
merge them into A in place"""
assert(len(A) == 6)
assert(len(B) == 3)
ai, bi, i = 2, 2, 5
while ai >= 0 or bi >= 0:
if bi < 0 or (ai >= 0 and A[ai] >= B[bi]):
A[i] = A[ai]
i -= 1
ai -= 1
elif ai < 0 or (bi >= 0 and B[bi] > A[ai]):
A[i] = B[bi]
i -= 1
bi -= 1
return A
public int[] MergeSortedArrays(int[] a1, int[] a2)
{
int i;
int m = a2.Length - 1;
int n = a1.Length - 1 - a2.Length;
if (a2[0] > a1[n])
{
for (i = 0; i < a2.Length; i++)
a1[i + 1 + n] = a2[i];
return a1;
}
for (int k = 0; m >= 0 && n >= 0; k++)
{
if (a1[n] > a2[m])
{
a1[a1.Length - 1 - k] = a1[n];
n--;
}
else
{
a1[a1.Length -1 - k] = a2[m];
m--;
}
}
if (n < 0 && m >= 0)
{
while (m >= 0)
{
a1[m] = a2[m];
m--;
}
}
return a1;
}
Need to merge the biggest element first(relative to end of arrayA to preserve in-place sorting:
public static int[] merge(final int[] arrayA, final int[] arrayB) {
for (int iterB = arrayB.length - 1, iterASelect = arrayB.length - 1, iterAInsert =
arrayA.length - 1; iterB >= 0;) {
if ((iterASelect >= 0) && (arrayB[iterB] >= arrayA[iterASelect])) {
arrayA[iterAInsert] = arrayB[iterB];
iterB--;
iterAInsert--;
}
else if ((iterASelect >= 0) &&
(arrayB[iterB] < arrayA[iterASelect])) {
arrayA[iterAInsert] = arrayA[iterASelect];
iterAInsert--;
iterASelect--;
}
else {
arrayA[iterAInsert] = arrayB[iterB];
iterB--;
iterAInsert--;
}
}
return arrayA;
}
void mergeSortedArrayInPlace(int[] bigger, int[] smaller) {
int i = bigger.length-1, j=smaller.length-1;
int k = bigger.length-1;
while(bigger[i] == 0) {
i = i-1;
}
while(i >= 0 && j >= 0) {
if(bigger[i] < smaller[j]) {
bigger[k] = smaller[j];
--k; --j;
}else {
bigger[k] = bigger[i];
bigger[i] = smaller[j];
--k; --i;
}
}
}
int[] function(int[] a, int[] b) {
int aSize = a.length;
int bSize = b.length;
int aIndex = aSize;
int bIndex = bSize;
for(int index = aSize-1; index >=0 ; index--) {
if(bIndex == 0) {
break;
} else if(aIndex == 0) {
a[index] = b[bIndex-1];
bIndex--;
} else if(a[aIndex-1] > b[bIndex-1]) {
a[index] = a[aIndex-1];
aIndex--;
} else {
a[index] = b[bIndex-1];
bIndex--;
}
}
return a;
}
Start from end
- seirgy August 29, 2012