← Back to blog Meta SDE NG VO Questions: Merge Sort Variant + Sliding Window Max
VO Meta

Meta SDE NG VO Questions: Merge Sort Variant + Sliding Window Max

2026-06-15

Meta's SDE New Grad VO doesn't just test whether you can write an algorithm—it tests how you read and frame a problem. Based on an oavoservice student's Meta SDE NG VO debrief, this post walks through two real questions: Q1 is a "non-typical" merge sort variant, and Q2 is the classic sliding window maximum (LeetCode 239). Together they cover the two most common follow-up patterns: "wrap existing logic" and "swap the data structure to optimize." At the end you'll find VO assist / VO proxy paths for anyone in a big-tech job search grinding problems.

1. Meta SDE NG VO Overview

Dimension Details
Format Remote video interview (Coderpad / shared editor)
Duration ~45 min per round, 2 coding questions
Language Your choice; most use Python
Focus Reading/framing the problem, edge cases, complexity, communication
Style Prompts may look "non-typical"—the real point is whether you spot the actual test

Meta NG coding rounds move fast: one round often means two problems in 45 minutes. The prompt isn't always a verbatim LeetCode problem—it's frequently deliberately wrapped to see whether you can peel back the shell and locate the core logic being tested.

2. Q1: A Non-Typical Merge Sort Variant (Input/Output Wrapping)

Problem

First a very simple ask: given a list, just sort it, in Python. The interviewer explicitly wants merge sort.

Then the follow-up: the list contains not only ints but also chars mixed in, and they all need to be sorted together.

Framing: What is he actually testing?

This is not a typical algorithm problem. When you hit a prompt that's been deliberately wrapped, the first thing to ask is—what is he really testing?

For this one, the point is clear: without touching the existing core algorithm, how do you do proper input/output handling? In plain terms, you build a layer like an "API gateway":

  1. On the way in, convert every char to an int with ord();
  2. Reuse the merge sort core untouched;
  3. On the way out, use chr() to turn the originally-char elements back.

Once you grab that point, the implementation has no tricks. The key is to extract the input/output wrapping into a separate function, keeping the merge sort body clean and the logic clear.

Python Solution

First the untouched merge sort core:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)

def _merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Then extract the I/O wrapping into a standalone function—merge sort stays the same:

def sort_mixed(items):
    # 1) Wrap input: record which positions were chars, encode to comparable ints
    encoded = []
    is_char = []
    for x in items:
        if isinstance(x, str):
            encoded.append(ord(x))
            is_char.append(True)
        else:
            encoded.append(x)
            is_char.append(False)

    # 2) Reuse the core, but keep track of which value was originally a char,
    #    so sort tuples of (value, was_char)
    pairs = list(zip(encoded, is_char))
    pairs = merge_sort(pairs)   # tuples compare by first field naturally

    # 3) Wrap output: decode the originally-char ones back with chr
    return [chr(v) if was_char else v for v, was_char in pairs]

Key idea: pack (value, was_char) into a tuple before feeding merge sort—tuples compare by the first field, so the core logic needs zero changes; on decode, the second field decides whether to chr() it back.

print(sort_mixed([3, 'a', 1, 'Z', 2]))
# [1, 2, 3, 'Z', 'a']   ord('Z')=90 < ord('a')=97

Time complexity: O(n log n) (dominated by merge sort). Space complexity: O(n) (encoded arrays + merge buffers).

3. Q2: Sliding Window Maximum (Monotonic Queue)

Problem

LeetCode 239. Given an integer array nums and a window size k, the window slides from the left one step at a time; return the maximum of each window as an array.

Framing: There's only one thing to optimize

The most intuitive approach recomputes the max of each window, giving O(nk). The key to any optimization is the idea: here the only thing you can really optimize is killing that k—dropping "find the max inside the window" from O(k) to O(1).

So the requirement is precise: a data structure that can

  1. keep only the elements that could still become a future max, in sorted order;
  2. get the max from the front in O(1), and insert new elements / pop smaller ones at the back in O(1).

The thing that satisfies both is a monotonic queue built on a deque (a monotonically decreasing queue).

Python Solution

Store indices in the queue; their values are monotonically decreasing front-to-back:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()      # stores indices; nums[dq] is decreasing
    res = []
    for i, x in enumerate(nums):
        # anything smaller at the back is useless now—pop it (keep decreasing)
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        # drop the front index if it slid out of the window
        if dq[0] <= i - k:
            dq.popleft()
        # once the window is formed, the front is the current max
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Three details: maintain monotonicity at the back (a smaller element can never out-rank a later, larger one, so drop it); check the front for sliding out of the window; only start recording answers once the index reaches k-1.

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Time complexity: O(n) (each index is pushed and popped at most once). Space complexity: O(k).

4. On-the-Spot Reminders

FAQ

Q1: How many questions per Meta SDE NG VO round, and how hard?

A coding round is usually ~45 min with 2 questions, mostly LeetCode Medium with occasional Medium-hard. The point isn't difficulty but reading, framing, and communication—prompts are often deliberately wrapped to test whether you can locate the real focus.

Q2: Is "merge sort with chars mixed in" an off-topic question? How do I prepare?

Not off-topic—it tests the engineering mindset of "do input/output wrapping without changing the core algorithm." Practice mapping general algorithms onto variant inputs, get comfortable with ord / chr and tuple packing for conversions, and extract the wrapping into a standalone function.

Q3: Why use a monotonic queue for sliding window maximum?

Because the only optimizable point is dropping "find the max inside the window" from O(k) to O(1). A monotonic queue (deque-based) gets the max from the front in O(1) and inserts/pops at the back in O(1), bringing O(nk) down to O(n)—the standard solution for this class of problems.

Q4: What platform does Meta VO use? Can I use Python?

Most rounds run in Coderpad or a shared editor, language of your choice, and the vast majority use Python. For timed mocks, line-by-line walkthroughs, or full VO assist / VO proxy support, see the path below.

Preparing for Meta SDE NG VO?

Meta NG coding rounds are fast and love to wrap their prompts—what they really test is framing, communication, and code organization. oavoservice offers full Meta prep: timed mocks on merge sort variants / sliding window / monotonic queue / hashing high-frequency questions, line-by-line framing and Coderpad walkthroughs, and predictions by NG question type. Coaches include senior big-tech engineers, with full VO assist / VO proxy support.

Add WeChat Coding0201 now to get Meta questions and coaching.

Contact