Microsoft Software Engineer Interview Experience — Online Assessment with a Balanced-Window and Monotonic-Stack Problem

Q1 — problem

You're given a permutation p of length n. For each k (1 ≤ k ≤ n), determine whether there's a contiguous subarray that is exactly a permutation of the numbers 1 through k (order doesn't matter). If one exists, call k "balanced." The final output is a length-n binary string, where the k-th digit says whether k is balanced.

Q1 — approach

The key isn't to enumerate subarrays — it's to focus on where the numbers 1 through k actually sit in the original array. First, record the index pos[x] of each number. Starting from k = 1 and expanding upward, dynamically maintain the leftmost position L and rightmost position R among 1..k. For a given k, the condition is just this: the minimum window that contains 1..k has length exactly k, i.e. R - L + 1 == k.

Q2 — problem

You're given a prices array. Selling items left to right, each item's final sale price follows this rule:

• Take the original price, and subtract the price of the first item to its right whose price is ≤ its own price
• If no such item exists to the right, it sells at the original price

The output has two lines: the first line is the total sale price; the second line is the indices (0-based, ascending) of all items that sold at their original price.

Q2 — approach

This is a standard "first element to the right that's smaller or equal" problem. The way to solve it is a monotonic stack. Traverse the array from right to left, maintaining a monotonically increasing stack (by price):

• While the current price is greater than the top of the stack, pop it
• After popping, if the stack isn't empty, the top is the first item to the right with price ≤ the current price
• If the stack is empty, there's nothing cheaper or equal to the right, so this item sells at its original price