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.