How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding 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

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

### 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 1. Describe an efficient algorithm for this problem, including: - Data structures you would use. - Time and space complexity. 2. 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.)*

Quick Answer: 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.

You are given `k` sorted arrays of integers, where each `arrays[i]` is sorted in non-decreasing order. Merge them into a single sorted list containing all `N` elements. A naive approach that rescans every array head at each of the `N` steps costs O(N*k), which is too slow when `k` is large. Use a min-heap (priority queue) holding the current front element of each non-empty array. Repeatedly pop the smallest, append it to the output, and push the next element from the same source array. Each of the N elements is pushed and popped once, and the heap holds at most k entries, giving O(N log k) time. Write `solution(arrays)` that takes a list of `k` sorted integer lists and returns the merged sorted list. Example: Input: arrays = [[1, 4, 9], [2, 6], [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. - 0 <= N <= 10^6 total elements. - Integer values fit in 32-bit signed range. - Some input arrays may be empty; the overall list may be empty.

Constraints

1 <= k <= 10^5
0 <= N <= 10^6 total elements across all arrays
Each individual array length can be zero or more
Integer values fit in 32-bit signed range
Input arrays may be empty and the merged result may be empty

Examples

Input: ([[1, 4, 9], [2, 6], [0, 3, 7, 8]],)

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

Explanation: The example case: three sorted arrays merged into one fully sorted list.

Input: ([],)

Expected Output: []

Explanation: No arrays at all -> empty result.

Input: ([[]],)

Expected Output: []

Explanation: A single empty array -> empty result; the heap is never seeded.

Input: ([[5]],)

Expected Output: [5]

Explanation: One array with one element -> returned as-is.

Input: ([[1, 1, 1], [1, 1]],)

Expected Output: [1, 1, 1, 1, 1]

Explanation: All-duplicate values across arrays; ties are handled by the array/element index in the heap tuple.

Input: ([[-5, -1, 3], [-3, 0, 2], []],)

Expected Output: [-5, -3, -1, 0, 2, 3]

Explanation: Negative values plus an empty array interleaved correctly.

Input: ([[1, 2, 3], [], [4, 5, 6]],)

Expected Output: [1, 2, 3, 4, 5, 6]

Explanation: An empty array in the middle is skipped; the two non-empty arrays concatenate in order.

Hints

Use a min-heap (priority queue) that holds the current smallest unconsumed element of each non-empty array.
Store tuples of (value, array_index, element_index) so that after popping the minimum you know which array to advance.
Initialize the heap with the first element of every non-empty array, then loop: pop the minimum, append it, and push the next element from that same array until the heap is empty.
This yields O(N log k) — strictly better than the O(N*k) repeated-linear-scan approach when k is large.

Quick Overview

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.