Case study: Mock interview - L146 LRU cache - Ruby

 Here is the link. 

	#
	# 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)

view raw LRU.rb hosted with ❤ by GitHub