Merge two sorted arrays in-place
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You are given two nondecreasing arrays A and B, where A has enough trailing empty slots to hold all elements of B. Merge B into A in-place so that A remains sorted. Describe and implement an algorithm that runs in O(m+n) time and O(
1) extra space, and argue correctness.
Quick Answer: This question evaluates proficiency in array manipulation, in-place algorithms, and reasoning about time and space complexity when merging sorted sequences.
Merge sorted B into A, where A has trailing slots, and return A after the in-place merge.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3,None,None,None], 3, [2,5,6], 3)
Expected Output: [1, 2, 2, 3, 5, 6]
Explanation: Merge from the back into trailing slots.
Input: ([None], 0, [1], 1)
Expected Output: [1]
Explanation: Empty A prefix is supported.
Input: ([1], 1, [], 0)
Expected Output: [1]
Explanation: Empty B leaves A unchanged.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.