Job queue overflow
An ingest service holds jobs in a waiting line of at most capacity jobs, and you replay one event log twice to compare two overflow policies. Each entry in events is either "add|job7", a job arriving under the name after the pipe, or "run", the worker taking the job at the front of the line and removing it, which does nothing when the line is empty. Under drop oldest, an arrival that finds the line full pushes out the job that has waited longest, then joins the back. Under drop newest, an arrival that finds the line full is refused and the line is left untouched. A capacity of zero means no job can ever wait, so every arrival is dropped under both policies. Names may repeat. Return exactly two lists: the names dropped under drop oldest in the order they were dropped, then the same for drop newest.
queue_drop_report(events: list[str], capacity: int) → list[list[str]][["add|a","add|b","add|c","run","add|d"],2]out[["a"],["c"]][["add|x","add|y","add|z","run","add|w","add|v"],1]out[["x","y","w"],["y","z","v"]][["add|a","add|b","run","add|c"],3]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.
[["add|a","add|b","add|c","run","add|d"],2][["a"],["c"]]not run yetsample[["add|x","add|y","add|z","run","add|w","add|v"],1][["x","y","w"],["y","z","v"]]not run yetsample[["add|a","add|b","run","add|c"],3][[],[]]not run yetsample