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 

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 

Finding whether 2 arrays are intersecting

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

Here are 2 arrays: **A1 1 8 7 5 6 A2 0 9 6 4 2 ** **These two are intersecting at 6. Complexity? ** Solution: This can be solved using Hash Tables. Take 1 Hash Table. Insert elements from A1 in Hast Table as key and put value in front of them (In case elemente get repeated increment the value count). Now traverse the second array A2 and check for element as a key. [Read More]
kodeknight  programming  array  two-arrays