Skip to content

Instantly share code, notes, and snippets.

@floriandejonckheere
Created March 31, 2023 06:04
Show Gist options
  • Save floriandejonckheere/5ee2272b65627b1df15fdb9f9ff0326f to your computer and use it in GitHub Desktop.
Save floriandejonckheere/5ee2272b65627b1df15fdb9f9ff0326f to your computer and use it in GitHub Desktop.
LRU cache
# frozen_string_literal: true
class LRUCache
attr_reader :capacity, :cache
def initialize(capacity)
@capacity = capacity
@cache = {}
end
def get(key)
cache[key] = cache.delete(key)
end
def put(key, value)
cache.delete(key)
cache[key] = value
evict
nil
end
private
def evict
return if cache.empty? || cache.count <= capacity
cache.delete(cache.keys.first)
end
end
cache = LRUCache.new(2)
cache.put(1, 1) # cache is {1=1}
cache.put(2, 2) # cache is {1=1, 2=2}
puts cache.get(1) # return 1
cache.put(3, 3) # LRU key was 2, evicts key 2, cache is {1=1, 3=3}
puts cache.get(2) # returns -1 (not found)
cache.put(4, 4) # LRU key was 1, evicts key 1, cache is {4=4, 3=3}
puts cache.get(1) # return -1 (not found)
puts cache.get(3) # return 3
puts cache.get(4) # return 4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment