LRU cache

Implement a LRU cache for looking up values by key. You should support lookup, insert and delete. Use the LRU strategy for cache eviction.

Solution

• Use a combination of hash table and a linked list

• Insert when not full

  • Add key to hash,
  • Create a linked list node with value,
  • Insert node at the start of the linked list
  • Add a reference to this node in the hash

• Insert when full

  • Find the last node in the list, which was not recently used
  • Delete its hash key, and delete that node from the list as well

• Lookup

  • Find key in hash table, lookup its linked list node and return value
  • Move the node to the start of the list, indicating it was recently used

• Delete

  • Find the node in hash table,
  • Delete its corresponding linked list node and its key from hash

Code

    class LRUCache
        attr_accessors :hash, :list, :size, :max_size

        def initialize(max_size)
            @hash = {}
            @list = LinkedList.new
            @max_size = max_size
        end

        def full?
            @size == @max_size
        end

        def insert(key, value)
            node = LinkedListNode.new(key,value)
            unless full?
                @list.insert_at_beginning(node)
                @hash[key] = node
            else
                # Delete node from end of list
                @hash[@list.last.key].remove
                @list.last.delete
                @list.insert_at_beginning(node)
                @hash[key] = node
            end
        end

        def lookup(key)
            node = @hash[key]

            # move to front of list
            @list.move_to_front(node)

            node.value
        end

        def delete(key)
            node = @hash[key]

            # delete from list and hash
            @list.delete(node)
            @hash[key].remove
        end
    end

Complexity

• Time: Lookup O(1), Insert (1), Delte (1)
• Space: 2n, where n is the number of keys

LRU cache with TTL

• For each node add an adidtional field "expiry", which is the creation time + ttl
• On lookup check if the node has expired by comparing current_time with expiry
• If it has expired delete the node and return not_found
• If its has not expired, then return the value found.