Least Recently Used cache in changed slightly from this: https://www.sitepoint.com/ruby-interview-questions-lru-cache-and-binary-trees/

lru.rb

#!/usr/bin/env ruby

# Doubly Linked List
Node = Struct.new(:key, :value, :next, :prev)

class LRU
  attr_accessor :head, :tail, :max, :cache
  def initialize(max)
    @head = nil
    @tail = nil
    @max = max
    @cache = {}
  end

  def set(key, value)
    @cache[key] = Node.new(key, value)
    reorder(@cache[key])

    if @cache.size > @max
      prev_tail = @tail.prev
      prev_tail.next = nil
      @tail = prev_tail
      @cache.delete(@tail.key)
    end
  end

  def get(key)
    node = @cache[key]
    return nil unless node
    reorder(node)
  end

  def reorder(node)
    node.next = @head
    @head.prev = node if @head
    @head = node
    @tail = node.next unless @tail
  end
end

require 'minitest/autorun'
require 'pry'

describe LRU do
  before do
    @lru = LRU.new(3)
    @lru.set('a', 1)
    @lru.set('b', 2)
    @lru.set('c', 3)
  end

  describe 'set' do
    it "should set many keys and pop things off at the max" do
      @lru.set('foo', 8)
      @lru.head.value.must_equal(8)
      @lru.tail.value.must_equal(2)
    end
  end

  describe 'get' do
    it "should get keys from the list and reorder" do
      @lru.get('b')
      @lru.head.value.must_equal(2)
      @lru.tail.value.must_equal(1)
      @lru.cache.keys.size.must_equal(3)
      @lru.cache.size.must_equal(3)
    end
  end
end