## Google Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
2
of 2 vote

1. construct a max(min) heap from first element of all array,
2. 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

Comment hidden because of low score. Click to expand.
0
of 0 votes

n = total number of element
m = number of array
O(n log m)

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

At step 4: we can improve it by repeating until heap size is greater than 1.

At the time when heap size is 1, it implies only one array is left. Simply dump all elements from the remaining array into merged output.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

O(nlogk) time, where n is number of integers, and k is number of sorted arrays.

Comment hidden because of low score. Click to expand.
0
of 0 votes

this is nlogn time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

We could do O(k logn) if we divide and conquer and merge the arrays in pairs.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

What this question needs is a definition of k and n.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, I meant 2 in the previous post

Comment hidden because of low score. Click to expand.
0
of 0 votes

how to get the array whose element is the one that is deleted from the min heap....nt able to implement it...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Loser tree

Comment hidden because of low score. Click to expand.
0
of 0 vote

zaphod is correct...its the right way to do it in minimum complexity

Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

IMO, Shell sort is the best to go with.

Comment hidden because of low score. Click to expand.
0
of 0 vote

why dont we just pairwise merge the arrays.
For N arrays, we will need log N steps.
Each step will be O(M), where M is the total number of elements.
So overall complexity O(M log N)

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(M log N) is optimal for this problem. If a linear time algorithm do exist, we could have considered a simple sorting problem as a n-way merging problem and achieve a linear time solution for sorting.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Pseudo Code will be something like as follows :

Merge (A[l..h]) {
if (l == h) return A[l];
B = Merge (A[l .. (l+h / 2)]);
C = Merge (A[l+h / 2 + 1 .. h]);
return MergeArray(B,C);
}
MergeArray() merges two array B and C.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

As some one said, why don't we simply merge 2 arrays at a time. It will be O(n), where n is total elements. It will need additional space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

ideone[dot]com/KXpiL

time complexity - O[m+n]

Comment hidden because of low score. Click to expand.
0
of 0 votes

This is to merge two arrays, the problem is to merge K arrays. :D

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More