Company: AT and T
Difficulty: medium
LFU Cache Implementation Implement a Least Frequently Used (LFU) cache data structure of size cacheSize that handles two types of queries, GET and PUT. A GET query attempts to retrieve the value of a given key. If the key is present in the cache, it is returned. Otherwise, it returns -1. A PUT query updates or inserts a key-value pair into the cache. When the cache is full, the least frequently used key is removed to accommodate the new key-value pair. If there is a tie in the frequency of keys, then the least recently used key is removed. Return an array of integers where each i th element is the answer for the i th GET query. Function Description Complete the function implementLFU with the following parameters: int cacheSize : the size of the cache string queries[q] : the query strings Returns int[] : the answers to the GET queries Constraints 2 ≤ cacheSize ≤ 100 1 ≤ q ≤ 10 5 Queries contain at least 1 query of type 1 |queries[i]| ≤ 13 key and value are made up of digits (\'0\' - \'9