text: # Time:  O(1), per operation.
  # Space: O(k), k is the capacity of cache.
  
  # Design and implement a data structure for Least Recently Used (LRU) cache.
  # It should support the following operations: get and put.
  #
  # get(key) - Get the value (will always be positive) of the key if the key exists in the cache,
  # otherwise return -1.
  # put(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.
  #
  # Follow up:
  # Could you do both operations in O(1) time complexity?
  #
  # Example:
  #
  # LRUCache cache = new LRUCache( 2 /* capacity */ );
  #
  # cache.put(1, 1);
  # cache.put(2, 2);
  # cache.get(1);       // returns 1
  # cache.put(3, 3);    // evicts key 2
  # cache.get(2);       // returns -1 (not found)
  # cache.put(4, 4);    // evicts key 1
  # cache.get(1);       // returns -1 (not found)
  # cache.get(3);       // returns 3
  
  class ListNode(object):
      def __init__(self, key, val):
          self.val = val
          self.key = key
          self.next = None
          self.prev = None
  
  class LinkedList(object):
      def __init__(self):
          self.head = None
          self.tail = None
  
      def insert(self, node):
          node.next, node.prev = None, None  # avoid dirty node
          if self.head is None:
              self.head = node
          else:
              self.tail.next = node
              node.prev = self.tail
          self.tail = node
  
      def delete(self, node):
          if node.prev:
              node.prev.next = node.next
          else:
              self.head = node.next
          if node.next:
              node.next.prev = node.prev
          else:
              self.tail = node.prev
          node.next, node.prev = None, None  # make node clean
  
  class LRUCache(object):
  
      # @param capacity, an integer
      def __init__(self, capacity):
          self.list = LinkedList()
          self.dict = {}
          self.capacity = capacity
  
      def _insert(self, key, val):
          node = ListNode(key, val)
          self.list.insert(node)
          self.dict[key] = node
  
  
      # @return an integer
      def get(self, key):
          if key in self.dict:
              val = self.dict[key].val
              self.list.delete(self.dict[key])
              self._insert(key, val)
              return val
          return -1
  
  
      # @param key, an integer
      # @param value, an integer
      # @return nothing
      def put(self, key, val):
          if key in self.dict:
              self.list.delete(self.dict[key])
          elif len(self.dict) == self.capacity:
              del self.dict[self.list.head.key]
              self.list.delete(self.list.head)
          self._insert(key, val)
  
  
  import collections
  class LRUCache2(object):
      def __init__(self, capacity):
          self.cache = collections.OrderedDict()
          self.capacity = capacity
  
      def get(self, key):
          if key not in self.cache:
              return -1
          val = self.cache[key]
          del self.cache[key]
          self.cache[key] = val
          return val
  
      def put(self, key, value):
          if key in self.cache:
              del self.cache[key]
          elif len(self.cache) == self.capacity:
              self.cache.popitem(last=False)
          self.cache[key] = value
  
  
  if __name__ == "__main__":
      cache = LRUCache(3)
      cache.set(1, 1)
      cache.set(2, 2)
      cache.set(3, 3)
      print cache.get(1)
      cache.set(4, 4)
      print cache.get(2)
  
  