Microsoft·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Microsoft SWE interview with a tricky stock trading problem that had a constraint I hadn't seen before. The D-day window restriction turned the usual buy-low-sell-high problem into something that actually required some thought.

Questions Asked (1)

Given an array of daily stock prices and an integer D, find the maximum profit from at most one buy-sell transaction where the sell must happen within D days of the buy. Return the best profit and the buy/sell indices, or 0 if no profitable trade exists. Your solution must run in O(n) time with O(1) extra space. Also discuss how you'd handle streaming input and very large D.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The window constraint is what makes this non-trivial.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints, then present an O(n) sliding window solution using a deque to maintain the minimum price within the last D days, tracking the best profit and indices. Finally, discuss how to adapt the solution for streaming input and very large D by using a circular buffer or online algorithm.

Pro tip: Emphasize that the deque approach naturally handles the 'within D days' constraint and can be extended to streaming by processing each price as it arrives, maintaining only the necessary state. Mention that for very large D, the window effectively covers the entire history, so you can simplify to a running minimum.

1. Clarify requirements and edge cases

Confirm that D is the maximum number of days between buy and sell (inclusive), and that only one transaction is allowed. Discuss edge cases: empty array, D=0, no profitable trade, and large D.

2. Design O(n) time, O(1) space algorithm

Use a monotonic deque to maintain indices of potential buy days (minimum prices) within the window of the last D days. Iterate through prices, update the deque, and compute profit for each sell day.

3. Track best profit and indices

Maintain variables for max profit, best buy index, and best sell index. Update them whenever a higher profit is found.

4. Handle streaming input

Process each price as it arrives, updating the deque and best profit on the fly. Since the window size is D, the deque size is bounded by D, but for streaming we only need to store up to D elements; however, if D is very large, we can use a running minimum instead.

5. Address very large D

If D >= n, the constraint is irrelevant; we can just track the minimum price seen so far and compute profit. For streaming with large D, maintain a running minimum and its index, updating best profit accordingly.

Key Points to Mention

Monotonic deque for sliding window minimum
Time complexity O(n) and space complexity O(1) (deque size bounded by D, but D can be large; however, we can argue O(1) if we consider D as constant or use a running minimum for large D)
Handling streaming input: process each price online, update state incrementally
Very large D: simplify to running minimum approach
Edge cases: no profit, D=0, empty array
Returning indices along with profit

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.