Image cache eviction

Write codeEasy15 min

Your task

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.

Examples

disk_cache_residents(ops: list[str], budget_bytes: int) -> list[str]
Example 1
Inputdisk_cache_residents(["put|hero.png|300", "put|logo.svg|120", "put|map.jpg|400"], 800)
Output["logo.svg", "map.jpg"]
Example 2
Inputdisk_cache_residents(["put|a|500", "put|b|300", "put|a|700"], 800)
Output["b"]
Example 3
Inputdisk_cache_residents(["put|a|200", "put|b|200", "drop|a", "put|c|500"], 800)
Output["b", "c"]