Snapshot Timeline Reconstruction: Rebuild Object State from a Series of Snapshots and Diffs

Question

## Problem

You receive a stream of events describing an object's state over time. Events are either:
- `SNAPSHOT t obj_state` — full state at time `t`
- `DIFF t patch` — a JSON-patch-style diff applied at time `t`

Given a query time `q`, reconstruct the object's state at time `q` using the nearest preceding snapshot plus any diffs between the snapshot and `q`.

```python
def reconstruct_state(
    events: list[dict],  # [{"type": "SNAPSHOT"|"DIFF", "t": int, "data": dict}]
    query_t: int
) -> dict:
    pass
```

## Example

```
events = [
  {"type": "SNAPSHOT", "t": 0,  "data": {"x": 1, "y": 2}},
  {"type": "DIFF",     "t": 5,  "data": {"op": "set", "key": "x", "val": 10}},
  {"type": "SNAPSHOT", "t": 10, "data": {"x": 10, "y": 5}},
  {"type": "DIFF",     "t": 15, "data": {"op": "del", "key": "y"}},
]

reconstruct_state(events, query_t=12)
# -> {"x": 10, "y": 5}  (snapshot at t=10, no diffs between 10 and 12)

reconstruct_state(events, query_t=17)
# -> {"x": 10}  (snapshot at t=10 + diff at t=15 removes y)
```

## Follow-ups

1. How do you index events to find the nearest preceding snapshot in O(log n)?
2. What if diffs can arrive out of order?
3. How would you design a compaction strategy to prune old snapshots and diffs?

Snapshot Timeline Reconstruction: Rebuild Object State from a Series of Snapshots and Diffs

Question Details

Full Details

Topics

More from Anthropic