LFU Cache (#460)

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Returns the value of the key if the key exists in the cache, otherwise returns -1.
void put(int key, int value) Sets or inserts the value if the key is not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For a tie in usage frequency, the least recently used key should be invalidated.

The functions get and put must each run in O(1) average time complexity.

Company Tags: Google, Amazon

Core Concept: Cache, HashMap, Frequency