LRU cache with runtime resizing

Implement a least recently used (LRU) cache whose capacity can change while it is in use.

class LRUCache:
    def __init__(self, capacity: int) -> None
    def get(self, key: int) -> int
    def put(self, key: int, value: int) -> None
    def resize(self, new_capacity: int) -> list[int]

• get(key) returns the value for key, or -1 if it is not cached. A successful get makes the key the most recently used.
• put(key, value) inserts or updates the key and makes it the most recently used. If the cache now holds more than capacity entries, evict the least recently used entry.
• resize(new_capacity) changes the capacity. If the cache holds more entries than the new capacity, evict least recently used entries until it fits. Return the evicted keys, oldest first. Growing the capacity evicts nothing. Resizing does not count as using any key.

Constraints

• get and put must run in O(1) time. resize may take time proportional to the number of entries it evicts.
• Capacity may be 0 (the cache then stores nothing). A negative capacity is an error.
• Up to 10^5 calls in total.

Example 1

LRUCache(3), put(1, 10), put(2, 20), put(3, 30), get(1) -> 10 (order from oldest: 2, 3, 1). put(4, 40) evicts key 2. resize(1) returns [3, 1] and leaves only key 4. resize(3) returns []. get(4) -> 40.

Example 2

LRUCache(2), put(1, 1), put(2, 2), put(1, 100) (update, no eviction), put(3, 3) evicts key 2, so get(2) -> -1 and get(1) -> 100.

Reconstructed from the reported question; details may differ from what interviewers ask.