Maximum Profit from Multi-Stock Trading Records
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# 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.
Quick Answer: 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.
You are given a list of stock price records from a trading feed. Each record is a triple `[date, stock, price]`:
- `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).
Trading 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 before buying it again. You buy and sell at that day's `price`.
- No fees; you start and must end holding nothing.
Return the **maximum total profit** achievable across all stocks (return `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]`, giving profit `6` (ride `1 -> 5 -> 7`). For `MSFT`, sorted prices are `[10, 6]` (strictly falling), so best action is no trade: profit `0`. Total = **`6`**.
Constraints
- 1 <= number of records <= 2 * 10^5
- Ticker strings have length 1..10
- 0 <= price <= 10^6
- Each (stock, date) pair is unique (at most one record per stock per day)
- A stock appearing on only one day contributes 0 profit
- The answer fits in a 64-bit signed integer
Examples
Input: ([['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]],)
Expected Output: 6
Explanation: AAPL sorted [1,5,7] -> profit 6; MSFT sorted [10,6] falling -> 0. Total 6.
Input: ([['2024-01-01', 'AAPL', 5]],)
Expected Output: 0
Explanation: A stock with a single record can never complete a buy-then-sell, so it contributes 0.
Input: ([['2024-01-01', 'A', 1], ['2024-01-02', 'A', 2], ['2024-01-03', 'A', 3]],)
Expected Output: 2
Explanation: Strictly increasing [1,2,3]: capture (2-1)+(3-2)=2 (equivalently buy 1 sell 3).
Input: ([['2024-01-01', 'M', 10], ['2024-01-02', 'M', 6], ['2024-01-03', 'M', 3]],)
Expected Output: 0
Explanation: Strictly decreasing [10,6,3]: no upward move, best is never to trade -> 0.
Input: ([['2024-01-01', 'A', 1], ['2024-01-02', 'A', 5], ['2024-01-01', 'B', 3], ['2024-01-02', 'B', 8]],)
Expected Output: 9
Explanation: Two independent stocks: A gives 5-1=4, B gives 8-3=5; total 9.
Input: ([['d1', 'A', 1], ['d2', 'A', 7], ['d3', 'A', 2], ['d4', 'A', 3]],)
Expected Output: 7
Explanation: Prices [1,7,2,3]: capture the up-move 1->7 (6) and 2->3 (1) = 7; the 7->2 dip is skipped.
Input: ([['2024-01-02', 'A', 7], ['2024-01-01', 'A', 1], ['2024-01-04', 'A', 3], ['2024-01-03', 'A', 2]],)
Expected Output: 7
Explanation: Unsorted dates; after sorting by date prices are [1,7,2,3] -> 6+1=7. Confirms date sort is required.
Hints
- The stocks are independent — you can solve each ticker separately and add up the profits.
- Records are unsorted; group them by ticker first, then sort each ticker's records by date (ISO date strings sort chronologically).
- With unlimited transactions and one unit at a time, the maximum single-stock profit is the sum of every positive difference between consecutive days' prices (capture every upward move).