Sept 20, 2020 - LRU cache design - double linked list - interviewee is an excellent programmer

LRU.rb

# 
# Your previous Plain Text content is preserved below:
# 
# Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
# 
# Implement the LRUCache class:
# 
# LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
# int get(int key) Return the value of the key if the key exists, otherwise return -1.
# void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
# Follow up:
# Could you do get and put in O(1) time complexity?
# 
#  
# 
# Example 1:
# 
# Input
# ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
# [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
# Output
# [null, null, null, 1, null, -1, null, -1, 3, 4]

=begin
  hashmap + double linked-list
  
  put
    - if at capacity, remove tail of DLL
    - add key and node to hashmap
    - insert at begining of DLL
    
  get
    - query hashmap
    - move node to beginning of DLL

=end

class DLL
  class Node
    attr_accessor :val, :key, :next, :prev
    def initialize(key = nil, val = nil)
      @val = val
      @key = key
      @next = nil
      @prev = nil
    end
  end
  
  def initialize
    @head = Node.new
    @tail = Node.new
    @head.next = @tail  # not empty, dummy head, dummy tail
    @tail.prev = @head
    
    # @head.prev = @tail; 
  end
  
=begin
  X   Y   Z    
    
=end
  def move_to_front(node)
    node.prev.next = node.next  # two nodes left 
    node.next.prev = node.prev
    # node.next = @head.next
    # node.prev = @head
    # @head.next = node
    push_left(node)
  end
  
  def push_left(node)
    node.next = @head.next
    node.prev = @head
    @head.next = node
  end
  
=begin
       
  H -----> T

=end
  def pop
    node = @tail.prev   # eviction - remove last node before tail
    node.prev.next = @tail
    @tail.prev = node.prev
    node   # return node
  end
end

class LRUCache

=begin
    :type capacity: Integer
=end
    def initialize(capacity)
      raise "Capacity must be greater than 0" if capacity <= 0
      @size = 0
      @capacity = capacity
      @map = {}
      @list = DLL.new
    end


=begin
    :type key: Integer
    :rtype: Integer
=end
    def get(key)
      return -1 unless @map[key]
      @list.move_to_front(@map[key])
      @map[key].val
    end


=begin
    :type key: Integer
    :type value: Integer
    :rtype: Void
=end
    def put(key, value)
      if @map[key]
        @map[key].val = value   # update map - push left 
        @list.move_to_front(@map[key])
      else
        if @size == @capacity
          # REMOVE LRU elem
          node = @list.pop
          @map.delete(node.key)
          @size -= 1   # -1, later +1, if check map size, no need to have @size
        end
        @map[key] = DLL::Node.new(key, value)
        @list.push_left(@map[key])
        @size += 1
      end
    end
end

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache.new(capacity)
# param_1 = obj.get(key)
# obj.put(key, value)

The design of DLL APIs are perfect with meaningful names, and all the code of double linked list are encapsulated very well.