How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Merge multiple sorted arrays using min-heap | Microsoft Interview Question

Q: Merge multiple sorted arrays using min-heap

This question evaluates algorithm design and data structure proficiency, focusing on merging multiple sorted sequences and reasoning about time and space complexity for large numbers of arrays and elements.

Problem

You are given k sorted arrays of integers:

arrays[0], arrays[1], ..., arrays[k-1]
Each arrays[i] is sorted in non-decreasing order.
The total number of elements across all arrays is N .

Your task is to merge these k sorted arrays into a single sorted array (or list) containing all N elements.

You should design an algorithm that is asymptotically optimal in terms of time complexity for large k and N. A straightforward approach that repeatedly scans all array heads at each step is too slow when k is large.

Output: a single sorted sequence of all elements from the k arrays.

Example

Input:

k = 3
arrays[0] = [1, 4, 9]
arrays[1] = [2, 6]
arrays[2] = [0, 3, 7, 8]

Output:

[0, 1, 2, 3, 4, 6, 7, 8, 9]

Constraints

1 <= k <= 10^5
Each array length can be zero or more.
Total number of elements N across all arrays: 0 <= N <= 10^6 (assume this upper bound for complexity discussion).
Integer values fit in 32-bit signed range.

Requirements

Describe an efficient algorithm for this problem, including:
- Data structures you would use.
- Time and space complexity.
Then implement the function that merges the arrays following your algorithm.

(Hint: Consider a priority-based data structure that efficiently gives you the smallest current element among the k arrays.)

Problem

You are given k sorted arrays of integers:

arrays[0], arrays[1], ..., arrays[k-1]
Each arrays[i] is sorted in non-decreasing order.
The total number of elements across all arrays is N .

Your task is to merge these k sorted arrays into a single sorted array (or list) containing all N elements.

Output: a single sorted sequence of all elements from the k arrays.

Example

Input:

k = 3
arrays[0] = [1, 4, 9]
arrays[1] = [2, 6]
arrays[2] = [0, 3, 7, 8]

Output:

[0, 1, 2, 3, 4, 6, 7, 8, 9]

Constraints

1 <= k <= 10^5
Each array length can be zero or more.
Total number of elements N across all arrays: 0 <= N <= 10^6 (assume this upper bound for complexity discussion).
Integer values fit in 32-bit signed range.

Requirements

Describe an efficient algorithm for this problem, including:
- Data structures you would use.
- Time and space complexity.
Then implement the function that merges the arrays following your algorithm.

(Hint: Consider a priority-based data structure that efficiently gives you the smallest current element among the k arrays.)

Merge multiple sorted arrays using min-heap

Quick Overview

Problem

Example

Constraints

Requirements

Comments (0)

Merge multiple sorted arrays using min-heap

Quick Overview

Problem

Example

Constraints

Requirements

Comments (0)