Register | Login
RSS  RSS



Who Voted for this Question


Article

Answers

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 CMaster


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 CMaster


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



Log in to comment or answer questions or register here.


CommonInterview
Common Interview is a place to help people keep up with the latest trends in job interviewing. You can interact by asking interview questions or by providing answers and ratings. Choose from thousands behavioural, technical, testing or program management questions and interview puzzles.
Top Users
FOLLOW ONCommonInterview Twitter Account
Live