← Problems96. Collapse a change feed to current stateMediumPython
00:00 / 20:00

Collapse a change feed to current state

MediumNot attempted yetAsked at Amazon, Walmart, TCS

A CDC feed gives you every change to a table. Before it can be merged into the warehouse it has to be collapsed to one row per key — what the table looks like now, not how it got there.

Input

  • changes — a list of (key, version, op, payload) - key — str - version — int, unique within a key and increasing with time - op — 'UPSERT' or 'DELETE' - payload — str, and None on a delete

The list is not in version order. A feed that replays, or that merges two partitions, delivers rows in whatever order they were read.

Output

A list of (key, payload) for every key whose newest change is an UPSERT. Order is not graded.

Example

changes [('a', 1, 'UPSERT', 'a1'), ('a', 2, 'UPSERT', 'a2'), ('b', 1, 'UPSERT', 'b1')] returns [('a', 'a2'), ('b', 'b1')]

Constraints

  • The newest change is the highest version, not the last row in the list.
  • A key whose newest change is a DELETE does not appear at all. It does not fall back to the value before the delete.
  • A key deleted and then written again at a higher version is present, with the newer payload.

Example 1an update wins

Input · changes
[
  ["a", 1, "UPSERT", "a1"],
  ["a", 2, "UPSERT", "a2"],
  ["b", 1, "UPSERT", "b1"]
]
Output
[["a", "a2"], ["b", "b1"]]

Example 2a delete removes the key

Input · changes
[
  ["a", 1, "UPSERT", "a1"],
  ["a", 2, "DELETE", null],
  ["b", 1, "UPSERT", "b1"]
]
Output
[["b", "b1"]]

Topics

data qualitylate arriving data

Similar problems

Community-reported interview topic. Not an official company question and no affiliation is implied.

solution.py
Loading editor…
Draft not saved yet · Spaces 4 · UTF-8⌘↵ run ⌘⇧↵ submit
Nothing run yet

Run against the public tests, or submit to score against all of them.