Scamming the coding interview: https://scammingthecodinginterview.com/ : Problem 011 : LFU cache

lfu_cache.py

"""
Scamming the coding interview.

Subscribe to our newsletter at https://scammingthecodinginterview.com/
to get a coding or design problem daily in your inbox and become exceptionally good at
coding interviews.
"""


class FrequencyNode(object):
    """
    Represents a frequency counting bucket.
    Frequency counting bucket holds a doubly linked list of items that were accessed
    value times.
    """
    def __init__(self):
        self.value = 0
        self.items_list_head = None
        self.next = None
        self.prev = None


class DataNode(object):
    """
    Represents the actual value that is cached.
    This also serves as the node of the double linked list of the items list in FrequencyNode
    """
    def __init__(self, key, value):
        self.value = value
        self.parent = None
        self.next = None
        self.prev = None
        self.key = key


class Cache(object):
    """
    The LFU cache
    """

    CACHE_SIZE = 5
    cache = {}
    frequency_bucket_head = None

    @classmethod
    def add_item_in_zero_usage_bucket(cls, data_node):
        """
        Adds the item to the zero frequency bucket list.
        If the bucket is not present, we initialise it.
        We always maintain that there are no frequency node present in the list that has no items in its item list.
        """
        if not cls.frequency_bucket_head or not cls.frequency_bucket_head.value == 0:
            new_head = FrequencyNode()
            new_head.next = cls.frequency_bucket_head
            cls.frequency_bucket_head = new_head

        prev_head = cls.frequency_bucket_head.items_list_head
        cls.frequency_bucket_head.items_list_head = data_node
        data_node.next = prev_head
        data_node.parent = cls.frequency_bucket_head
        if prev_head:
            prev_head.prev = data_node

    @classmethod
    def remove_least_frequently_used_item(cls):
        """
        When the cache overflows, we remove the least frequently used item.
        If there are multiple items, we remove the first one.
        """
        items_head = cls.frequency_bucket_head.items_list_head
        cls.frequency_bucket_head.items_list_head = items_head.next
        cls.cache.pop(items_head.key)

        if cls.frequency_bucket_head.items_list_head is None:
            cls.frequency_bucket_head = cls.frequency_bucket_head.next

    @classmethod
    def set_value(cls, key, value):
        """
        Whenever a new key is set in the cache:
        1. We check if the cache is full.
        2. If yes, then we remove the least frequently used item
        3. We add the item in the cache map.
        4. We add the item in the zero frequency bucket list.
        """

        if len(cls.cache) >= cls.CACHE_SIZE:
            cls.remove_least_frequently_used_item()

        data_node = DataNode(key=key, value=value)

        cls.cache[key] = data_node
        cls.add_item_in_zero_usage_bucket(data_node)

    @classmethod
    def delete_a_node_from_frequency_node_items(cls, node, frequency_node):
        """
        Helper method to delete a node from the frequency node items
        """
        if node.prev is None:
            frequency_node.items_list_head = node.next
            if node.next:
                node.next.prev = None
        elif node.next is None:
            node.prev.next = None
        else:
            node.prev.next = node.next
            node.next.prev = node.prev

    @classmethod
    def delete_a_node_from_frequency_nodes_list(cls, frequency_node):
        """
        Helper method to delete the node from the frequency node list.
        We use this to delete frequency nodes that have no items left in its items list.
        """
        if frequency_node.prev is None:
            cls.frequency_bucket_head = frequency_node.next
            if frequency_node.next:
                frequency_node.next.prev = None
        elif frequency_node.next is None:
            frequency_node.prev.next = None
        else:
            frequency_node.prev.next = frequency_node.next
            frequency_node.next.prev = frequency_node.prev

    @classmethod
    def get_value(cls, key):
        """
        Gives the value against the key.
        We also handle incrementing the frequency usage count.
        We take the data node from its current frequency node items list, add put it in the frequency node items list
        where frequency was one more than the current frequency.
        If no such frequency node is present, we create the new frequency node with that frequency value.
        """
        data_node = cls.cache.get(key)

        if not data_node:
            return None

        # remove the data_node from the current frequency list
        frequency_node = data_node.parent

        cls.delete_a_node_from_frequency_node_items(data_node, frequency_node)

        # insert the data node in the next frequency list
        next_frequency_list = frequency_node.next

        data_node.prev = None
        data_node.next = None

        if not next_frequency_list:
            next_frequency_list = FrequencyNode()
            next_frequency_list.value = frequency_node.value + 1
            next_frequency_list.items_list_head = data_node
            frequency_node.next = next_frequency_list
        elif next_frequency_list.value == frequency_node.value + 1:
            temp = next_frequency_list.items_list_head
            next_frequency_list.items_list_head = data_node
            temp.prev = data_node
            data_node.next = temp
        else:
            new_frequency_list = FrequencyNode()
            new_frequency_list.value = frequency_node.value + 1
            frequency_node.next = new_frequency_list
            new_frequency_list.next = new_frequency_list
            new_frequency_list.items_list_head = data_node

        if frequency_node.items_list_head is None:
            cls.delete_a_node_from_frequency_nodes_list(frequency_node)

    @classmethod
    def delete_key(cls, key):
        """
        Deletes the key from the cache
        """
        data_node = cls.cache.pop(key)

        if not data_node:
            return

        cls.delete_a_node_from_frequency_node_items(data_node, data_node.parent)

        if data_node.parent.items_list_head is None:
            cls.delete_a_node_from_frequency_nodes_list(data_node.parent)


if __name__ == '__main__':

    Cache.set_value("owl", "city")
    Cache.set_value("owl2", "city2")
    Cache.get_value("owl2")
    Cache.delete_key("owl")
    Cache.set_value("owl3", "city3")
    Cache.get_value("owl3")