Compute max profit across dated stock quotes
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an unsorted list of price records for multiple stocks, each record as (date, symbol, price). Dates may be repeated across different symbols. Design an algorithm to compute the maximum profit and an explicit trading plan under these rules:
(
1) You can hold at most one share across all symbols at any time.
(
2) You may perform unlimited buy/sell transactions, but every buy must occur on a strictly later date than the previous sell (no same-day buy-and-sell for profit), and short selling is not allowed.
(
3) Assume prices are daily closes; if duplicates or missing dates occur, specify how you handle them. Return:
(a) the maximum achievable profit, and
(b) the sequence of trades (for each trade, list buy date, buy symbol, buy price, sell date, sell price). Explain your algorithm, prove correctness, and analyze time and space complexity. Discuss edge cases such as unsorted input, duplicate (date, symbol) rows, and non-monotonic dates.
Quick Answer: This question evaluates a candidate's ability to reason about time-series and transaction-constrained optimization, including handling unsorted inputs, duplicate records, and constructing an explicit sequence of trades under ordering and no-short-selling constraints.
You are given an unsorted list of stock price records for multiple symbols. Each record is a tuple (date, symbol, price), where date is an integer day number. Dates may repeat across different symbols, and the input may be in any order.
Design a function that computes:
1. The maximum achievable profit.
2. One optimal trading plan.
Trading rules:
- You may hold at most one share total across all symbols at any time.
- You may complete unlimited buy/sell transactions.
- Every buy must happen on a strictly later date than the previous sell date. In particular, you may not sell and then buy again on the same date.
- Short selling is not allowed.
- Prices are daily closing prices.
Data-cleaning rules for this problem:
- If the same (date, symbol) appears multiple times, keep only the last occurrence from the input.
- Missing dates do not need to be filled in; a symbol can only be bought or sold on dates where it has a price record.
Return a tuple (max_profit, trades), where trades is a chronological list of trades. Each trade must be represented as:
(buy_date, buy_symbol, buy_price, sell_date, sell_price)
If no profitable trade exists, return 0 and an empty trade list.
A strong interview solution should also be able to justify correctness, explain why same-day switching is disallowed by the transition logic, and analyze time and space complexity.
Constraints
- 0 <= len(records) <= 200000
- Each record is (date, symbol, price) where date is an integer, symbol is a non-empty string, and price >= 0
- If duplicate (date, symbol) rows exist, only the last occurrence in the input is considered valid
Examples
Input: ([(3, 'A', 8), (1, 'A', 5), (2, 'A', 9), (4, 'A', 7), (5, 'B', 3), (7, 'B', 10), (6, 'B', 2)],)
Expected Output: (12, [(1, 'A', 5, 2, 9), (6, 'B', 2, 7, 10)])
Explanation: Buy A on day 1 and sell on day 2 for profit 4. Then buy B on day 6 and sell on day 7 for profit 8. Total profit is 12.
Input: ([(1, 'A', 1), (2, 'A', 5), (2, 'B', 1), (3, 'B', 5)],)
Expected Output: (4, [(1, 'A', 1, 2, 5)])
Explanation: You cannot sell A on day 2 and then buy B on day 2, because a buy must be on a strictly later date than the previous sell. So the best valid profit is 4, from trading A only.
Hints
- Normalize the data first: collapse duplicate (date, symbol) rows, then process dates in sorted order.
- Use dynamic programming with two kinds of states: the best profit when you end a date with no stock, and for each symbol the best profit when you end the date holding that symbol. Be careful: sells for a date must be evaluated before buys for that same date.