Design LFU Cache

An LFU (Least Frequently Used) cache is a data structure that maintains a fixed-size collection of key-value pairs, evicting items based on their access frequency rather than recency. When the cache reaches its capacity limit, it removes the item with the lowest frequency count. In case of a tie, it evicts the least recently used item among those with the same frequency.

Core Concept

The LFU cache operates on a different principle than LRU: the item that has been accessed the least number of times is the first to be removed.

Your Task

Implement an LFU cache with O(1) time complexity for both get and put operations. The cache should have a fixed capacity and evict the least frequently used item when the cache is full. Use a combination of hash map and doubly linked list for optimal performance.

Data Structure Requirements

Both get and put operations should be O(1) time complexity.

Implement an LFU (Least Frequently Used) cache with O(1) time complexity for both get and put operations. The cache should evict the least frequently used item, and in case of a tie, evict the least recently used item. Use a combination of hash maps and doubly linked lists to maintain frequency levels.

#include <unordered_map>
#include <map>
#include <list>
#include <iostream>

// TODO: Implement an LFU (Least Frequently Used) cache with O(1) time complexity
// for both get and put operations
//
// Requirements:
// 1. Fixed capacity cache that evicts least frequently used items
// 2. O(1) time complexity for get(key) and put(key, value) operations
// 3. In case of frequency tie, evict least recently used item
//
// Key Methods to Implement:
// - get(key): Return value if key exists, -1 otherwise. Increment frequency.
// - put(key, value): Add/update key-value pair. Evict LFU if at capacity.

class LFUCache {
private:
    // TODO: Implement the data structures

public:
    LFUCache(int capacity) {
        // TODO: Initialize your data structures
    }

    // TODO: Get value for key, return -1 if not found
    // Also increment the frequency of the accessed item
    int get(int key) {
        return -1;
    }

    // TODO: Put key-value pair into cache
    // If key exists, update value and increment frequency
    // If cache is full, evict least frequently used item
    void put(int key, int value) {
    }
};