Software Engineer · Phone Screen · Coding

Microsoft — Software Engineer ✅ Passed

Level: Junior-Level

Round: Phone Screen · Type: Coding · Difficulty: 6/10 · Duration: 60 min · Interviewer: Neutral

Topics: Arrays, Stacks, Monotonic Stack

Location: Seattle, WA, US

Interview date: 2026-01-15

Summary

Round 1: Phone Screen

Question: I was asked two questions in my phone screen.

Details

I had a phone screen where I was asked two questions:

Question 1: Given an array p of length n, determine for each k (1 ≤ k ≤ n) whether there exists a contiguous subarray that contains exactly one permutation of the numbers 1 to k (regardless of order). If such a subarray exists, k is considered 'balanced'. The final output should be a binary string of length n, where the k-th position indicates whether k is balanced.

My Approach: The key is not to enumerate intervals, but to focus on the positional distribution of numbers 1 to k in the original array. First, record the index pos[x] for each number x. Starting from k = 1 and expanding upwards, dynamically maintain the leftmost position L and rightmost position R of the current 1..k.

For a given k, the condition to satisfy is: The minimum interval containing 1..k has a length of exactly k, i.e., R - L + 1 == k.

Question 2: Given an array of prices, prices, sell items from left to right. The final selling price of each item is determined as follows: Subtract the price of the first item to its right that has a price less than or equal to its own price from its original price. If there is no such item to the right, sell it at the original price.

The output should be two lines: The first line is the total selling price. The second line is the indices (0-based, ascending order) of all items sold at their original price.

My Approach: This is a standard problem of finding the "first smaller or equal element to the right." The approach involves using a monotonic stack.

Iterate through the array from right to left, maintaining a monotonically increasing stack (based on price): If the current price is greater than the top of the stack, pop elements from the stack until this is no longer the case. After popping, if the stack is not empty, the top of the stack is the first item to the right with a price ≤ the current price. If the stack is empty, it means there are no cheaper or equal items to the right, so the current item is sold at its original price.