Katkat
Back

Maximum Profit from Multi-Stock Trading Records

RampSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates a candidate's ability to parse and sort unstructured event data, then apply a greedy or dynamic-programming strategy for maximizing profit across multiple independent series. It falls under coding and algorithms, commonly used to assess array processing, state tracking, and stock-trading pattern recognition at a practical implementation level.

Maximum Profit from Multi-Stock Trading Records

You are given a list of stock price records collected from a trading feed. Each record is a triple:

  • date — the trading day, a string in ISO YYYY-MM-DD format (lexicographic order equals chronological order).
  • stock — the ticker symbol, a string (e.g. "AAPL").
  • price — the closing price of that stock on that day, a non-negative integer.

The records arrive unsorted — they are not in date order, and records for different stocks are interleaved. For any single stock there is at most one record per day (each (stock, date) pair is unique).

You may trade according to these rules:

  • You may buy and sell any number of times (unlimited transactions).
  • You may hold several different stocks at the same time, so the stocks are independent of one another.
  • For a single stock you must buy before you sell, and you may hold at most one unit of it at a time — you must sell your current unit of that stock before buying it again. You buy and sell at that day's price.
  • Buying and selling carry no fees, and you start and must end holding nothing.

Compute the maximum total profit achievable across all stocks, summed over every transaction. Return a single number (the profit; 0 if no profitable trade exists).

Example

records = [
 ["2024-01-03", "AAPL", 7],
 ["2024-01-01", "AAPL", 1],
 ["2024-01-02", "AAPL", 5],
 ["2024-01-01", "MSFT", 10],
 ["2024-01-02", "MSFT", 6]
]

For AAPL, sorted by date the prices are [1, 5, 7]. Buying at 1, selling at 5, buying at 5, selling at 7 (equivalently, riding 1 -> 7) yields 6. For MSFT, sorted prices are [10, 6], a strictly falling series, so the best action is to never trade it: profit 0. Total maximum profit = 6.

Constraints

  • 1 <= number of records <= 2 * 10^5.
  • Ticker strings have length 1..10; 0 <= price <= 10^6.
  • A stock may appear on only one day; such a stock contributes 0 profit.
  • The answer fits in a 64-bit signed integer.