Answers and Comments


User Avatar
Written by lrreiche


Furschlugginer editor!

I doubt this can be done on O(n). If n.eq.1, m.gt.0, and B[0].lt.A[0], then there will have to be m assignments after assigning C[0] = B[0]. Here is my solution on O(m+n).

a=0; b=0; c=0;
while ((a.lt.m) and (b.lt.n)) do
___C[c++] = (A[a].lt.B[b]) ? A[a++] : B[b++];
while (a.lt.m) do
___C[c++] = A[a++];
while (b.lt.n) do
___C[c++] = B[b++];


User Avatar
Written by CommonInterview


The solution if you think about it is quite simple, one of possible approaches would be:

1. Check if you exhausted one array. If so, take numbers from the other one and continue

2. If both arrays are in play, take the smaller element and increment indexer of the array which been used

3. Repeat



Here is the code in C#:


public static int[] Merge(int[] A, int[] B)
{
if ((A == null) || (A.Length == 0)) return B;
if ((B == null) || (B.Length == 0)) return A;

int index = 0;
int i = 0;
int j = 0;
int CountB = B.Length - 1;
int CountA = A.Length - 1;
int finalSize = A.Length + B.Length;
int[] C = new int[finalSize];

while (index <= (finalSize - 1))
{
if (i > CountA)
{
C[index] = B[j];
j++;
}
else
if (j > CountB)
{
C[index] = A[i];
i++;
}
else
{
if (A[i] < B[j])
{
C[index] = A[i];
i++;
}
else
{
C[index] = B[j];
j++;
}
}
index++;
}
return C;
}


User Avatar
Written by Job-Interview


By Tony Morris

Using a library I am working on:

using Fcs;

public class M {
public static void Main(string[] args) {
var s = Show<int>.AnyShow<int>().IEnumerableShow;

var a = List<int>.list(1, 3, 5, 5, 100);
var b = 2.To(9);
var c = Merge(a, b);
s.Println(c); // [1,2,3,3,4,5,5,5,6,7,8,9,100]
}

public static List<int> Merge(List<int> a, List<int> b) {
return a.IsEmpty
? b
: b.IsEmpty
? a
: a.Head < b.Head
? a.Head + Merge(a.Tail, b)
: b.Head + Merge(a, b.Tail);
}
}


User Avatar
Written by Job-Interview


By Gregor Burger

Here is my solution i C/C++.

#include <iostream>
#include <assert.h>

int *merge(int *A, int a_l, int *B, int b_l) {
assert(A);
assert(B);
int *AB = new int[a_l+b_l];
int a, b;
a = b = 0;
for (int i = 0; i < (a_l+b_l); i++) {
if ((A[a] < B[b] && a < a_l) || b >= b_l) {
AB[i] = A[a];
a++;
continue;
}
if ((A[a] >= B[b] && b < b_l) || a >= a_l) {
AB[i] = B[b];
b++;
continue;
}
}

return AB;
}

int main(int argc, char *argv[]) {
(void) argc;
(void) argv;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100};
int B[] = {2, 3, 4, 6, 8, 10, 12};

int a_l = sizeof(A)/sizeof(int);
int b_l = sizeof(B)/sizeof(int);

int *AB = merge(A, a_l, B, b_l);

for (int i = 0; i < (a_l+b_l); i++) {
std::cout << AB[i] << std::endl;
}
}


Saved Stories

Sponsored Categories





100 Common Interview Questions, audio book