Latency budget queries
A load test sweeps one service at a rising set of client counts. concurrency is strictly increasing and latency_ms holds the p99 measured at each of those counts, in the same order. Warm parallelism pulls the curve down to a single low point and contention pushes it back up, so latency_ms falls strictly to its minimum and rises strictly after it, and no two neighbouring readings are equal. Either side may be empty. For every entry of budget_ms return the largest client count whose p99 is at or below that budget, or -1 when no setting qualifies, in query order. Both lists are long, so rereading the sweep per query is too slow, and the readings are not sorted, so a plain bisect over them lands on the wrong side.
highest_safe_concurrency(concurrency: list[int], latency_ms: list[int], budget_ms: list[int]) → list[int][[1,2,4,8,16,32],[90,60,41,55,120,400],[50,41,40,400]]out[4,4,-1,32][[5,10,15],[30,20,25],[25,19]]out[15,-1][[2,4,6,8,10],[50,30,10,30,50],[10,30,50,9,51]]out[6,8,10,-1,10]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.
[[1,2,4,8,16,32],[90,60,41,55,120,400],[50,41,40,400]][4,4,-1,32]not run yetsample[[5,10,15],[30,20,25],[25,19]][15,-1]not run yetsample[[2,4,6,8,10],[50,30,10,30,50],[10,30,50,9,51]][6,8,10,-1,10]not run yetsample