Design

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support get and put operations.

  • get(key): Get the value (which 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.

Can you do both operations in O(1) time complexity?

Input:

operations = ['LRUCache','put','put','get','put','get','put','get','get','get']
input = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

Output:

[null,null,null,1,null,-1,null,-1,3,4]

Try it yourself

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade