LRU Cache

Question

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and `set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Thoughts

Reference

LRU cache数据结构的核心就是当存储空间满了，而有新的item要插入时，要先丢弃最早更新的item。这里的数据结构需要符合以下条件：

1. 要能快速找到最早更新的item。这里需要将item以更新时间顺序排序。 可选的有：queue，heap，linked list

2. 要能快速访问指定item，并且访问以后要更新它的时间顺序。 对于更新时间顺序这个操作，queue和heap要做到就很困难了。所以这点最佳的是linked list。但linked list中查找指定item需要遍历，这里可以用一个hash table来记录key与节点之间的对应。并且由于要随时更新节点位置，doubly linked list更为适用。(也可以不用doubly linked list, 在hashmap总存listnode的前一个，并且用head和tail来track list的头尾就可以)

linked list最尾部的表示最新访问的

get(key)

• 把node放到尾部
• 读取value

set(key, value)

如果key已经有了

• 放到尾部
• 更新value

如果key还没有

• 放到尾部
• 如果 size > capacity, 讲头部的node pop掉

因为头部和尾部都不确定，所以就像linkedlist要有dummy node一样，要有一个head和tail

head一直不变，指向第一个node（表示least recently used） tail一直指向最后一个node，每次更新(表示mose recently used)

Solution

class LinkedNode:

    def __init__(self, key=None, value=None, next=None):
        self.key = key
        self.value = value
        self.next = next

class LRUCache:

    # @param capacity, an integer
    def __init__(self, capacity):
        # write your code here
        #hash
        #key: key
        #value: prev ListNode in the linkedlist
        self.hash = {}
        self.head = LinkedNode()
        self.tail = self.head
        self.capacity = capacity

    def pushTail(self, node):
        self.hash[node.key] = self.tail
        self.tail.next = node
        self.tail = node
        node.next = None

    def popFront(self):
        del self.hash[self.head.next.key]
        self.head.next = self.head.next.next
        self.hash[self.head.next.key] = self.head

    def updateLink(self, prev):
        node = prev.next
        #if already tail, no need to update
        if node == self.tail:
            return
        else:
            prev.next = node.next
            if node.next:
                self.hash[node.next.key] = prev


    # @return an integer
    def get(self, key):
        # write your code here
        if key not in self.hash:
            return -1
        else:
            #key in hash
            #1. update node's prev and next
            #2. put node to tail
            prev = self.hash[key]
            node = prev.next
            if node != self.tail:
                self.updateLink(prev)
                self.pushTail(node)
            return self.hash[key].next.value

    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        # write your code here
        if key in self.hash:
            #key in hash
            #1. update node's prev and next
            #2. put node to tail
            prev = self.hash[key]
            node = prev.next
            if node != self.tail:
                self.updateLink(prev)
                self.pushTail(node)
            self.hash[key].next.value = value
        else:
            node = LinkedNode(key, value) 
            #1. put node to tail
            #2. if size > cap, pop lru node
            self.pushTail(node)
            if len(self.hash) > self.capacity:
                self.popFront()

the part to determine if it's tail & updateLink and pushTail can be combined into updateLink()

    def updateLink(self, prev):
        node = prev.next
        #if already tail, no need to update
        if node == self.tail:
            return
        else:
            prev.next = node.next
            if node.next:
                self.hash[node.next.key] = prev
            #change
            self.pushTail(node)

    # @return an integer
    def get(self, key):
        # write your code here
        if key not in self.hash:
            return -1
        else:
            #change
            prev = self.hash[key]
            self.updateLink(prev)
            return self.hash[key].next.value

    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        # write your code here
        if key in self.hash:
            #change
            prev = self.hash[key]
            self.updateLink(prev)
            self.hash[key].next.value = value
        else:
            node = LinkedNode(key, value) 
            #1. put node to tail
            #2. if size > cap, pop lru node
            self.pushTail(node)
            if len(self.hash) > self.capacity:
                self.popFront()