How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Maximize profit with bounded sell window | Microsoft Coding Question

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.

Given an array `prices[0..n-1]` of daily stock prices and an integer `D >= 1`, you may perform **at most one transaction** (buy on some day `i`, then sell on a later day `j`). The sell day must lie within `D` days of the buy day: `i < j <= min(i + D, n - 1)`. Return the maximum achievable profit together with the buy/sell day pair `(i, j)` that achieves it, as a list `[profit, i, j]`. If no transaction yields a **strictly positive** profit, return `[0, -1, -1]` to indicate that no transaction should be made. Design an algorithm that runs in **O(n) time and O(1) extra space** (aside from the bounded sliding-window structure, which holds at most `D + 1` indices). **Examples** - `prices = [3, 2, 6, 5, 0, 3]`, `D = 2` -> `[4, 1, 2]` (buy at index 1 for 2, sell at index 2 for 6). - `prices = [7, 6, 4, 3, 1]`, `D = 3` -> `[0, -1, -1]` (prices only fall; no positive profit). - `prices = [1, 2, 100]`, `D = 1` -> `[98, 1, 2]` (the window forbids buying at index 0 to sell at index 2). When several `(i, j)` pairs tie on profit, any optimal pair is accepted (the deque approach naturally returns the latest equal-or-cheaper buy index inside the window).

Constraints

1 <= D (the sell day j must satisfy i < j <= min(i + D, n - 1)).
0 <= n; n may be 0 or 1, in which case no transaction is possible -> [0, -1, -1].
Prices may be zero or negative (e.g. spread/relative values); profit is prices[j] - prices[i].
At most one transaction (one buy followed by one later sell).
Only strictly positive profit counts; ties on profit may return any optimal (i, j).

Examples

Input: ([3, 2, 6, 5, 0, 3], 2)

Expected Output: [4, 1, 2]

Explanation: Buy at index 1 (price 2), sell at index 2 (price 6) within the 2-day window; profit 4.

Input: ([7, 6, 4, 3, 1], 3)

Expected Output: [0, -1, -1]

Explanation: Prices are strictly decreasing, so no buy/sell pair gives positive profit -> no transaction.

Input: ([1, 2, 100], 1)

Expected Output: [98, 1, 2]

Explanation: With D=1 you cannot buy at index 0 and sell at index 2 (gap 2 > D). Best legal trade is buy at 1, sell at 2: 100 - 2 = 98.

Input: ([1, 2, 100], 2)

Expected Output: [99, 0, 2]

Explanation: With D=2 the window allows buying at index 0 and selling at index 2: 100 - 1 = 99.

Input: ([5], 3)

Expected Output: [0, -1, -1]

Explanation: A single day offers no sell opportunity; no transaction.

Input: ([], 1)

Expected Output: [0, -1, -1]

Explanation: Empty input -> no transaction possible.

Input: ([2, 2, 2, 2], 4)

Expected Output: [0, -1, -1]

Explanation: All prices equal, so every trade yields 0 (not strictly positive) -> no transaction.

Input: ([1, 5, 3, 8, 4], 1)

Expected Output: [5, 2, 3]

Explanation: With D=1 each sell day can only buy the previous day. Best is buy at 2 (price 3), sell at 3 (price 8): profit 5.

Input: ([10, 1, 1, 1, 1, 9], 4)

Expected Output: [8, 4, 5]

Explanation: Sell at index 5 (price 9); the cheapest legal buy in window [1,4] has price 1. The deque retains index 4 among the equal-priced candidates, giving the optimal profit 8.

Input: ([-3, -1, -10, 0], 2)

Expected Output: [10, 2, 3]

Explanation: Negative prices are allowed. Sell at index 3 (price 0); window [1,2] contains the minimum price -10 at index 2: profit 0 - (-10) = 10.

Hints

Fix the sell day j and ask: what is the cheapest buy day i allowed? It must lie in the sliding window [max(0, j - D), j - 1]. So this is a sliding-window-minimum problem, not the classic O(n) running-min trick (which would let you buy arbitrarily far in the past).
Maintain a monotonic deque of indices whose prices are increasing. The front is always the index of the minimum price in the current window. Before scoring day j, pop front indices that have fallen out of [j - D, j - 1].
Order matters: evaluate selling at j against the deque front FIRST (the front holds buy days strictly before j), THEN push j itself as a candidate buy day for the next D sell days. For streaming input, you only ever keep the last D prices' worth of deque entries, and for very large D the deque simply stops being a binding constraint (it degenerates to the standard track-the-running-minimum solution).

Quick Overview

This question evaluates proficiency in array algorithms, time and space complexity analysis, and techniques for bounded-range optimization and streaming adaptation.