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 Fora Travel.

What role is this question designed for?

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

Merge Sorted Arrays | Fora Travel Coding Question

Quick Overview

This question evaluates competency in implementing and generalizing merge operations on sorted arrays, exercising algorithmic problem-solving, array manipulation, handling of edge cases (empty arrays, negative numbers, duplicates), and analysis of time and space complexity.

Merge Sorted Arrays

Company: Fora Travel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two related tasks about sorted integer arrays. 1. Implement a function that takes two arrays sorted in nondecreasing order and returns a new sorted array containing all elements from both inputs. 2. Generalize the solution to merge K arrays, where each array is sorted in nondecreasing order, and return one sorted array containing all elements. Requirements: - Preserve duplicates. - Handle empty arrays, negative numbers, and arrays of different lengths. - Return a new array rather than mutating the inputs. - Discuss the time and space complexity of your approach.

Quick Answer: This question evaluates competency in implementing and generalizing merge operations on sorted arrays, exercising algorithmic problem-solving, array manipulation, handling of edge cases (empty arrays, negative numbers, duplicates), and analysis of time and space complexity.

Part 1: Merge Two Sorted Arrays

Given two integer arrays a and b sorted in nondecreasing order, return a new array containing all elements from both arrays in nondecreasing order. Preserve duplicates, handle empty arrays and negative numbers, and do not mutate the inputs.

Constraints

0 <= len(a), len(b) <= 100000
-1000000000 <= a[i], b[i] <= 1000000000
Both input arrays are already sorted in nondecreasing order
The solution must return a new array rather than modifying the inputs

Examples

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

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

Explanation: A standard merge of two equal-length sorted arrays.

Input: ([-3, -1, 2], [-2, 2, 2, 7])

Expected Output: [-3, -2, -1, 2, 2, 2, 7]

Explanation: Handles negative values, duplicates, and different lengths.

Hints

Keep one pointer in each array and compare the current elements.
After one array is exhausted, append the remaining elements from the other array.

Part 2: Merge K Sorted Arrays

Given a list of K integer arrays, where each array is sorted in nondecreasing order, return one new array containing all elements from all arrays in nondecreasing order. Preserve duplicates, handle empty arrays and negative numbers, and do not mutate the inputs.

Constraints

0 <= K <= 10000, where K is the number of arrays
0 <= total number of elements across all arrays <= 200000
-1000000000 <= arrays[i][j] <= 1000000000
Each inner array is already sorted in nondecreasing order
The solution must return a new array rather than modifying the inputs

Examples

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

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

Explanation: A classic example with three sorted arrays.

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

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

Explanation: Handles empty inner arrays, negative numbers, and duplicates.

Hints

At any moment, you only need to know the smallest current unused element from each array.
A min-heap can help you repeatedly extract the next smallest element in better than O(K) per step.

Quick Overview