Meta·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Meta ML engineer interview with a classic in-place merge problem. Nothing fancy, just one tight algorithmic question that punishes you if you haven't thought carefully about traversal direction.

Questions Asked (1)

You have two sorted arrays A and B. Array A has extra space at the end to fit all of B's elements. Merge B into A in-place so the result is sorted, using O(m+n) time and O(1) space. Walk through your approach and argue why it's correct.

Algorithms & Data Structures

Author's notes

The key move is starting from the back of both arrays instead of the front.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a three-pointer technique starting from the end of both arrays: compare the largest remaining elements and place the larger one at the end of A's buffer, moving backwards. This avoids overwriting unmerged elements in A and achieves O(m+n) time and O(1) space.

Pro tip: Emphasize that merging from the end is the key insight to avoid extra space; also mention edge cases like empty arrays and that the algorithm is stable if you choose B's element when equal.

1. Clarify inputs and constraints

Confirm that A has length m+n with the last n slots empty, B has length n, and both are sorted. State that the goal is to merge in-place with O(m+n) time and O(1) extra space.

2. Initialize pointers

Set i = m-1 (last valid element in A), j = n-1 (last element in B), and k = m+n-1 (last position in A's buffer).

3. Merge from the end

While i >= 0 and j >= 0, compare A[i] and B[j]; place the larger at A[k], then decrement the corresponding pointer and k. If equal, prefer B[j] to maintain stability.

4. Handle remaining elements

If j >= 0 after the loop, copy remaining B elements into A[0..j]. If i >= 0, the remaining A elements are already in place.

5. Argue correctness and complexity

Explain that each step places the largest remaining element in its final position, so the array remains sorted. Time is O(m+n) because each element is processed once; space is O(1) since only pointers are used.

Key Points to Mention

Merging from the end avoids overwriting unmerged elements in A.
Three pointers: i for A's valid part, j for B, k for the write position.
Time complexity O(m+n) because each element is compared and placed once.
Space complexity O(1) because only a constant number of pointers are used.
Edge cases: empty A or B, all elements of one array smaller than the other.
Stability: when elements are equal, taking from B first preserves relative order.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.