LFU Cache - BNY Online Assessment IGDTUW

Problem Preview

"Implement an **LFU (Least Frequently Used) cache** of size `cacheSize` that supports two operations. * **GET key** * Retrieve the value associated with `key`. * If the key is not present, return `-1`. * **PUT key value** * Insert or update the `(key, value)` pair. * If the cache is full, remove the **least frequently used** key. * If multiple keys have the same frequency, remove the **least recently used** among them. Return an array containing the outputs of every `GET` query in order. --- ### Example ``` cacheSize = 1 queries = ["PUT 1 1", "PUT 2 2", "GET 1"] ``` Execution | Query | Cache | Output | | ------- | ----- | ------ | | PUT 1 1 | {1=1} | | | PUT 2 2 | {2=2} | | | GET 1 | {2=2} | -1 | Return ``` [-1] ``` --- ### Function ``` implementLFU(cacheSize, queries) ``` #### Parameters ``` int cacheSize string queries[q] ``` #### Returns ``` int[] ``` Outputs of all GET queries. --- ### Constraints ``` 2 ≤ cacheSize ≤ 100 1 ≤ q ≤ 10^5 At least one GET query exists. Length of query ≤ 17 Keys and values contain digits (0-9) only. Value of key ≤ 300 Value of value ≤ 10^5 ``` ---"