Least Common Used Cache (LCU) | Dataford Interview Questions

PayPay India services may cache frequently requested values while evicting entries that are used least often. Implement a least commonly used (LCU) cache with O(1) average-time insertion, retrieval, update, and removal.

Each cache entry has a usage frequency. A successful get and every put increase that entry's frequency by one. When the cache is full, evict the entry with the smallest frequency. If multiple entries have the same frequency, evict the least recently used entry among them.

Implement simulate_lcu(capacity, operations). Each operation is one of the following:

['put', key, value]: Insert or update an entry. Return None.
['get', key]: Return the value, or -1 if the key does not exist.
['remove', key]: Remove the entry and return True, or return False if it does not exist.

Keys are integers and values are integers. The returned list must contain one result for every operation, in order.

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 2 * 10^5
Keys and values are integers in [-10^9, 10^9]
Every operation is a valid put, get, or remove command
All cache operations must run in O(1) average time

Function Signature

def simulate_lcu(capacity, operations):

Your question is Least Common Used Cache (LCU). Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem