LRU Cache

double-linked-list-based.rb

class Node
  attr_accessor :prev, :next, :value
  attr_reader :key

  def initialize(key, value)
    @key = key
    @value = value
  end
end

class DoubleLinkedList
  def initialize
    @head = Node.new(nil, nil)
    @tail = Node.new(nil, nil)
    @head.next = @tail
    @tail.prev = @head
  end

  # Adds node to the head of the list
  # @param node [Node]
  # @return [void]
  def prepend(node)
    second_to_head = @head.next

    node.prev = @head
    @head.next = node

    node.next = second_to_head
    second_to_head.prev = node
  end

  # Romevs node from the list
  # @return [void]
  def remove(node)
    prev_node = node.prev
    next_node = node.next

    prev_node.next = next_node
    next_node.prev = prev_node
  end

  def pop
    second_to_tail = @tail.prev

    @tail.prev = second_to_tail.prev
    second_to_tail.prev.next = @tail
    second_to_tail
  end
end

class LRUCache
=begin
    :type capacity: Integer
=end
  def initialize(capacity)
    @capacity = capacity
    @cache = {}
    @usage = DoubleLinkedList.new # from recent to least used keys
  end


=begin
    :type key: Integer
    :rtype: Integer
=end
  def get(key)
    return -1 unless @cache.has_key?(key)

    node = @cache[key]
    @usage.remove(node)
    @usage.prepend(node)
    node.value
  end


=begin
    :type key: Integer
    :type value: Integer
    :rtype: Void
=end
  def put(key, value)

    if @cache.has_key?(key)
      node = @cache[key]
      node.value = value
      @usage.remove(node)
    else
      node = Node.new(key, value)
      @cache[key] = node
    end

    @usage.prepend(node)

    if @cache.size > @capacity
      least_used = @usage.pop
      @cache.delete(least_used.key)
    end
  end
end

hash-based.rb

class LRUCache
=begin
    :type capacity: Integer
=end
    def initialize(capacity)        
        @capacity = capacity
        @cache = {}
    end


=begin
    :type key: Integer
    :rtype: Integer
=end
    def get(key)
        return -1 unless @cache.has_key?(key)
        value = @cache.delete(key)
        @cache[key] = value    
    end


=begin
    :type key: Integer
    :type value: Integer
    :rtype: Void
=end
    def put(key, value)
        if @cache.has_key?(key)
            @cache.delete(key)
        end
        @cache[key] = value 
        while @cache.size > @capacity
            @cache.shift
        end
    end
end