Microsoft OA Interview Experience (2026) - 4-Problem Walkthrough & Offer

Sort the array, then sweep two pointers. For each left index i , advance a right pointer j as far as possible while arr[j] - arr[i] <= k . The best window width across the sweep is the answer.

O(n log n) for the sort, O(n) for the sweep. I explained the equivalence (pairwise-diff <= k iff max-min <= k) out loud before coding so the interviewer could see the reduction.

Problem 3: Dominating XOR

Problem: Given an array of non-negative integers, find the number of subarrays where the XOR of all elements is strictly greater than the sum of the first and last elements of the subarray.

I stared at this one for about 4 minutes before I started coding. The key observation: XOR is always <= sum for non-negative integers (since XOR "loses" the carry bits that sum keeps). So XOR first + last is pretty restrictive.

For a subarray of length 1, XOR == first == last, so XOR is not first + last (which equals 2 first). Fail. For a subarray of length 2, XOR(a, b) = a + b - 2 (a AND b). So XOR a + b iff a AND b < 0, which is never. Fail. For length 3, XOR(a, b, c) vs a + c. The middle element b is only in the XOR. Big b values can dominate.

So the problem reduces to: count subarrays of length = 3 where the XOR of middle elements (everything except first and last) exceeds first + last - XOR(first, last) ... no wait. Let me redo.

XOR of [a, b1, b2, ..., bk, c] = XOR(a, b1, ..., bk, c). Let M = XOR(b1, ..., bk) . Then full XOR = a XOR M XOR c. The condition is a XOR M XOR c a + c .

For fixed endpoints (a, c), we want to count pairs (i, j) with a XOR M {i..j} XOR c a + c . This is still O(n²) pairs × O(n) for the middle XOR, which is O(n³) — too slow for n = 10^5.

I did not solve this one optimally in the OA. I wrote the O(n²) solution (iterate all (i, j) pairs, compute XOR with prefix XOR, check condition) knowing it would TLE on large cases. Got partial credit.

In retrospect, the trick is to use prefix XORs + some bitwise trie structure to count pairs satisfying the inequality faster. Not something I'd expect most candidates to get under time pressure.

Problem 4: Maximum Possible MEX

Problem: You have an array a and can perform up to k operations. In one operation, pick any element and change its value to anything. Maximize the MEX of the resulting array.

MEX (minimum excludant) is the smallest non-negative integer not in the array.

Observation: to achieve MEX = m, we need 0, 1, 2, ..., m-1 to all be present. Count how many of those are missing; that's how many operations we need. Binary search on m.

Actually, even simpler: sweep from 0 upward. Maintain a needed counter for missing values and a "free operations" counter. If the current value i is present, continue. If missing, use one of our k operations. If we run out of k , the MEX is i. If we make it through the whole array, the MEX is max(a) + 1 .

Wait, that's not quite right because we also have "excess" elements (duplicates of values already seen, or values above m) that we can freely convert. So the flow is:

1. Count frequencies. Count how many distinct values 0, 1, 2, ... are missing before the first gap.
2. Count excess (values duplicated or >= some threshold) — these are "free conversions."
3. We can afford to fill in missing values up to min(k, excess) — but wait, we can always convert elements, and `k` limits us. So the MEX is the largest `m` such that the count of missing values in `[0, m-1]` is <= `k`.

Implementation: build a set of present values, then sweep m from 0 upward, bumping a missing count each time m is absent. Return m the moment missing count exceeds k .

There's a subtlety: when we "change" an element, the array length stays the same, so we need enough elements to fill the MEX gap. If n < m , MEX can't be m (not enough slots). The bound is m <= n . I capped the loop at len(a) + 1 accordingly. O(n) after the set build, and I got this one in about 10 minutes.

What I Learned From the OA

Microsoft's 4-problem format rewards breadth over depth. You're better off getting partial credit on all four than fully solving three. Budget 20-22 minutes per problem on the first pass.

Problem 3 (Dominating XOR) is the type of problem designed to eat candidates' time. If you don't see the trick in 5 minutes, skip it and come back.

Phone Screen (45 min)

One coding problem: given a string, find the longest substring where every character occurs at least k times. Classic divide-and-conquer. Count characters in the current string. If every character already meets the threshold, the whole string is the answer. Otherwise pick any character below threshold, split the string around every occurrence, and recurse into the pieces; the answer is the max over the recursive results.

O(n 26) in the worst case. I walked through why the recursion terminates (each split strictly shrinks the string and removes at least one character class) and discussed the alternative sliding window with a "number of unique characters" constraint, which is trickier to get right.

Onsite Preview

Four rounds: two coding, one system design, one "as-appropriate" (could be a behavioral + technical hybrid). I won't go deep because the questions were close enough to the Microsoft writeups floating around — LRU cache implementation, an OS-flavored problem about process scheduling, design a notification system, and a behavioral round heavy on cross-team collaboration stories.

Practice it: [[problem/668?company=5|Shopping at Ozone Galleria Mall]]

Result

L62 offer (equivalent to mid-level IC). Standard Microsoft comp for the role, with a solid signing bonus. Recruiter turnaround was fast once the loop completed.

Tips

1. Budget 20 minutes per problem on the first pass. The 4-problem OA is a time-management test disguised as a coding test. The candidates who finish all 4 are rarely the ones who started with the hardest.
2. Binary search on the answer is a frequent pattern. The alloy problem, the team-size problem, and many Microsoft OA variants reduce to "what's the largest X such that some monotonic predicate holds?" If you see that shape, default to binary search.
3. For Problem 3 / Dominating XOR, skip and return. If a problem involves bitwise operations + subarrays and you don't see the trick in 5 minutes, move on. You'll come back with better odds after finishing the other three.
4. MEX problems reduce to counting missing values. Sort, sweep, count gaps. This pattern covers most MEX variations and is worth practicing once.
5. On CodeSignal, use their test-case runner aggressively. Don't hand-verify. Paste sample inputs into the console and run. The time you save on manual verification is worth more than the time you spend on edge case thinking.
6. For the phone screen, expect the classic divide-and-conquer problems. Longest-substring-with-k-repeats, max-subarray-sum, merge-k-sorted-lists — these are all in Microsoft's phone screen pool. Master them.

Microsoft's OA is one of the harder ones in the industry, but the onsite is relatively friendly once you're through. Push hard on the OA prep.