Code RoomTransaction crash recovery
EasyPrep Room Coding #4736

Transaction crash recovery

CodingDatabases & SQLStorage & CDNEntry–Mid~16 min

A checkout ledger crashed and recovery has to decide what to roll back. The journal is the records it appended, in order, with fields separated by a vertical bar. "begin|t7" opens transaction t7. "put|t7|cart:12|open" records that t7 wrote the value open to the key cart:12. "commit|t7" and "abort|t7" close t7. A transaction needs undo when it wrote at least one value and the journal holds neither a commit nor an abort for it, so its work is neither durable nor already rolled back. A transaction that opened but wrote nothing has nothing to undo. Some puts have no begin in this journal because the begin predates the last checkpoint, and those writes still count. Return the transaction ids needing undo, without duplicates, sorted ascending as text, so "t10" comes before "t2".

Implement
txns_needing_undo(journal: list[str]) → list[str]
Examples
in[["begin|t1","put|t1|cart:12|open","commit|t1","begin|t2","put|t2|cart:13|open"]]out["t2"]
in[["begin|t3","commit|t3","begin|t4","put|t4|user:9|paid","abort|t4"]]out[]
in[["put|t8|order:1|new","begin|t9","put|t9|order:2|new","begin|t7","put|t7|order:3|new","commit|t9"]]out["t7","t8"]
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 16 min
InputExpectedGot
[["begin|t1","put|t1|cart:12|open","commit|t1","begin|t2","put|t2|cart:13|open"]]["t2"]not run yetsample
[["begin|t3","commit|t3","begin|t4","put|t4|user:9|paid","abort|t4"]][]not run yetsample
[["put|t8|order:1|new","begin|t9","put|t9|order:2|new","begin|t7","put|t7|order:3|new","commit|t9"]]["t7","t8"]not run yetsample