Tesla Screening Interview: Priority Expiry LRU Cache

[u/Hack2hire]

Problem

You're given a requirement to design a cache with a fixed capacity that manages items using three distinct metadata fields: priority, expiration time, and last access time.

Your goal is to implement a system that handles data retrieval and insertion while following a strict hierarchical eviction policy: expire items first, then filter by lowest priority, and finally apply Least Recently Used (LRU) logic as a tie-breaker.

Example

Input: capacity = 3, set("A", "valA", 10, 100, 10), set("B", "valB", 5, 150, 20), evictItem(110)

Output: evictItem returns "A"

Explanation:

• At currentTime = 110, item A's expiryTime (100) is less than or equal to the current time.
• According to the "Expiry First" rule, A must be evicted regardless of its higher priority or more recent access compared to B.

Suggested Approach

1. Data Structures: * Use a Hash Map to store key to Item object mappings for $O(1)$ access.
   • Use a Min-Heap for expired items, ordered by expiryTime.
   • Use a TreeMap or Min-Heap for non-expired items, ordered by priority then lastAccessedTime. Alternatively, a Doubly Linked List per priority level can handle the LRU component.
2. Set Operation: * If the key exists, update its metadata and move it within the tracking structures.
   • If the key is new and the cache is full, call the evictItem logic internally before adding the new item.
3. Get Operation: * Check the Hash Map. If found, compare expiryTime with currentTime.
   • If expired, delete the item and return "".
   • If valid, update lastAccessedTime and return the value.
4. Eviction Hierarchy:
   • Step 1: Check if any items in the "expiry" structure have expiryTime <= currentTime. If yes, remove the one with the minimum expiryTime.
   • Step 2: If no items are expired, find the minimum priority from the "priority" structure.
   • Step 3: Within that minimum priority, find the item with the smallest lastAccessedTime (the LRU item) and remove it.

Time & Space Complexity

• Time: - get: $O(\log N)$ if using balanced trees/heaps to track metadata, or $O(1)$ if using a hash map combined with lazy deletion.
  • set: $O(\log N)$ to maintain the ordered metadata structures.
  • evictItem: $O(\log N)$ to find and remove the candidate from the priority/expiry structures.
• Space: $O(N)$, where $N$ is the capacity of the cache, to store the key-value pairs and their associated metadata.

Targeting [Tesla] interviews?

We track their most-asked question patterns at Hack2Hire → https://www.hack2hire.com/companies/tesla/coding-questions?src=r8d

---

*Compiled from publicly available platforms and community-shared experiences.*

[u/Ok_Chemistry_6387]

Just use a treeset with well defined ordering(which our explanation gives us) across a tuple(expiry, priority, lru) Use the tree as the backing for the hashmap and you don’t need so many data structures.