Design a cache called PriorityExpiryLRUCache that associates keys with values, and also tracks a priority and an expiration time for each entry. The cache can hold at most capacity elements at any moment. When the cache is full and a new entry needs to be added, the eviction policy selects one victim by applying a strict hierarchy of rules — first considering expiry, then priority, and finally recency of access.
Internally, every cached entry stores:
valuepriorityexpiryTimelastAccessedTimeThe lastAccessedTime is refreshed whenever an entry is:
set call,get.Implement the PriorityExpiryLRUCache class with the following methods:
PriorityExpiryLRUCache(int capacity)
Constructs a cache with the given maximum capacity.
void set(String key, String value, int priority, int expiryTime, int currentTime)
Inserts a new entry or updates an existing one.
key already exists in the cache, replace its value, priority, and expiryTime.key is absent and the cache has reached its capacity, a single entry must be evicted according to the eviction hierarchy before the new entry can be inserted.lastAccessedTime as currentTime.String get(String key, int currentTime)
Returns the value bound to key.
key is not found, return an empty string "".expiryTime ≤ currentTime), remove it from the cache and return "".lastAccessedTime to currentTime and return its value.String evictItem(int currentTime)
Removes exactly one entry from the cache according to the following layered rules and returns the removed key. If the cache is empty, return "".
expiryTime ≤ currentTime, evict one of the expired entries; among the expired entries, choose the one with the earliest expiryTime.priority value.lastAccessedTime is the smallest (the Least Recently Used entry).Constraints:
1 ≤ capacity, priority ≤ 10^40 ≤ expiryTime, currentTime ≤ 10^510^5.Example:
["PriorityExpiryLRUCache","set","set","set","evictItem","get","set","evictItem","set","evictItem","get","get","set","get","set","set","set","get"] [[3],["A","valueA",10,100,10],["B","valueB",5,150,20],["C","valueC",5,200,30],[110],["B",120],["D","valueD",3,300,130],[135],["E","valueE",5,250,140],[145],["Z",145],["B",150],["E","newE",8,400,160],["E",165],["F","valueF",2,500,170],["G","valueG",7,500,175],["H","valueH",6,500,180],["H",185]]
[ null, null, null, null, "A", "valueB", null, "D", null, "C", "", "", null, "newE", null, null, null, "valueH" ]
PriorityExpiryLRUCache cache = new PriorityExpiryLRUCache(3); cache.set("A","valueA",10,100,10); // Insert A with priority 10, expiry 100. cache.set("B","valueB",5,150,20); // Insert B with priority 5, expiry 150. cache.set("C","valueC",5,200,30); // Insert C with priority 5, expiry 200. cache.evictItem(110); // Returns "A". At time 110, A is expired (100 ≤ 110); expired items are evicted first. cache.get("B",120); // Returns "valueB". A successful get updates B's lastAccessedTime to 120. cache.set("D","valueD",3,300,130); // Insert D with priority 3, expiry 300. cache.evictItem(135); // Returns "D". No items are expired at time 135, so the lowest-priority item (D, priority 3) is evicted. cache.set("E","valueE",5,250,140); // Insert E with priority 5, expiry 250. cache.evictItem(145); // Returns "C". Lowest priority is 5 (B, C, E). Breaking the tie by LRU: C has the smallest lastAccessedTime. cache.get("Z",145); // Returns "" because key Z is not present. cache.get("B",150); // Returns "" and removes B since it is expired at the boundary (150 \le 150). cache.set("E","newE",8,400,160); // Update E’s value/priority/expiry and refresh its lastAccessedTime to 160. cache.get("E",165); // Returns "newE". cache.set("F","valueF",2,500,170); // Insert F with priority 2, expiry 500. cache.set("G","valueG",7,500,175); // Insert G with priority 7, expiry 500. cache.set("H","valueH",6,500,180); // Cache is full, so an item is automatically evicted before inserting H. No expired items exist; the lowest-priority item F is evicted. cache.get("H",185); // Returns "valueH".