Tesla Coding Interview: Priority Expiry Cache Eviction

You are asked to implement evictItem() for a cache that must evict exactly one entry according to a strict precedence: expired items first, then the item with the lowest numeric priority, and if multiple items share that lowest priority, the least-recently-used (LRU) item among them.

This question treats set/get as blackbox operations that already store items with fields (key, value, priority, expireTime) and update recency metadata. Your evictItem() should locate a single candidate, remove it from the cache storage, and return its key (or None/null if the cache is empty). You must not change how set/get work or how recency is updated.

Flow you’ll be asked to explain or implement:

• Check for any expired items (expireTime < now) and evict one if present.
• If none expired, find the minimum priority value and evict one item with that priority.
• If multiple items tie on priority, pick the LRU among them using the maintained recency metadata.

Skill signals interviewers expect:

• Familiarity with priority queues/heaps and min-heap ordering
• Use of timestamps and lazy-deletion to keep auxiliary heaps in sync with main storage
• Handling of edge cases (empty cache, concurrent modifications, equal expireTime or priority)
• Time/space complexity reasoning (aim for O(log n) per eviction with lazy cleanup)

Practical tips: describe data structures you’d maintain (e.g., an expire-time min-heap and a priority min-heap keyed by (priority, lastAccessTime)), explain lazy invalidation when set/get mutates storage, and outline unit tests and common pitfalls (clock drift, identical timestamps).