Common Interview Questions - Merging Arrays Interview Question

Comment #139

CMaster — Wed, 12 May 2010 21:17:24 MDT

By Gregor Burger Here is my solution i C/C++. #include #include 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; } }
0 Vote(s)

Comment #138

CMaster — Wed, 12 May 2010 21:16:16 MDT

By Tony Morris Using a library I am working on: using Fcs; public class M { public static void Main(string[] args) { var s = Show.AnyShow().IEnumerableShow; var a = List.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 Merge(List a, List b) { return a.IsEmpty ? b : b.IsEmpty ? a : a.Head < b.Head ? a.Head + Merge(a.Tail, b) : b.Head + Merge(a, b.Tail); } }
0 Vote(s)

Comment #137

CommonInterview — Wed, 12 May 2010 21:08:44 MDT

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; }
0 Vote(s)

Comment #33

lrreiche — Mon, 25 Jan 2010 22:51:35 MST

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++];
1 Vote(s)