Merge 'k' sorted arrays, each array may have max 'n' elements

Question

eqeuny · Accepted Answer

Complexity for 1st solution is wrong:

Let's assume that each array has n elements. When we doing first merge, we do O(n + n )operation. Second merge requires O(n+n+n) operations, Third O(3*n + n) operation.
1. 2*n
2. 3*n
3. 4*n
....
k-1. k*n
So the total time wil be O(n*k*k)

jalaj · Answer

@Interview Candidate:  space is O(k) for second method

the_strider · Answer

You can use priority queue to find min from k elements at any time in O(logk). Total number of lookups will be n * k, so the running time is O(n*k*logk). PHP already has SplPriorityQueue which is implemented using heap:

 $p2) return -1;
    return 0;
  }
}

$arrays = array(
  0 => array(1, 5, 8, 9, 10, 15),
  1 => array(-5, 6, 6, 7, 9, 90, 111),
  2 => array(-5, 6, 6, 7, 9, 90, 111),
  3 => array(9999),
);

$n = count($arrays);
$indices = array();
$queue = new MinPriorityQueue;
for ($i = 0; $i insert($i, $arrays[$i][0]);
  $indices[$i] = 0;
}
$result = array();
while (!$queue->isEmpty()) {
  $index = $queue->extract();
  $result[] = $arrays[$index][$indices[$index]++];
  if (isset($arrays[$index][$indices[$index]])) {
    $queue->insert($index, $arrays[$index][$indices[$index]]);
  }
}
print_r($result);

Anonymous · Answer

two solutions
1) Do it like merge sort's reduce step, O(nk) running time and O(nk) space
2) Create min heap out of heads of the arrays and keep extracing mins and adding the next entries from whichever array  min-value was extracted. O(nk logk) running time and O(log k) space

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?