LRU Cache

Problem Statement

Design a data structure that supports the following two operations:

• insert(key, value)
  : Inserts a
  key-value
  pair into the data structure.
• get(key)
  : Returns the value associated with the given
  key
  . If the
  key
  is not found, returns
  -1
  .

The data structure should maintain a Least Recently Used (LRU) cache. When the cache reaches its capacity, the oldest item should be removed first.

Rules and Constraints

• The
  insert
  operation takes
  key
  and
  value
  as input, and returns
  null
  .
• The
  get
  operation takes
  key
  as input and returns the associated
  value
  if found, or
  -1
  otherwise.
• The cache has a fixed capacity
  capacity
  .
• The data structure should use the most efficient time and space complexity.
• The
  insert
  operation should update the LRU order of the keys in the cache.
• The
  get
  operation should return the value associated with the given
  key
  if it exists in the cache, without modifying the LRU order.
• If the cache is empty or does not contain the given
  key
  ,
  get
  should return
  -1
  .

Assumptions

• The
  key
  and
  value
  are integers.
• The
  capacity
  is a positive integer.
• The input data is valid (i.e., the number of operations will not exceed the capacity).

Metrics for Success

• The data structure should implement the
  insert
  and
  get
  operations efficiently (i.e., with low time complexity).
• The data structure should maintain the LRU order of the keys in the cache.
• The data structure should use a reasonable amount of space (i.e., linear or sublinear with respect to the input data).

Example

Input: {"capacity":2,"ops":["put","put","get"]} Output: [null,null,1]