Microsoft Online Assessment (OA)

The Microsoft Online Assessment (OA) is a timed coding test, usually on Codility or HackerRank, that many candidates take before the onsite. It is its own problem universe: a recurring bank of greedy, counting, and graph problems, graded on hidden test cases you never see. The trees, intervals, and design prompts that fill the onsite hardly ever surface here, and vice versa. Grind the standard onsite list and walk into the OA cold, and you get blindsided. Treat it as a separate prep track.

The Microsoft online assessment is its own problem universe. The questions that decide it are a recurring bank of greedy, counting, and graph problems that hardly ever surface at the onsite. Meanwhile the trees, intervals, and design prompts that fill the onsite hardly ever surface here. A candidate who grinds the standard Microsoft onsite list and walks into the OA cold gets blindsided. So treat the assessment as a separate prep track with its own short list of shapes to drill.

The format barely changes, though the org you applied to sets the details. You get a timed session on Codility or HackerRank, usually two or three problems inside 60 to 90 minutes. Your code runs against hidden test cases that you never see. So the bar is whether it compiles and passes every case the grader throws at it. That includes the empty input, the single element, and the all-same-letter string you forgot about.

How to read and clear the OA

The grading is mechanical, so approach it mechanically. Read the constraints before the prose. The bounds on input size tell you whether an O(n squared) scan passes or you need O(n log n). The alphabet size tells you whether you can index by character. Then list the edge cases the hidden tests will probe before you write a line. An empty string, a single character, every character identical, and the largest allowed input are the four that catch people. The visible example never includes them, and the grader always does.

Build a few inputs of your own and run them in the editor, since the hidden suite gives you no feedback beyond a pass count. A solution that handles the sample but crashes on the empty string scores as a fail on those cases. There is no partial credit for "almost." When a problem looks like one you have seen, name the family before you start typing. Most of the OA bank is a handful of ideas in fresh wrapping.

The Microsoft angle

Skipping the OA is the most common way strong candidates fall at the first hurdle. The bank leans greedy and counting, exactly what a tree-and-DP-heavy prep plan under-trains. Block out a few sessions on the recurring OA shapes here and keep them separate from your onsite drilling. The onsite rewards a clean class model and a narrated walk. The OA rewards one thing: a correct submission against tests you cannot see.

Asked at Microsoft

Three problems drawn straight from the recurring bank. The first is the no-three-in-a-row family in its cleanest form, so learning it once carries the other four wordings. The second is Max Network Rank, a graph-degree count that rewards reading "connected pair" correctly. The third is the minimum adjacent swaps to make a string a palindrome, a greedy two-pointer that hides a feasibility check. Build each in the editor against your own edge cases, the way you would have to under the grader, before you open the walkthrough.

1

Longest Happy String: No Three in a Row

MediumFrequently asked

Problem

You have a letters 'a', b letters 'b', and c letters 'c'. Build the longest string you can that contains no substring "aaa", "bbb", or "ccc", in other words no letter appearing three times in a row. You do not have to use every letter. Return any longest valid string, or "" if none can be built.

This is the cleanest member of the recurring no-three-in-a-row family. The same greedy idea answers the rest of the family: fewest deletions to remove every run of three, most insertions without creating a run of three, and the lexicographically constrained variants.

Input: a = 1, b = 1, c = 7

Output: "ccaccbcc"

Seven c's cannot sit together, so they break into runs of at most two, separated by the single a and b. One c is left unused because nothing remains to break a third pair.

Input: a = 2, b = 2, c = 1

Output: "ababc"

Every letter fits with no run of three, so all five are used.

How this uses the pattern

Always place the letter you have the most of, unless the last two characters are already that letter. In that case place one of the next-most-common letter to break the run, then come back. A max-heap keyed on remaining count makes "the most of" a single pop.

Longest Happy String: No Three in a Row

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: a=1, b=1, c=7Expected: "ccaccbcc"

Input: a=2, b=2, c=1Expected: "ababc"

Input: a=7, b=1, c=0Expected: "aabaa"

Input: a=0, b=0, c=0Expected: ""

Need a hint? (3 available)

The Microsoft angle

