Microsoft 26 New Grad SDE OA Interview Experience (2026) - Max Score Jumping Path & Reduce n to Zero, Offer

Problem: Start at index 0 of an array and end at index n - 1 . At each position you can move forward one step, or jump forward by p steps where p is any prime whose last digit is 3 . At every index you land on, including the start, you collect the score at that position. Return the maximum total collected score on any valid path from 0 to n - 1 .

Two things going on here. First, the set of legal jump lengths is small and bounded by n , because any jump beyond n - 1 is invalid. Precompute the set of primes up to n whose last digit is 3 using a Sieve of Eratosthenes, then filter to those ending in 3 and add the step-of-one option. Call that set steps .

Second, this is a one-dimensional DP. Let dp[i] be the maximum score achievable at position i along any legal path from 0. Initialize dp[0] to score[0] and everything else to negative infinity. For each i with a non-negative dp[i] , relax the state to every reachable j = i + s where s is in the steps set, taking the max against dp[i] + score[j] . Final answer is dp[n - 1] .

Runtime is roughly O(n |steps|) . The prime-ends-in-3 set is sparse, on the order of O(n / log n) , so the worst case is well within limits. The brute force path is a naive DFS over all jump paths that blows up exponentially, and that is exactly the fast-fail trap. Anyone who starts with DFS runs out of time on the third hidden test.

The trap I personally fell into on a practice run was forgetting to include the step-of-one option alongside the prime jumps. The statement reads "move right one step, or jump by a prime ending in 3," and I initially only built the prime set. Kept failing small cases until I re-read the prompt.

Practice it: [[problem/130?company=5|Max Consecutive Ones III]]

Round 2 — Minimum Operations to Reduce n to Zero

Problem: Given a positive integer n , each operation lets you add or subtract any power of two, meaning 2 i for any non-negative integer i . Return the minimum number of operations required to reduce n to exactly 0.

This is the Non-Adjacent Form of a binary number dressed up in interview clothes. The core observation is that if you look at n in binary from the low bit up, runs of consecutive 1 bits cost more to knock out one-at-a-time than they do to knock out by first adding 1 to bump the run into a higher zero bit, leaving just a single 1 further up.

The correct strategy processes n bit by bit from low to high. If the lowest bit is 0, right-shift and keep going (no operation cost). If the lowest bit is 1, look at the next bit. If the next bit is also 1, adding 1 turns the run of 1s into a carry that ripples up, leaving a single 1 higher up and costing one operation. If the next bit is 0, subtracting 1 clears the lowest bit cleanly for one operation. Either way you increment the operation count, adjust n , and loop until n is zero.

The subtle case is n = 3 , which is binary 11 . Subtracting 1 gets you to 10 then subtracting 2 gets you to 0 , two ops. Adding 1 gets you to 100 then subtracting 4 gets you to 0 , also two ops. Equivalent. But n = 7 , binary 111 , is three ops by the subtract-every-bit route and only two ops by adding 1 to get 1000 and then subtracting 8. That is where the greedy-adds-on-runs insight earns its keep.

Greedy here is provably optimal because the NAF representation is minimum-weight across all signed-binary representations of a positive integer. You do not need to prove it on the exam but you should trust it. Runtime is O(log n) .

I had no matching Microsoft question to link for pure bit-manipulation DP, so I recommend practicing this one against any arbitrary-base arithmetic problem rather than a Microsoft-specific one. If you are short on time, do not let the absence of a drill question make you skip the pattern; NAF reasoning shows up in enough places that it earns the prep time.

Strategy That Worked

The common new-grad failure on the Microsoft OA is spending fifteen minutes on T1 without writing code because you are worried about the brute force. Flip that. Write the straightforward DP in eight minutes, check it against the examples in two, and move on. The prime sieve is a ten-line function and should not be the thing you struggle with.

For T2, resist the urge to write a BFS over the state space. It works on small n but blows up past n around 10^6 . The greedy bit-level approach is both faster and shorter. If you find yourself sketching a visited-set and a queue, stop and think for sixty seconds about the representation.

Microsoft also scores heavily on code cleanliness. Variable names like jump lengths over j and remaining over x actually shift the reviewer's read of your submission, and on partial credit boundary cases it can push you up a band.

Result

Offer about seven weeks after I submitted the OA. Microsoft's new grad process was the least stressful of my cycle because the OA is genuinely passable and the onsite is structured. I will write a separate post on the onsite once I have caught up on sleep.

Tips

1. Sieve primes up to `n` before the DP. Sieve of Eratosthenes is ten lines and runs in linear-log time. Anything else is error-prone under pressure.
2. Always include the step-of-one in jump-problem step sets. The statement bundles it with the prime jumps and it is easy to miss on a fast read.
3. Know NAF for bit-manipulation problems. The add-1-to-clear-a-run insight unlocks a whole family of "minimize operations" puzzles that show up in Microsoft OAs, Amazon OAs, and Bloomberg OAs.
4. Pre-write your sieve and your bit-scan helpers in a notepad before the exam. Microsoft does not allow copy-paste into the editor for proctored sessions but it does not stop you from mentally rehearsing the template. Drill it.
5. Budget 25 minutes per problem and stop. With only 70 minutes and 2 problems you need fifteen minutes of slack for testing and re-reads. Do not burn it in the first problem.
6. Partial credit is real at Microsoft. A slow but correct DP on T1 scores materially better than a blank. Ship the naive version before you optimize.