new_contents: """Leetcode 146. LRU Cache
  Medium
  
  URL: https://leetcode.com/problems/lru-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.
  
  The cache is initialized with a positive capacity.
  
  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
  cache.get(4);       // returns 4
  
  Follow up:
  Could you do both operations in O(1) time complexity?
  
  Your LRUCache object will be instantiated and called as such:
  obj = LRUCache(capacity)
  param_1 = obj.get(key)
  obj.put(key, value)
  """
  
  class LRUCache(object):
      def __init__(self, capacity):
          """Least recently used cache.
          :type capacity: int
          """
          pass
  
      def get(self, key):
          """
          :type key: int
          :rtype: int
          """
          pass
  
      def put(self, key, value):
          """
          :type key: int
          :type value: int
          :rtype: None
          """
          pass
  
  
  def main():
      pass
  
  
  if __name__ == '__main__':
      main()
  
subject: Add lc0146_lru_cache.py