Design an LFU Cache

The problem statement is to design a data structure for an LFU cache. Our LFUCache class should perform the following operations:

LFUCache(int n)

The constructor initializes the cache object with the required capacity.

int get(int key)

This method gets the value of the key if the key exists in the cache. If not, it returns -1.

void put(int key, int value)

This method does the following:

• If the key is present, it updates the value of the key.
• If the key is not present, it inserts the key along with the value.
• If the cache becomes full, it removes the least frequently used key, and then inserts a new element.
• If the cache becomes full, and there's a tie between the least frequently used key, then the least recently used key would be invalidated.