Transaction crash recovery
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".
txns_needing_undo(journal: list[str]) → list[str][["begin|t1","put|t1|cart:12|open","commit|t1","begin|t2","put|t2|cart:13|open"]]out["t2"][["begin|t3","commit|t3","begin|t4","put|t4|user:9|paid","abort|t4"]]out[][["put|t8|order:1|new","begin|t9","put|t9|order:2|new","begin|t7","put|t7|order:3|new","commit|t9"]]out["t7","t8"]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.
[["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