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.

results matching ""

    No results matching ""