Implement an LRU Cache in JavaScript

This challenge asks you to implement a Least Recently Used (LRU) cache. An LRU cache is a memory management technique that discards the least recently used items first when the cache is full. This is a common data structure used in various applications to optimize performance by keeping frequently accessed data readily available in memory.

Problem Description

You need to design and implement a JavaScript class LRUCache that supports two primary operations: get(key) and put(key, value). The cache will have a fixed capacity.

Key Requirements:

1. get(key):

   • Retrieves the value associated with the given key.
   • If the key exists in the cache, it should return the corresponding value and mark this key as the most recently used.
   • If the key does not exist, it should return -1.

2. put(key, value):

   • Inserts or updates the key-value pair in the cache.
   • If the key already exists, update its value and mark it as the most recently used.
   • If the key does not exist:
     • If the cache is not yet full, simply add the new key-value pair and mark it as the most recently used.
     • If the cache is full, it must evict the least recently used item before inserting the new key-value pair and marking it as the most recently used.

Expected Behavior:

• The cache should maintain an order of usage, where the most recently accessed or updated item is considered the "most recently used" and the item that hasn't been accessed or updated for the longest time is considered the "least recently used".
• When the cache reaches its capacity and a new item needs to be inserted, the least recently used item is removed to make space.

Edge Cases:

• Putting a key that already exists.
• Getting a key that doesn't exist.
• Cache capacity of 1.
• Empty cache.

Examples

Example 1:

Input:
capacity = 2
operations = [
  ["put", 1, 1],
  ["put", 2, 2],
  ["get", 1],      // returns 1
  ["put", 3, 3],   // evicts key 2
  ["get", 2],      // returns -1 (not found)
  ["put", 4, 4],   // evicts key 1
  ["get", 1],      // returns -1 (not found)
  ["get", 3],      // returns 3
  ["get", 4]       // returns 4
]

Output:
[1, -1, -1, 3, 4]

Explanation:
1. LRUCache(2) created.
2. put(1, 1): cache is {1=1}. Most recently used: 1.
3. put(2, 2): cache is {1=1, 2=2}. Most recently used: 2, Least recently used: 1.
4. get(1): returns 1. Cache is {2=2, 1=1}. Most recently used: 1, Least recently used: 2.
5. put(3, 3): Cache is full. Evict key 2 (least recently used). cache is {1=1, 3=3}. Most recently used: 3, Least recently used: 1.
6. get(2): returns -1.
7. put(4, 4): Cache is full. Evict key 1 (least recently used). cache is {3=3, 4=4}. Most recently used: 4, Least recently used: 3.
8. get(1): returns -1.
9. get(3): returns 3. Cache is {4=4, 3=3}. Most recently used: 3, Least recently used: 4.
10. get(4): returns 4. Cache is {3=3, 4=4}. Most recently used: 4, Least recently used: 3.

Example 2:

Input:
capacity = 1
operations = [
  ["put", 10, 5],
  ["get", 10],     // returns 5
  ["put", 20, 10], // evicts key 10
  ["get", 10],     // returns -1
  ["get", 20]      // returns 10
]

Output:
[5, -1, 10]

Explanation:
1. LRUCache(1) created.
2. put(10, 5): cache is {10=5}. MRU: 10.
3. get(10): returns 5. Cache is {10=5}. MRU: 10.
4. put(20, 10): cache is full. Evicts 10. cache is {20=10}. MRU: 20.
5. get(10): returns -1.
6. get(20): returns 10. Cache is {20=10}. MRU: 20.

Constraints

• 1 <= capacity <= 1000
• 1 <= key, value <= 10000
• The number of operations will be between 1 and 1000.
• Keys and values will be integers.
• The operations array will contain valid operations.

Notes

• You will need to store both the key-value pairs and the order of usage efficiently.
• Consider how you can achieve O(1) time complexity for both get and put operations. A combination of data structures might be helpful.
• The LRUCache class should have a constructor that takes the capacity as an argument.
• The get and put methods should be part of the LRUCache class.