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