Cache With Time Limit - Leetcode Solution

The Cache With Time Limit problem on leetcode asks us to implement a data structure that provides a cache with a given time limit for each item. The data structure should support two main operations: "put" and "get". The "put" operation should add a new item to the cache or update an existing item. The "get" operation should return the value associated with a given key if the key is present in the cache and its time limit has not expired.

To solve this problem, we can use a combination of a hash table and a doubly linked list. The hash table allows us to quickly look up items by their key, while the doubly linked list allows us to efficiently remove items that have expired.

The cache can be initialized with a maximum size and a default time limit. Items can be added to the cache using the "put" operation, which takes a key, a value, and an optional time limit as arguments. If the cache is already full, the least recently used item should be removed before adding the new item. If the time limit is not provided, the default time limit should be used.

The "put" operation can be implemented as follows:

1. Check if the key is already present in the cache. If it is, update the value and the time limit (if provided) and move the item to the front of the list.
2. If the cache is full, remove the least recently used item (which is at the end of the list).
3. Add the new item to the front of the list and add it to the hash table.

The "get" operation takes a key as an argument and returns the value associated with that key if it is present in the cache and its time limit has not expired. If the key is not present or its time limit has expired, the function should return -1.

The "get" operation can be implemented as follows:

1. Look up the key in the hash table. If it is not present, return -1.
2. If the item's time limit has expired, remove it from the cache and return -1.
3. If the item is present and its time limit has not expired, move it to the front of the list and return its value.

To keep track of the least recently used item, we need to maintain a doubly linked list that keeps the items in the order of their recent usage. Every time an item is accessed (either through a "put" or a "get" operation), we move it to the front of the list. This way, the least recently used item will always be at the end of the list.

The time complexity of the "put" and "get" operations is O(1) because we are using a hash table to look up items by their key and a doubly linked list to keep track of recent usage. The space complexity is O(n) because we need to store all the items in both the hash table and the doubly linked list.

Here is the Python code for the Cache With Time Limit problem:

class ListNode:
    def __init__(self, key=None, val=None, time_limit=None):
        self.key = key
        self.val = val
        self.time_limit = time_limit
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int, default_time_limit: int):
        self.capacity = capacity
        self.default_time_limit = default_time_limit
        self.size = 0
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.cache = {}

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        if node.time_limit is not None and node.time_limit < time.time():
            self.remove_node(node)
            del self.cache[key]
            return -1
        self.move_to_front(node)
        return node.val

    def put(self, key: int, value: int, time_limit: int = None) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            if time_limit is not None:
                node.time_limit = time.time() + time_limit
            self.move_to_front(node)
            return
        node = ListNode(key, value, time_limit or time.time() + self.default_time_limit)
        self.cache[key] = node
        self.add_to_front(node)
        self.size += 1
        if self.size > self.capacity:
            node = self.remove_from_end()
            del self.cache[node.key]
            self.size -= 1

    def move_to_front(self, node: ListNode) -> None:
        self.remove_node(node)
        self.add_to_front(node)

    def add_to_front(self, node: ListNode) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def remove_node(self, node: ListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def remove_from_end(self) -> ListNode:
        node = self.tail.prev
        self.remove_node(node)
        return node

In this implementation, the cache stores the item's key, value, and time limit in a ListNode object. The get() and put() functions use the doubly linked list operations to add, remove, and move nodes. The move_to_front() function removes a node from its current position and adds it to the front of the list. The add_to_front() function adds a new node to the front of the list. The remove_node() function removes a node from the list. The remove_from_end() function removes the least recently used item (which is at the end of the list) and returns it.

The cache is initialized with a maximum size and a default time limit for each item. The default_time_limit argument is optional and defaults to 60 seconds if not provided. If an item's time limit is not provided, the default time limit is used.

The get() function looks up the key in the cache and returns the associated value if the key is present and the time limit has not expired. If the key is not present or the time limit has expired, the function returns -1.

The put() function adds a new item to the cache or updates an existing item. If the cache is already full, the least recently used item is removed before adding the new item. If an item's time limit is not provided, the default time limit is used.

1