Quick Overview

This question evaluates dynamic programming, algorithmic optimization, and complexity-analysis skills by requiring a bottom-up DP implementation that maximizes stock trading profit with at most k transactions while returning optimal buy-sell pairs under tie-breaking constraints.

Implement max profit with K transactions (DP)

Company: Citadel

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an array prices[0..n-1] of daily stock prices and an integer k, implement a bottom-up dynamic program to compute the maximum achievable profit with at most k buy-sell transactions (no overlapping positions). Requirements: (1) Return both the profit and the list of (buy_day, sell_day) pairs achieving it; break ties by lexicographically smallest sequence of pairs. (2) Time: O(nk), Space: O(k). (3) Handle edge cases k = 0, n < 2, and prices with plateaus. (4) Prove correctness via optimal substructure and explain how you avoid O(n^2 k).

Overview: This question evaluates dynamic programming, algorithmic optimization, and complexity-analysis skills by requiring a bottom-up DP implementation that maximizes stock trading profit with at most k transactions while returning optimal buy-sell pairs under tie-breaking constraints.

Read the full Citadel Data Scientist interview experience this question came from

Given an array prices where prices[i] is the stock price on day i and an integer k, write solution(prices, k) that returns a tuple (max_profit, transactions). transactions must be a list of at most k pairs (buy_day, sell_day), using 0-based day indices, such that buy_day < sell_day and consecutive transactions are strictly disjoint: b1 < s1 < b2 < s2 < .... Among all ways to achieve the maximum profit, return the lexicographically smallest transaction list. Compare two lists left to right by pair; compare pairs by buy_day first, then sell_day; if one list is a prefix of the other, the shorter list is smaller. Handle edge cases such as k = 0, n < 2, and plateaus in prices. Target a bottom-up dynamic program with O(nk) time and rolling O(k) numeric DP state; in the interview, be ready to justify optimal substructure and explain why maintaining the best buy balance avoids the naive O(n^2 k) scan over all earlier buy days.

Constraints

  • 0 <= len(prices) <= 10000
  • 0 <= k <= 100
  • 0 <= prices[i] <= 10^9
  • Transactions must satisfy buy_day < sell_day, and different transactions must be strictly disjoint in time.

Examples

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

Expected Output: (7, [(1, 2), (4, 5)])

Explanation: Buy on day 1 and sell on day 2 for profit 4, then buy on day 4 and sell on day 5 for profit 3. Total profit is 7.

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

Expected Output: (4, [(0, 1), (3, 4)])

Explanation: The best two disjoint transactions are (0,1) for profit 2 and (3,4) for profit 2, totaling 4.

Hints

  1. Use exact-transaction DP states: cash[t] for the best profit after exactly t completed transactions and no stock in hand, and hold[t] for the best balance after opening transaction t.
  2. The O(n^2 k) version tries every earlier buy day for every sell day. You can avoid that by carrying forward the best value of cash[t-1] - prices[i] as you sweep from left to right.

Loading coding console...