Union and Intersection of two sorted arrays

 Posted on July 30, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Find Union and Intersection of two sorted arrays Example For example, if the input arrays are: arr1[] = {1, 3, 4, 5, 7} arr2[] = {2, 3, 5, 6} Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}. Solution Algorithm Union(arr1[], arr2[]): For union of two arrays, follow the following merge procedure. Use two index variables i and j, initial values i = 0, j = 0 If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i. [Read More]
Adobe  kodeknight  merge  union  two-sorted-arrays  intersection 

Merge two sorted arrays - One having big enough buffer to hold another

 Posted on March 28, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Another way to ask same question Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. [Read More]
kodeknight  merge  sorting  two-arrays  two-sorted-arrays  CrackingTheCodingInterview  sorted-array  sorting-and-searching 

Merge two arrays efficiently - one sorted, another unsorted

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently. Solution Method 1 - Insert the elements in sorted array using binary search Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that. Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity. [Read More]
kodeknight  merge  union  sorting  array  two-arrays  two-sorted-arrays  sorted-array 

k-way merge - Merging k sorted arrays of n elements

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Given k sorted arrays of size n each, merge them and print the sorted output. Example: **Input:** k = 3, n = 4 arr = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; **Output:** 0 1 2 3 4 5 6 7 8 9 10 11 Method 1 - Merging from 1 array to other It does so by using the “merge” routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged. [Read More]
kodeknight  merge  divide and conquer  sorting  array  two-sorted-arrays  min-heap  sorted-array 

Median of 2 sorted arrays of equal size n

 Posted on September 13, 2011  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Question  There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Solution Before going to solution what is the median. What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. [Read More]
Adobe  kodeknight  Microsoft  yahoo  divide and conquer  Amazon  array  two-sorted-arrays  median  incomplete  two-arrays  sorted-array 

Intersection of two sorted lists or 2 sorted arrays

 Posted on May 20, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

For two sorted lists, 1, 2, 12, 15, 17, 18 1, 12, 14, 15, 16, 18, 20 intersection is bold numbers. Solution 1 : Brute force An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. [Read More]
kodeknight  link list  Single Link List  binary search  two-arrays  two-sorted-arrays  intersection  sorted-array 

Given two sorted arrays of size m and n respectively (m >> n), how to merge them together?

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Given two sorted arrays of size m and n respectively (m » n), how to merge them together? (Note: if you try to insert n numbers to the larger array to obtain O(n \log m) complexity, pay attention that you have to move elements around for insertions. Also, simply merging those two arrays is not the optimal solution here.) Solution Consider A[m+1] and B[n+1] and C[m+n] (m»n and indexing starts from 1) [Read More]
kodeknight  merge  sorting  array  two-arrays  two-sorted-arrays