Order book budget limit
A trading screen draws the sell side of an order book as a ladder of rungs. ask_cents holds the resting ask prices in cents, sorted ascending, and several orders can rest on one rung, so equal prices repeat. A trader sets a per unit limit of budget_cents and wants to know how far down that ladder the limit reaches. Given ask_cents and budget_cents, return the index of the last rung priced at or below the budget. When a run of rungs shares that price, return the last of them, since every rung in the run is affordable. When even the cheapest rung costs more than the budget, return -1, and an empty ladder returns -1 too. Prices are positive whole cents and the ladder is redrawn on every tick, so the lookup has to be logarithmic.
last_affordable_rung(ask_cents: list[int], budget_cents: int) → int[[100,250,250,400],250]out2[[100,250,400],99]out-1[[100,250,400],1000]out2State 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.
[[100,250,250,400],250]2not run yetsample[[100,250,400],99]-1not run yetsample[[100,250,400],1000]2not run yetsample