Microsoft SDE2 DSA Question
- Result
- no offer
- Posted
- 22 Aug 2025
Summary
Had an interview for the SDE2 position at Microsoft where I faced a DSA question. The problem involved finding the maximum profit from a contiguous subarray of length at most k. The solution required optimizing the approach beyond a brute force method.
How it went
I was asked to find the maximum possible profit from a contiguous subarray whose length is at most k. The problem was similar to the maximum subarray problem but with a constraint on the subarray length. The given solution had a time complexity of O(N*k), which I was supposed to optimize. I tried to think of a more efficient approach, but I couldn't come up with a better solution than the one provided. The problem also asked for similar questions on LeetCode or other coding forums, which I couldn't answer immediately.
Questions asked (1)
- 01
Maximum Profit with Subarray Length Constraint
data structures & algorithms · medium
You are given an integer array pnl of length n, where pnl[i] represents the profit or loss on day, you are also given an integer k. Your task is to find the maximum possible profit of any contiguous subarray whose length is at most k.