Algorithm - Design (1)

Leetcode Data Structure Design Problem Set (1)

• 146.LRU Cache
• 284.Peeking Iterator
• 341.Flatten Nested List Iterator
• 295.Find Median from Data Stream

146. LRU Cache

Design Least Recently Used (LRU) Cache
Use double-linked list as cache, disconnect the old node and reconnect it to the tail of the list when get an value. add new node to the tail and drop the first (the least used) node if exceed capacity.
use a dictionary to log {key: node}

class Node:
    def __init__(self, k=0, v=0):
        self.k = k
        self.v = v
        self.prev = None
        self.next = None
        
class LRUCache:

    def __init__(self, capacity: int):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.dict = {}
        self.cap = capacity
    
    def _remove(self, node):
        # remove the least used node
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add(self, node):
        last = self.tail.prev
        self.tail.prev = node
        last.next = node
        node.next = self.tail
        node.prev = last
    
    
    def get(self, key: int) -> int:
        if key not in self.dict:
            return -1
        
        # move recent used node to tail
        node = self.dict[key]
        self._remove(node)
        self._add(node)
        return node.v
        

    def put(self, key: int, value: int) -> None:
        # remove the existed key first, we will add new anyway
        if key in self.dict:
            node = self.dict[key]
            self._remove(node)
            del self.dict[key]
        
        node = Node(key, value)
        self._add(node)
        self.dict[key] = node
        
        if len(self.dict) > self.cap:
            least = self.head.next
            self._remove(least)
            del self.dict[least.k]

284. Peeking Iterator

My initial idea was create a one-way linked list, or initialize a normal list, which is too easy. But if so, it lose the meaning as iterator. Then I second thought, I don’t even need a list, I just need a buffer for the peak value.

class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self._iterator = iterator
        self._peak = None
        

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if not self._peak and self._iterator.hasNext():
            self._peak = self._iterator.next()
        return self._peak

    def next(self):
        """
        :rtype: int
        """
        if self._peak:
            peak = self._peak
            self._peak = None
            return peak
        
        return self._iterator.next()

    def hasNext(self):
        """
        :rtype: bool
        """
        if self._peak:
            return True
        return self._iterator.hasNext()

341. Flatten Nested List Iterator

Flatten nested list in init. Use deque to faster pop the first element.

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.ls = deque()
        self.flatten(nestedList)
        
    
    def flatten(self, nestedList):
        for l in nestedList:
            if l.isInteger():
                self.ls.append(l.getInteger())
            else:
                self.flatten(l.getList())      
    
    def next(self) -> int:
        return self.ls.popleft() if self.hasNext else None
            
    
    def hasNext(self) -> bool:
        return len(self.ls) > 0

295. Find Median from Data Stream

Dividing data into 2 heaps (length as equal as possible):

• Use max heap to store a chunk of smaller elements
• Use min heap to store another chunk of larger elements.
  Reference:
  https://mp.weixin.qq.com/s/oklQN_xjYy--_fbFkd9wMg

import heapq

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.small = []  # store smaller data, maxHeap
        self.large = []  # store larger data, minHeap

    def addNum(self, num: int) -> None:
        
        # insert into large
        if len(self.small) >= len(self.large):
            heapq.heappush(self.small, -num)
            heapq.heappush(self.large, -heapq.heappop(self.small))
        else:
            heapq.heappush(self.large, num)
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return  -self.small[0]
        elif len(self.large) > len(self.small):
            return self.large[0]
        else:
            # even len
            return (-self.small[0] + self.large[0]) / 2