Code RoomWait-free atomic snapshot
HardPrep Room Coding #307

Wait-free atomic snapshot

CodingConcurrencySenior–Staff~35 min

Implement a wait-free atomic snapshot of an array of counters using the classic double-collect technique. You are given M counters (initially all 0) and a list of events. Each event is either ['inc', i] (counter i increments by 1) or ['snap'] (a reader attempts to take a snapshot). Model the reader's wait-free scan as: take a 'collect' of all counters, take a second 'collect'; if the two collects are identical, that is the snapshot. Otherwise, between the two collects exactly one inc happened (events are sequential), so RETRY by collecting again until two consecutive collects match. Since events are sequential, a 'snap' event sees no concurrent change and the first double-collect always matches. Return the list of snapshots (each a list of M ints) in the order 'snap' events occur.

Implement
atomic_snapshots(m: int, events: list[list]) → list[list[int]]
Examples
in[2,[["inc",0],["snap"],["inc",1],["snap"]]]out[[1,0],[1,1]]
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 35 min
InputExpectedGot
[2,[["inc",0],["snap"],["inc",1],["snap"]]][[1,0],[1,1]]not run yetsample