This is the highest-frequency OA item, and it recurs as about five differently-worded problems that share one greedy idea. Always spend the most-abundant letter, but never let it run to three. No search involved. Get the family fluent once and a large slice of the OA bank is handled, since the deletion, insertion, and lexicographic versions all reduce to the same place-the-biggest-unless-it-would-make-three step.

Take it further

A common variant asks for the fewest deletions to make an existing string have no run of three identical letters. That one drops the heap entirely: scan once, count the length of each run of equal characters, and for a run of length L you must delete L - 2 of them when L > 2. Sum those. The walkthrough builds it, since recognizing it as the same family is what this titling tests.

Show solution & walkthrough

2

Max Network Rank: Degree Counting

MediumFrequently asked

Problem

There are n cities numbered 0 to n - 1 and a list of bidirectional roads, where roads[i] = [a, b] connects cities a and b. The network rank of two different cities is the total number of roads directly connected to either city. A road that joins the two cities themselves is counted only once, not twice.

Return the maximum network rank over all pairs of cities.

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]

Output: 4

City 0 has degree 2 and city 1 has degree 3. They share the road [0,1], so their rank is 2 + 3 - 1 = 4, the maximum.

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]

Output: 5

Cities 1 and 2 each have degree 3 and share a road: 3 + 3 - 1 = 5.

How this uses the pattern

Count each city's degree (how many roads touch it). For a pair, the rank is the sum of the two degrees, minus one if a road connects them directly, since that road was counted in both degrees. Record connected pairs in a set so the overlap check is O(1).

Max Network Rank: Degree Counting

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: n=4, roads=[[0,1],[0,3],[1,2],[1,3]]Expected: 4

Input: n=5, roads=[[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]Expected: 5

Input: n=8, roads=[[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]Expected: 5

Input: n=2, roads=[[0,1]]Expected: 1

Need a hint? (3 available)

The Microsoft angle

This recurring OA graph item is graded entirely on the shared-road subtraction. The hidden tests lead with a directly-connected pair, where the joining road sits in both degrees and has to come off once. Keep a set of connected pairs and the fix is one O(1) lookup. Plain degree counting passes the sample and fails the grader.

Take it further

For large n, the brute-force pair scan is O(n squared), which can time out. A faster route notes the answer pairs the two highest-degree cities. Find the highest degree and how many cities reach it. If two or more cities share that top degree, check whether every such pair is connected. If any top pair is unconnected, the answer is twice the top degree, otherwise it is twice the top minus one. If only one city has the top degree, pair it with the best second-tier city. Sketched in the walkthrough.

Show solution & walkthrough

3

Min Adjacent Swaps to Palindrome: Greedy Two-Pointer

HardCommonly asked

Problem

Given a string s, return the minimum number of adjacent swaps needed to turn it into a palindrome. Each swap exchanges two characters that sit next to each other. If no rearrangement of s is a palindrome, return -1.

A string can be rearranged into a palindrome only when at most one character has an odd count.

Input: s = "mamad"

Output: 3

One sequence: "mamad" to "maamd" to "maadm" to "madam", a palindrome, in three adjacent swaps.

Input: s = "asflkj"

Output: -1

Six characters each appear once, so more than one has an odd count and no palindrome exists.

How this uses the pattern

Two pointers, left and right. For the character at left, scan inward from right to find its match, then bubble that match to the right end with adjacent swaps, counting each. If left's character is the lone odd one out, swap it one step toward the center first. Move both pointers in and repeat.

Min Adjacent Swaps to Palindrome: Greedy Two-Pointer

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: s="mamad"Expected: 3

Input: s="asflkj"Expected: -1

Input: s="ntiin"Expected: 1

Input: s="aabb"Expected: 2

Need a hint? (3 available)

The Microsoft angle

This recurring OA problem hides a feasibility gate in front of a greedy. The hidden tests lead with the impossible case: a string with two or more odd-count characters. A solution that dives into swapping without the odd-count check returns a number instead of -1 and fails on the first test. Check feasibility, then run the greedy two-pointer. The greedy is provably minimal, so there is no search.

Take it further

Why the greedy is optimal is the natural probe. Fixing the outer pair first never wastes a swap, because the matching character has to reach the boundary eventually and moving it now costs exactly the distance it must travel. The lone odd character, when it blocks a match, is nudged one step toward the center and resolved later as the middle. Reasoning through why no rearrangement beats this is in the walkthrough.

Show solution & walkthrough