Rejected photo uploads
A phone backup service uploads photos in the background and never lets more than limit uploads run at the same time. Its log is a list of events, each a string "id|action" such as "p14|start" or "p14|done". Walk the events in order. A "start" is admitted when fewer than limit uploads are running, and that upload joins the running set. A "start" that arrives while limit uploads are already running is rejected: the photo never uploads, and a later "done" carrying its id changes nothing. A "done" for a running upload removes it and frees its slot. Every id starts at most once. Return the ids of the rejected uploads in the order they were rejected, or an empty list when every upload was admitted.
rejected_uploads(limit: int, events: list[str]) → list[str][2,["p1|start","p2|start","p3|start","p1|done","p4|start"]]out["p3"][1,["a|start","b|start","b|done","c|start","a|done","d|start"]]out["b","c"][2,["x|start","x|done","y|start","y|done"]]out[]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.
[2,["p1|start","p2|start","p3|start","p1|done","p4|start"]]["p3"]not run yetsample[1,["a|start","b|start","b|done","c|start","a|done","d|start"]]["b","c"]not run yetsample[2,["x|start","x|done","y|start","y|done"]][]not run yetsample