Maximize profit with bounded sell window
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given an array prices[0..n-1] of daily stock prices and an integer D ≥ 1, you may perform at most one transaction (buy then sell). The sell day j must satisfy i < j ≤ min(i + D, n −
1) for the chosen buy day i. Return the maximum profit and the pair (i, j) achieving it; if no positive profit exists, return 0 and indicate that no transaction should be made. Design an O(n) time, O(
1) extra space algorithm, and discuss how you would adapt it for streaming input and for very large D.
Quick Answer: This question evaluates proficiency in array algorithms, time and space complexity analysis, and techniques for bounded-range optimization and streaming adaptation.