Code RoomCanonicalize execution traces
MediumPrep Room Coding #4930

Canonicalize execution traces

CodingConcurrencyAlgorithms & data structuresMid–Senior~25 min

A test harness replays a concurrent program many times and records each run as a log. A log entry is a thread name, a colon, then an event name, and both names are non empty and hold only lowercase letters and digits. Entries appear in the order the harness observed them, so two replays of one program differ only in how the threads were interleaved. Two runs are the same execution when every thread performed the same events in the same order in both, whatever order the threads took their turns in. A thread that acts in one run and not in the other makes the two runs different. Given the runs, return how many distinct executions were observed.

Implement
distinct_executions(runs: list[list[str]]) → int
Examples
in[[["t1:a","t2:x","t1:b"],["t1:a","t1:b","t2:x"]]]out1
in[[["t1:b","t1:a"],["t1:a","t1:b"]]]out2
in[[["t1:x","t2:y"],["t1:x","t1:y"]]]out2
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 25 min
InputExpectedGot
[[["t1:a","t2:x","t1:b"],["t1:a","t1:b","t2:x"]]]1not run yetsample
[[["t1:b","t1:a"],["t1:a","t1:b"]]]2not run yetsample
[[["t1:x","t2:y"],["t1:x","t1:y"]]]2not run yetsample