Maximum Profit from Dated Stock Trade Records
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Maximum Profit from Dated Stock Trade Records
You are given a log of stock trades. Each trade is a record `[date, symbol, price]`:
- `date` — a calendar date as a string in `"YYYY-MM-DD"` format.
- `symbol` — the stock's ticker, an uppercase string (e.g., `"AAPL"`).
- `price` — the trade price as a **positive integer** (the price in cents, so every value is exact).
The records may appear in **any order** — they are not sorted by date.
You want to make exactly **one** buy-then-sell transaction:
- Buy one share of some stock on one day, then sell that **same** stock on a **strictly later** day.
- The profit of a transaction is `sell_price - buy_price`.
- The buy and sell must share the same `symbol`, and the sell `date` must be strictly after the buy `date`.
Return the **maximum profit** achievable from a single such transaction. If no transaction yields a positive profit (for example, fewer than two records exist for every symbol, or every symbol only declines over time), return `0`.
### Input / Output
- Input: `records`, a list of `[date, symbol, price]` entries.
- Output: a single integer — the maximum achievable profit, or `0` if none is positive.
### Examples
Example 1:
```
records = [
["2024-01-03", "AAPL", 100],
["2024-01-01", "AAPL", 90],
["2024-01-02", "GOOG", 200],
["2024-01-04", "GOOG", 150]
]
Output: 10
```
Explanation: For `AAPL`, buy at 90 on 2024-01-01 and sell at 100 on 2024-01-03, giving a profit of 10. For `GOOG`, the price only falls (200 down to 150), so it offers no profit. The best single transaction is 10.
Example 2:
```
records = [
["2024-05-01", "TSLA", 300],
["2024-05-02", "TSLA", 250],
["2024-05-03", "TSLA", 200]
]
Output: 0
```
Explanation: `TSLA` only declines, so no profitable buy-then-sell exists.
Example 3:
```
records = [
["2024-07-10", "NVDA", 500]
]
Output: 0
```
Explanation: A single record cannot form a buy-then-sell pair.
### Constraints
- `0 <= len(records) <= 2 * 10^5`.
- Each `date` is a valid `"YYYY-MM-DD"` string; lexicographic string comparison matches chronological order.
- `1 <= price <= 10^9`.
- Multiple records may share the same `date` **and** `symbol`; a buy and a sell on the **same** date do not form a valid transaction, because the sell date must be strictly later than the buy date.
Quick Answer: This question evaluates a candidate's ability to design an efficient single-pass algorithm for grouped time-series data, tracking per-symbol running minimums to compute maximum achievable profit. It tests array processing, hash-map grouping, and edge-case handling for unsorted records, commonly used in coding interviews to assess practical algorithmic problem-solving rather than pure theory.
You are given a log of stock trades. Each trade is a record `[date, symbol, price]`:
- `date` — a calendar date as a string in `"YYYY-MM-DD"` format.
- `symbol` — the stock's ticker, an uppercase string (e.g. `"AAPL"`).
- `price` — the trade price as a positive integer.
The records may appear in any order (they are not sorted by date).
Make exactly one buy-then-sell transaction: buy one share of some stock on one day, then sell that same stock on a strictly later day. The profit is `sell_price - buy_price`, the buy and sell must share the same `symbol`, and the sell `date` must be strictly after the buy `date`.
Return the maximum profit achievable from a single such transaction, or `0` if no transaction yields a positive profit.
Note: multiple records may share the same `date` and `symbol`; a buy and a sell on the same date do NOT form a valid transaction because the sell date must be strictly later.
### Approach
Group records by symbol. Within each symbol, sort by date and sweep in date order while tracking `min_price`, the cheapest price seen on any strictly earlier date. For every record on the current date, the best sale profit is `price - min_price`. Crucially, update `min_price` with the current date's prices only AFTER scoring all sells on that date — this enforces the strictly-later rule for records that share a date. Overall `O(n log n)` time, `O(n)` space.
Constraints
- 0 <= len(records) <= 2 * 10^5
- Each date is a valid "YYYY-MM-DD" string; lexicographic comparison matches chronological order
- 1 <= price <= 10^9
- Multiple records may share the same date and symbol
- A buy and a sell on the same date do NOT form a valid transaction
Examples
Input: ([['2024-01-03', 'AAPL', 100], ['2024-01-01', 'AAPL', 90], ['2024-01-02', 'GOOG', 200], ['2024-01-04', 'GOOG', 150]],)
Expected Output: 10
Explanation: AAPL: buy 90 on 2024-01-01, sell 100 on 2024-01-03 -> profit 10. GOOG only declines (200 -> 150). Best single transaction is 10.
Input: ([['2024-05-01', 'TSLA', 300], ['2024-05-02', 'TSLA', 250], ['2024-05-03', 'TSLA', 200]],)
Expected Output: 0
Explanation: TSLA strictly declines over time, so no buy-then-sell yields positive profit.
Input: ([['2024-07-10', 'NVDA', 500]],)
Expected Output: 0
Explanation: A single record cannot form a buy-then-sell pair.
Input: ([],)
Expected Output: 0
Explanation: No records at all, so no transaction is possible.
Input: ([['2024-01-01', 'AAPL', 90], ['2024-01-01', 'AAPL', 100]],)
Expected Output: 0
Explanation: Both records share the same date; a same-day buy/sell is not valid because the sell must be strictly later, so profit is 0.
Input: ([['2024-01-05', 'X', 1], ['2024-01-01', 'X', 10], ['2024-01-03', 'X', 2], ['2024-01-06', 'X', 50]],)
Expected Output: 49
Explanation: The cheapest buy (price 1 on 2024-01-05) precedes the highest later sell (50 on 2024-01-06): profit 49. The min-so-far must be tracked in date order, not by list order.
Input: ([['2024-01-01', 'A', 5], ['2024-01-01', 'A', 3], ['2024-01-02', 'A', 4]],)
Expected Output: 1
Explanation: On 2024-01-01 there are two prices (5 and 3); neither can sell against the other (same day). Buying at the lower 3 and selling at 4 on 2024-01-02 gives profit 1.
Input: ([['2024-01-01', 'A', 1], ['2024-01-02', 'A', 2], ['2024-01-01', 'B', 10], ['2024-01-02', 'B', 100]],)
Expected Output: 90
Explanation: A yields profit 1 (1 -> 2); B yields profit 90 (10 -> 100). The best across symbols is 90.
Hints
- A single global min/max over all records is wrong — the sell must come after the buy in time, and the buy/sell must be the same symbol. Process each symbol independently.
- Within a symbol, sort by date and sweep once, keeping the minimum price seen so far as the candidate buy. For each record, profit = current price - running min.
- Watch the strictly-later rule: when several records share a date, score all of them as potential sells against the earlier running minimum FIRST, then fold that date's prices into the minimum — so a same-day pair never counts.