Code RoomRolled back read detection
EasyPrep Room Coding #4794

Rolled back read detection

CodingConcurrencyEntry–Mid~18 min

An audit tool replays a storage log to find reads that saw data the writer later threw away. Each event is a string of fields joined by a vertical bar: "t3|write|balance|500" sets a key, "t7|read|balance" reads one, and "t3|commit" or "t3|abort" ends a transaction. Values are plain text and never contain a bar. Every key keeps a stack of versions. A write pushes one, and an abort drops every version that transaction wrote, so the key falls back to its previous version. A read sees the top version of its key, or nothing when the key has none. A read is rolled back when the version it saw came from a different transaction that aborts later in the log. A transaction the log never ends counts as open, not aborted. Return one string per rolled back read, in log order, written as the reader, the key and the value seen, joined by bars.

Implement
rolled_back_reads(events: list[str]) → list[str]
Examples
in[["t1|write|balance|500","t2|read|balance","t1|abort","t2|commit"]]out["t2|balance|500"]
in[["t1|write|stock|9","t1|commit","t2|read|stock","t2|commit"]]out[]
in[["t1|write|price|300","t1|read|price","t1|abort"]]out[]
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 18 min
InputExpectedGot
[["t1|write|balance|500","t2|read|balance","t1|abort","t2|commit"]]["t2|balance|500"]not run yetsample
[["t1|write|stock|9","t1|commit","t2|read|stock","t2|commit"]][]not run yetsample
[["t1|write|price|300","t1|read|price","t1|abort"]][]not run yetsample