Image cache eviction
A photo app stores downloaded images on disk under a fixed byte budget. Replay ops in order. Each op is either "put|key|bytes", which writes that key at that size, or "drop|key", which deletes it (dropping a key that is not resident does nothing). Writing a key that is already resident changes its size and leaves its arrival position alone. Writing a key that is not resident places it at the newest arrival position. After each write, while the resident bytes exceed budget_bytes, the cache evicts the oldest arrived resident key, and the key just written gets no protection from that loop. Return the keys still resident at the end, oldest arrival first. Return an empty list when none are.
disk_cache_residents(ops: list[str], budget_bytes: int) → list[str][["put|hero.png|300","put|logo.svg|120","put|map.jpg|400"],800]out["logo.svg","map.jpg"][["put|a|500","put|b|300","put|a|700"],800]out["b"][["put|a|200","put|b|200","drop|a","put|c|500"],800]out["b","c"]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.
[["put|hero.png|300","put|logo.svg|120","put|map.jpg|400"],800]["logo.svg","map.jpg"]not run yetsample[["put|a|500","put|b|300","put|a|700"],800]["b"]not run yetsample[["put|a|200","put|b|200","drop|a","put|c|500"],800]["b","c"]not run yetsample