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 Technical Screen rounds at Verkada.

What role is this question designed for?

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

Merge Sorted Arrays In Place | Verkada Coding Question

Merge Sorted Arrays In Place

Company: Verkada

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two non-decreasing integer arrays. - `A` has length `m + n`. - The first `m` elements of `A` are valid sorted numbers. - The last `n` elements of `A` are empty placeholders and should not be treated as real values. - `B` has length `n` and all of its elements are sorted. Merge all elements from `B` into `A` so that after the operation, `A` contains all `m + n` elements in non-decreasing order. Requirements: - Modify `A` in place. - Use `O(1)` extra space.

Quick Answer: This question evaluates array manipulation and in-place merging skills, specifically understanding sorted sequences, pointer/index management, and space-time trade-offs within array algorithms, and it falls under the Coding & Algorithms domain.

You are given two non-decreasing integer arrays, `A` and `B`. - `A` has length `m + n`. - The first `m` elements of `A` are valid sorted numbers. - The last `n` elements of `A` are placeholders and should not be treated as real values. - `B` has length `n` and all of its elements are sorted. Merge all elements from `B` into `A` so that `A` contains all `m + n` elements in non-decreasing order. You must modify `A` in place and use only `O(1)` extra space. For testing purposes, return the modified array `A` after performing the merge.

Constraints

0 <= m, n <= 100000
len(A) == m + n
len(B) == n
-1000000000 <= A[i], B[i] <= 1000000000 for valid elements
The first m elements of A are sorted in non-decreasing order
B is sorted in non-decreasing order

Examples

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

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

Explanation: Merge the two sorted lists [1,2,3] and [2,5,6]. The final sorted array is [1,2,2,3,5,6].

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

Expected Output: [1]

Explanation: There are no elements in B, so A stays unchanged.

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

Expected Output: [1]

Explanation: A has no valid initial elements, so the result is just B copied into A.

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

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

Explanation: After merging the sorted values from both arrays, the result is [-3,-2,-1,2,2,4].

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

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

Explanation: This case checks duplicates. The merged sorted array is [1,2,2,2,3].

Hints

If you merge from the front, you may overwrite values in `A` that you still need later.
Compare the largest unmerged elements from the end of both arrays and fill `A` from right to left.

Quick Overview

This question evaluates array manipulation and in-place merging skills, specifically understanding sorted sequences, pointer/index management, and space-time trade-offs within array algorithms, and it falls under the Coding & Algorithms domain.