Daily Totals of Several Stocks' Prices with Missing Days Carried Forward
Company: Palantir
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Several companies report stock prices, each only on some days. For every date that appears anywhere in the input, compute the total of all companies' prices on that date. When a company has no price on a date, use its previous value, so that every company is counted in every day's total.
### Function Signature
```python
def daily_totals(price_lists: list[list[tuple[str, int]]]) -> list[tuple[str, int]]:
```
### Rules
- `price_lists[i]` is the price history of company `i`: a list of `(date, price)` records.
- A date is a string `"M/D"`: the month (1 to 12) and the day, with no leading zeros and no year. All dates fall in the same year, so dates are ordered by month and then by day: `"5/8"` comes before `"5/10"`, and `"9/30"` before `"10/1"`.
- The output has exactly one `(date, total)` pair for every distinct date that appears in any company's records, in chronological order.
- A company's contribution to the total for date `d` is:
- its price on `d`, if it has a record for `d`;
- otherwise, the price of its latest record before `d`;
- if it has no record on or before `d`, the price of its earliest record. The reported example requires this rule (see the total for `"5/1"` in Example 1).
- Every company contributes to every total.
### Constraints
- `1 <= len(price_lists) <= 1000`
- `1 <= len(price_lists[i])` for every company, and the total number of records over all companies is at most `10^5`
- Each company's records are in chronological order, with at most one record per date.
- Every date is a valid `"M/D"` string as described above.
- `0 <= price <= 10^6`, an integer. Every total is at most `10^9`, so all values fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: price_lists = [
[("5/1", 200), ("5/5", 100), ("5/8", 50)], # PLTR
[("5/1", 50), ("5/8", 100)], # MSFT
[("5/5", 50), ("5/8", 200)], # AMZN
]
Output: [("5/1", 300), ("5/5", 200), ("5/8", 350)]
```
On `5/1`, AMZN has no price yet, so it contributes its earliest price, 50: `200 + 50 + 50 = 300`. On `5/5`, MSFT has no record and carries its `5/1` price: `100 + 50 + 50 = 200`. On `5/8` every company has a price: `50 + 100 + 200 = 350`.
**Example 2**
```text
Input: price_lists = [[("4/30", 7), ("5/10", 3)], [("5/2", 4)]]
Output: [("4/30", 11), ("5/2", 11), ("5/10", 7)]
```
On `4/30` the second company has no record yet and contributes its earliest price, 4. On `5/2` the first company carries its `4/30` price, 7. On `5/10` the second company carries its `5/2` price, 4. The date `"5/10"` comes after `"5/2"`.
Overview: Given several companies' stock prices reported on different days, compute the total across all companies for every date, filling a company's missing day with its most recent earlier price. It tests merging sparse time series, carry-forward logic, and ordering month/day date strings chronologically rather than as text.
Read the full Palantir Software Engineer interview experience this question came from
Several companies report stock prices, each only on some days. For every date that appears anywhere in the input, compute the total of all companies' prices on that date. When a company has no price on a date, use its previous value, so that every company is counted in every day's total.
Implement `daily_totals(price_lists)`.
**Rules**
- `price_lists[i]` is the price history of company `i`: a list of `(date, price)` records.
- A date is a string `"M/D"`: the month (1 to 12) and the day, with no leading zeros and no year. All dates fall in the same year, so dates are ordered by month and then by day: `"5/8"` comes before `"5/10"`, and `"9/30"` comes before `"10/1"`.
- Return exactly one `(date, total)` pair for every distinct date that appears in any company's records, in chronological order.
- A company's contribution to the total for date `d` is:
- its price on `d`, if it has a record for `d`;
- otherwise, the price of its latest record before `d`;
- if it has no record on or before `d`, the price of its earliest record (Example 1 requires this rule for `"5/1"`).
- Every company contributes to every total.
**Language representation**
- Python: each record is a tuple `(date, price)`; return a list of `(date, total)` tuples.
- JavaScript: each record is a two-element array `[date, price]`; return an array of `[date, total]` arrays.
- Java: each record is a `java.util.List<Object>` holding the `String` date and the price as a `Number`; return a `java.util.List` of two-element lists, each holding the `String` date and the `Integer` total.
- C++: each record is a `std::pair<std::string, int>`; return a `std::vector<std::pair<std::string, int>>`.
**Constraints**
- `1 <= len(price_lists) <= 1000`
- `1 <= len(price_lists[i])` for every company, and the total number of records over all companies is at most `10^5`
- Each company's records are in chronological order, with at most one record per date.
- Every date is a valid `"M/D"` string as described above (month 1 to 12, a valid day of that month).
- `0 <= price <= 10^6`, an integer. Every total is at most `10^9`, so all values fit in a 32-bit signed integer: no value exceeds `2^31 - 1`, and `int` suffices in Java and C++.
**Example 1**
```text
Input: price_lists = [
[("5/1", 200), ("5/5", 100), ("5/8", 50)], # PLTR
[("5/1", 50), ("5/8", 100)], # MSFT
[("5/5", 50), ("5/8", 200)], # AMZN
]
Output: [("5/1", 300), ("5/5", 200), ("5/8", 350)]
```
On `5/1`, AMZN has no price yet, so it contributes its earliest price, 50: `200 + 50 + 50 = 300`. On `5/5`, MSFT has no record and carries its `5/1` price: `100 + 50 + 50 = 200`. On `5/8` every company has a price: `50 + 100 + 200 = 350`.
**Example 2**
```text
Input: price_lists = [[("4/30", 7), ("5/10", 3)], [("5/2", 4)]]
Output: [("4/30", 11), ("5/2", 11), ("5/10", 7)]
```
On `4/30` the second company has no record yet and contributes its earliest price, 4. On `5/2` the first company carries its `4/30` price, 7. On `5/10` the second company carries its `5/2` price, 4. The date `"5/10"` comes after `"5/2"`.
Constraints
- 1 <= len(price_lists) <= 1000
- 1 <= len(price_lists[i]) for every company, and the total number of records over all companies is at most 10^5
- Each company's records are in chronological order, with at most one record per date.
- Every date is a valid "M/D" string: month 1 to 12, a valid day of that month, no leading zeros, no year; all dates fall in the same year.
- 0 <= price <= 10^6, an integer. Every total is at most 10^9, so all values fit in a 32-bit signed integer (no value exceeds 2^31 - 1).
Examples
Input: ([[('5/1', 200), ('5/5', 100), ('5/8', 50)], [('5/1', 50), ('5/8', 100)], [('5/5', 50), ('5/8', 200)]],)
Expected Output: [('5/1', 300), ('5/5', 200), ('5/8', 350)]
Explanation: Source Example 1: on 5/1 the third company contributes its earliest price 50 (200 + 50 + 50); on 5/5 the second company carries its 5/1 price (100 + 50 + 50); on 5/8 all report (50 + 100 + 200).
Input: ([[('4/30', 7), ('5/10', 3)], [('5/2', 4)]],)
Expected Output: [('4/30', 11), ('5/2', 11), ('5/10', 7)]
Explanation: Source Example 2: earliest-record rule on 4/30, carry-forward on 5/2 and 5/10, and 5/10 sorts after 5/2.
Hints
- Order dates by their numeric (month, day) value rather than by string comparison: "9/30" comes before "10/1", and "5/2" before "5/10".
- For a single company, its contribution on a date depends only on which of its records is the latest one on or before that date, or on its earliest record when there is none.
- A date reported by several companies still produces exactly one output pair, and every company counts toward every date's total.