Google Interview Question Software Engineer / Developers
0of 0 votesWrite a Code to merge N sorted array.
Zaphod : N arrays will have some elements as well right? If size is S of each array then compleity will be like : S*n*lgn
<pre lang="java" line="1" title="CodeMonkey91627" class="run-this">import java.util.*;
class KwayMerge
{
public static List<Integer> merge(List<List<Integer>> sortedLists) {
// estimate length
int size = 0;
for (List<Integer> list : sortedLists) {
size += list.size();
}
List<Integer> output = new ArrayList<Integer>(size);
Queue<Entry> queue = new PriorityQueue<Entry>(sortedLists.size());
// read first entry from each source
for (List<Integer> list : sortedLists) {
Iterator<Integer> it = list.iterator();
if (it.hasNext()) {
queue.add(new Entry(it.next(), it));
}
}
// process until queue becomes empty
while (!queue.isEmpty()) {
Entry entry = queue.poll();
Integer value = entry.getValue();
output.add(value);
if (entry.readNext())
queue.add(entry);
}
return output;
}
public static void main(String[] args) {
List<Integer> list1 = Arrays.asList(new Integer[] { 1, 3, 5, 7, 9 });
List<Integer> list2 = Arrays.asList(new Integer[] { 2, 4, 6, 8, 10 });
List<Integer> list3 = Arrays.asList(new Integer[] { 0, 1, 2, 3, 4, 5 });
List<List<Integer>> lists = new ArrayList<List<Integer>>();
lists.add(list1);
lists.add(list2);
lists.add(list3);
List<Integer> output = merge(lists);
System.out.println(output);
}
}
class Entry implements Comparable<Entry>
{
private Integer value;
private Iterator<Integer> it;
public Entry(Integer value, Iterator<Integer> it) {
this.value = value;
this.it = it;
}
public Integer getValue() {
return this.value;
}
public boolean readNext() {
if (it.hasNext()) {
value = it.next();
return true;
} else {
return false;
}
}
public int compareTo(Entry entry) {
return this.value - entry.value;
}
}
</pre>
<pre lang="java" line="1" title="CodeMonkey82853" class="run-this">//My Solution was n-way merge
class MergeNArray {
public static void main(String args[]) {
int[][] input = new int[4][];
input[0] = new int[] { 1, 2, 5, 74, 344 };
input[1] = new int[] { 1, 8, 12, 33, 90, 95 };
input[2] = new int[] { 9, 12, 17, 20, 91 };
input[3] = new int[] { 1, 3 };
int[] output = nWayMerge(input);
for (int i = 0; i < output.length; i++) {
System.out.print(output[i] + ",");
}
}
private static int[] nWayMerge(int[][] input) {
// TODO Auto-generated method stub
int[] output;
int n = 0;
for (int i = 0; i < input.length; i++) {
n = n + input[i].length;
}
output = new int[n];
int[] counter = new int[input.length];
int j = 0;
while (true) {
int index = compare(input, counter);
if (index == -1)
break;
else {
output[j++] = input[index][counter[index]];
counter[index]++;
}
}
return output;
}
private static int compare(int[][] input, int[] counter) {
// TODO Auto-generated method stub
int min = Integer.MAX_VALUE;
int index = -1;
for (int i = 0; i < input.length; i++) {
if (counter[i] < input[i].length && input[i][counter[i]] < min) {
min = input[i][counter[i]];
index = i;
}
}
return index;
}
}
</pre><pre title="CodeMonkey82853" input="yes">1
2
10
42
11
</pre>
@MaYank: How about the complexity of your code for n-way merge? Isn't it O(nk)?
How much time was given for the coding during the phone interview? For efficiency, you'd probably mention using a heap (that would take longer to code) to get an O(n logk) solution.
Could you pls explain your approach a little to get O(k logn) solution?
The method that I mentioned maintains a k-element heap (smallest element from each of k sorted list), and extract min from this heap takes O(log k); so a total of O(n logk) to get all n elements in sorted sequence. Thanks.
Well I started by telling him heap. I said we can use min heap of size n but then got confuse. I am still confuse with min heap
Say I start with heap of n size now I will remove min value now which value I will insert
Say array is
1,2,7,8
5,6,9,11
10,20,30
construct heap now of size 3
1,5,10
remove 1
now insert new item in heap which Item should I pick and if you say minimum of 2,6,20 then this is the same what I am doing.
Any one has answer let me know
Continue..
Second thing he said heap wont work and then I suggest him above Idea and He likes that and then asked me to code I have 20 min to code and was able to code in this way with some edge condition missing at that and I told him about that I need to think about it so he said that is fine.
Mayank, obviously you should pick 5, the element next to the one that you just deleted from the heap in that array. This implies that the elements of heap should store both the value, and the index of the array from which they come from.
Assuming M arrays of N elements each and that we have an array of M*N elements to merge these into
Merge the first two arrays placing the elements at the beginning of the big array.
Now merge the big array with the third from the rear and place them at the end of the big array.
Then with the forth while placing the elements at the beginning.
The number of operations would be 2N + 3N + 4N... + M*N. I am tempted to call this O(M*N).
Shouldn't it be totally dependent on the total size of the array. Say for example if the final array is of size m. Shouldn't the complexity be O(m lg m)??
It looks like it's a merge sort at half way state and in merge sort the complexity doesn't depend on the number of sorted arrays, it rather depends on the full size of the final array.
Please advise.
divide&conquer
static int[] simple_merge( int[] first, int[] second ) {
int i = 0;
int j = 0;
int[] result = new int[first.length + second.length];
while ( i < first.length && j < second.length ) {
if ( first[i] < second[j] ) {
result[i + j] = first[i++];
} else {
result[i + j] = second[j++];
}
}
while ( i < first.length )
result[i + j] = first[i++];
while ( j < second.length )
result[i + j] = second[j++];
return result;
}
static int[] merge( int[][] arrays, int low, int high ) {
if ( high == low ) {
return arrays[low];
} else if ( high - low == 1 ) {
return simple_merge( arrays[low], arrays[high] );
} else {
int middle = ( high + low ) / 2;
int[] left = merge( arrays, low, middle );
int[] right = merge( arrays, middle + 1, high );
return simple_merge( left, right );
}
}
let's say
a1 [1-n]
a2 [1-n]
.
.
.
an [1-n]
index[n] ={0} //keep track the current index of each array initialize with 0
Result[1-n^2]
int k=0
for(j=1 to n)
{
min =infinite;
ptr=-1;
for( i=1 to n )
{
{
if(a{i}[index[i]] < min)
{
min=a[i][index[i]];
ptr = i;
}
}
}
result[k++] = min;//store the result in final array
index[ptr] ++; //update the pointer of particular array
}
In order to merge K-sorted arrays, we can simply merge the sorted sub-arrays at the back of the
bigger array.
I've added comments in the code. just to give the idea how it works, it is not the optimized version and also make
some assumption but overall gives the clear idea of the algorithm.
// A little modified form of merge algorithm, it just keep track of the start position
// in the bigger array.
void merge(int left[], int right[], int n, int m, int a[], int start) {
int i = 0;
int j = 0;
while (i <n && j < m) {
if (left[i] < right[j]){
a[start++] = left[i++];
}
else {
a[start++] = right[j++];
}
}
while (i < n) a[start++] = left[i++];
while (j < m) a[start++] = right[j++];
}
// The algorithm is based on the merge-sort merge algorithm.
// what it actually does is simple it simply picks up the list and
// merge it at the end of the bigger array.
// a little arithematic for indexing is required.
// I've assume size of each sub-list to be 10 it can easily extends to different size lists.
// the logic is simple every time you perform the merge start from size of already merged list + size of new sub-list to be merged.
// The you need to remember two things at every iteration.
// first = size of array 'a', (i.e. elements that are present in array a)
// second = the starting index from where to start merging the new list to the existing list.
void merge_lists(int* lists[], int sz, int a[], int n)
{
// assume size of every sub-list = 10.
int m = 10;
// flag to keep track whether it's a first pass
// if yes then it simply
bool isFirstPass = false;
int iListIter = 0;
// copy the array directly to a.
while (sz > 0) {
// pick the list and merge it
int* left = lists[iListIter];
if (isFirstPass == false) {
iListIter++;
isFirstPass = true;
// merge two lists in the bigger array.
int* right = lists[iListIter];
merge(left, right, m, m, a, n - (iListIter + 1)* m);
sz--;
}
else {
merge(left, a + n - (iListIter * m), m, (iListIter * m), a, n - ((iListIter + 1)* m));
}
iListIter++;
sz--;
}
}
1. construct a max(min) heap from first element of all array,
- Zaphod July 08, 20102. extract a max(min) value from the heap and write to output
3. get one more element from array which the value extracted step 2 was in.
4. repeat until heap is not empty