Problem:

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert 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 this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be evicted.

Follow up: Could you do both operations in O(1) time complexity?

Solution:

To solve this problem, we can use a combination of a hash table and a doubly linked list. We will call the hash table the "cache," and the doubly linked list the "freq list".

Each node in the doubly linked list corresponds to a frequency of access. Each node has a frequency value, and a linked list of cache entries, where each entry has the same frequency value as the node it belongs to.

When a cache entry is accessed, its frequency value will be incremented and its position in the freq list will be adjusted accordingly. If the entry had the lowest frequency value in its current node's linked list, and its new frequency value is not present in the freq list, a new node with the new frequency value will be created and inserted after the current node. If the entry's new frequency value is present in the freq list, the entry will be moved to the linked list of its new node.

When a new entry is inserted into the cache, it will be inserted into the linked list of the node with frequency value 1. If the cache is already at capacity, the least frequently used cache entry will be evicted from the cache (which will be the entry at the head of the linked list of the node with the lowest frequency value).

The cache will contain a hash map of key-value pairs, with the key mapping to a doubly linked list node that contains the value and its frequency.

The time complexity of all operations will be O(1), assuming we can perform constant time hash map and doubly linked list operations.

Here is the implementation in Python:

class Node: def init(self, freq): self.freq = freq self.prev = None self.next = None self.entries = set()

class LFUCache:

def __init__(self, capacity: int):
    self.capacity = capacity
    self.cache = {}
    self.freq_list_head = Node(0)

def get(self, key: int) -> int:
    if key not in self.cache:
        return -1
    
    # update entry frequency
    entry, freq_node = self.cache[key]
    freq_node.entries.remove(entry)
    
    if not freq_node.entries and freq_node != self.freq_list_head:
        # remove freq node if empty and not head
        freq_node.prev.next = freq_node.next
        freq_node.next.prev = freq_node.prev
    
    if freq_node.next.freq != freq_node.freq + 1:
        # create new freq node if not exist
        new_freq_node = Node(freq_node.freq + 1)
        new_freq_node.prev = freq_node
        new_freq_node.next = freq_node.next
        freq_node.next.prev = new_freq_node
        freq_node.next = new_freq_node
    
    # move entry to next freq node
    next_freq_node = freq_node.next
    next_freq_node.entries.add(entry)
    entry.freq_node = next_freq_node
    self.cache[key] = (entry, next_freq_node)
    
    return entry.value

def put(self, key: int, value: int) -> None:
    if not self.capacity:
        return
    
    if key in self.cache:
        # update existing entry value and frequency
        entry, freq_node = self.cache[key]
        freq_node.entries.remove(entry)
        
        if not freq_node.entries and freq_node != self.freq_list_head:
            # remove freq node if empty and not head
            freq_node.prev.next = freq_node.next
            freq_node.next.prev = freq_node.prev
        
        if freq_node.next.freq != freq_node.freq + 1:
            # create new freq node if not exist
            new_freq_node = Node(freq_node.freq + 1)
            new_freq_node.prev = freq_node
            new_freq_node.next = freq_node.next
            freq_node.next.prev = new_freq_node
            freq_node.next = new_freq_node
        
        # move entry to next freq node
        next_freq_node = freq_node.next
        next_freq_node.entries.add(entry)
        entry.freq_node = next_freq_node
        entry.value = value
    else:
        if len(self.cache) == self.capacity:
            # evict least frequently used cache entry
            entry_to_evict = self.freq_list_head.next.entries.pop()
            del self.cache[entry_to_evict.key]
            
            if not self.freq_list_head.next.entries:
                # remove freq node if empty
                self.freq_list_head.next.next.prev = self.freq_list_head
                self.freq_list_head.next = self.freq_list_head.next.next
            
        # insert new cache entry with freq 1
        new_entry = Entry(key, value)
        new_entry.freq_node = self.freq_list_head.next
        self.cache[key] = (new_entry, self.freq_list_head.next)
        self.freq_list_head.next.entries.add(new_entry)
    

class Entry: def init(self, key, value): self.key = key self.value = value self.freq_node = None

Example usage

lfu_cache = LFUCache(2) lfu_cache.put(1, 1) lfu_cache.put(2, 2) print(lfu_cache.get(1)) # 1 lfu_cache.put(3, 3) print(lfu_cache.get(2)) # -1 print(lfu_cache.get(3)) # 3 lfu_cache.put(4, 4) print(lfu_cache.get(1)) # -1 print(lfu_cache.get(3)) # 3 print(lfu_cache.get(4)) # 4

1