Microsoft SDE 2 Interview Question: Stock Buy Sell

The Stock Buy and Sell problem is a popular coding interview question, especially at big tech companies like Microsoft.

This question tests your skills in breaking down problems, spotting patterns, and using dynamic programming techniques.

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 105

Solution

To solve the "Best Time to Buy and Sell Stock III" problem, we'll use dynamic programming to track the maximum profit at each stage, considering up to two transactions.

Here's the step-by-step approach:

📌 Initialization: Create variables to keep track of the cost of the first and second buy (first_buy, second_buy) and the profit from the first and second sell (first_sell, second_sell).

Initialize first_buy and second_buy to a large negative number to represent the cost, and first_sell and second_sell to 0 to represent profit.

📌 Iterate Through Prices: Loop through each price in the prices array.

📌 First Buy: Update first_buy to be the minimum of the current first_buy and the negative of the current price.

This represents the lowest price at which we could have bought the stock.

📌 First Sell: Update first_sell to be the maximum of the current first_sell and the current price plus first_buy.

This represents the maximum profit we could have made from the first transaction.

📌 Second Buy: Update second_buy to be the maximum of the current second_buy and first_sell minus the current price.

This represents the lowest net cost of buying the stock for the second transaction.

📌 Second Sell: Update second_sell to be the maximum of the current second_sell and the current price plus second_buy.

This represents the maximum profit we could have made from the second transaction.

📌 Result: After iterating through all prices, second_sell will hold the maximum profit achievable with up to two transactions.

Here's the Python code implementing this approach:

Here's the Python code implementing this approach:

def maxProfit(prices):
    first_buy, second_buy = float('-inf'), float('-inf')
    first_sell, second_sell = 0, 0

    for price in prices:
        first_buy = max(first_buy, -price)
        first_sell = max(first_sell, first_buy + price)
        second_buy = max(second_buy, first_sell - price)
        second_sell = max(second_sell, second_buy + price)

    return second_sell

# Example usage:
print(maxProfit([3,3,5,0,0,3,1,4]))  # Output: 6
print(maxProfit([1,2,3,4,5]))        # Output: 4
print(maxProfit([7,6,4,3,1]))        # Output: 0

Time Complexity: O(n), where n is the length of the prices array, as we iterate through the array once.

Space Complexity: O(1), as we only use a constant amount of extra space for the variables.

That's how you can solve the classic "Stock Buy Sell' dynamic programming problem asked in coding interviews at Microsoft.

If you're preparing for Microsoft or other product-based company interviews, I'd be happy to guide you through more such questions and help you strengthen your technical skills.

Click here to book a free 1:1 call.

Let’s connect and practice together!