Code RoomImage cache eviction
EasyPrep Room Coding #4739

Image cache eviction

CodingStorage & CDNEntry–Mid~15 min

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.

Implement
disk_cache_residents(ops: list[str], budget_bytes: int) → list[str]
Examples
in[["put|hero.png|300","put|logo.svg|120","put|map.jpg|400"],800]out["logo.svg","map.jpg"]
in[["put|a|500","put|b|300","put|a|700"],800]out["b"]
in[["put|a|200","put|b|200","drop|a","put|c|500"],800]out["b","c"]
What a strong answer looks like

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.

0:00 of about 15 min
InputExpectedGot
[["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