2018-10-23/24 LRU Cache [H]

  1. LRU Cache = LC: 146

Have Practiced: 0
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.

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):
        self.hash = {}
        self.head = LinkedNode() # dummy
        self.tail = self.head
        self.capacity = capacity

    # change "head -> node1 -> node2"
    # to "head -> node1 -> node2 -> node3"
    def push_back(self, node):
        self.hash[node.key] = self.tail
        self.tail.next = node
        self.tail = node
    
    # change "head -> node1 -> node2 -> node3"
    # to "head -> node2 -> node3"
    def pop_front(self,):
        del self.hash[self.head.next.key] # delete a reference, not node
        self.hash[self.head.next.next.key] = self.head
        self.head.next = self.head.next.next
    
    # change "head -> node -> node2"
    # to "head -> node2 -> node"
    def move_to_back(self, prev):
        node = prev.next
        if node == self.tail:
            return
        prev.next = node.next
        self.hash[node.next.key] = prev
        node.next = None
        self.push_back(node)
    
    """
    @param: key: An integer
    @return: An integer
    """
    def get(self, key):
        if key in self.hash:
            self.move_to_back(self.hash[key])
            return self.hash[key].next.value
        return -1

    """
    @param: key: An integer
    @param: value: An integer
    @return: nothing
    """
    def set(self, key, value):
        if key in self.hash:
            self.move_to_back(self.hash[key])
            self.hash[key].next.value = value
        else:
            self.push_back(LinkedNode(key, value))
            if len(self.hash) > self.capacity:
                self.pop_front()

Time: O(1) for all
Space: ``

Notes:

  1. I need to understand WHAT is LRU cache:
    Least Recently Used - The data you visited in the last round, you will very probably visit it in the next round.
  2. Use linked list in this problem, because I want to have pop_front(), push_back() and move_to_back().
    • Linked list takes least time, O(1), but not for move_to_back(). Therefore, use hash map(cache key, linked list node) to look up nodes in O(1) time
    • If I need to remove a node, I need to know its prev node. Therefore, Doubly linked list is needed. Or, use hash map(cache key, prev node) instead. Hash map works 1) adding another property of linked, prev. 2) easy to edit value of node.
  3. Learn to write LinkedNode() in Python.
    Remember to initialize all values to be None
def __init__(self, key=None, value=None, next=None):
  1. Relate this problem to First Unique Character in a String. A follow-up of this problem is data stream.

Extension:

  1. Python Tricks, use OrderedDict which has the same concept. Similar to LinkedHashMap in Java.
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        value = self.cache.pop(key) # take it out
        self.cache[key] = value # insert it back
        return value
        
    def set(self, key, value):
        if key in self.cache:
            self.cache.pop(key)
        elif len(self.cache) == self.capacity:
            ## last = True => FILO
            ## last = False => FIFO
            self.cache.popitem(last = False) # just pop head or tail, no key input
        self.cache[key] = value
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,452评论 0 10
  • 4/16加入的初心: 1.微商營銷太酷了,我要好好學微營銷 ! 2.一手江山一手心肝️️❤️❤️ 其实我很早就开始...
    沛沛小詩阅读 611评论 0 1
  • 1、工作继续跟wms做对接,顺便讨论和准备和AGV的对接。对于小公司,需要把握的一点是,那些事情你要全力向前冲,保...
    吕鹏_hunhun阅读 204评论 1 0
  • 想问世间的风雨 每一次都是为谁 还有划过天际的闪电 是为相遇 还是道别 不断旋转的年轮 留不住秋华春泥 我静守空...
    伏笔_ac61阅读 110评论 0 0
  • 2018年跟着亭主,开始关注财富、财务这块。 新年阅读的第一本有关金钱的书,就是《小狗钱钱》的作者博多.舍费尔写的...
    咏儿正向教养力阅读 636评论 2 4