Oracle OA 2023 - Minimum Cache Capacity

Given a list of n items accessed in sequence from a system, and a cache with Least Recently Used (LRU) replacement policy, the goal is to determine the minimum cache size required to ensure at least k requests hit the cache. If it is not possible to achieve k hits, return -1.

Assume each item in the list has a size of 1 unit.

Note: A cache following Least Recently Used (LRU) replacement policy is of fixed size, and when it becomes full, we will delete the value which is least recently used and insert a new value.

Example

Input: n = 5, requests = ["item1", "item1","item3", "item1", "item3"], k = 1
Output: 1
Explanation:
Request 1: "item1" → Miss (insert "item1" into the cache)
Request 2: "item1" → Hit (cache contains "item1", so no need to load)
Request 3: "item3" → Miss (evict "item1", insert "item3")
Request 4: "item1" → Miss (evict "item3", insert "item1")
Request 5: "item3" → Miss (evict "item1", insert "item3")

With a cache size of 1, we achieve 1 hit. Since the requirement is at least k = 1 hit, a cache size of 1 is sufficient.