Implementing an LRU Cache Component in Vue.js

This challenge requires you to build a Vue.js component that functions as a Least Recently Used (LRU) cache. An LRU cache is a common data structure used to manage a fixed amount of memory, evicting the least recently accessed item when the cache reaches its capacity. This is particularly useful for optimizing performance in web applications by storing frequently accessed data client-side.

Problem Description

You are tasked with creating a Vue.js component, LruCache, that simulates an LRU cache. This component should accept a capacity prop, defining the maximum number of items it can hold.

Key Requirements:

1. capacity Prop: The component must accept an integer capacity prop that determines the maximum number of key-value pairs the cache can store.
2. get(key) Method: Implement a method get(key) that retrieves the value associated with a given key.
   • If the key exists, return its value and mark it as the most recently used.
   • If the key does not exist, return undefined (or a similar indicator of absence).
3. put(key, value) Method: Implement a method put(key, value) that adds or updates a 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 full, add the new key-value pair and mark it as the most recently used.
     • If the cache is full, evict the least recently used item to make space for the new item, and then add the new key-value pair, marking it as the most recently used.
4. LRU Eviction: The cache must correctly identify and evict the least recently used item when it reaches its capacity and a new item needs to be added. The most recently used item should be the one that was accessed or put most recently.

Expected Behavior:

The LruCache component should internally manage its state representing the cached items and their usage order. The get and put methods will modify this internal state according to the LRU eviction policy.

Edge Cases:

• Cache with capacity 0 or 1.
• Putting an item when the cache is at full capacity.
• Getting an item that doesn't exist.
• Updating an existing item.

Examples

Example 1:

Input:
capacity = 2

const cache = new LruCache({ capacity: 2 });
cache.put('a', 1); // cache: { 'a': 1 } (most recent: 'a')
cache.put('b', 2); // cache: { 'a': 1, 'b': 2 } (most recent: 'b')
const val1 = cache.get('a'); // returns 1, cache: { 'b': 2, 'a': 1 } (most recent: 'a')
cache.put('c', 3); // evicts 'b' (least recent), cache: { 'a': 1, 'c': 3 } (most recent: 'c')
const val2 = cache.get('b'); // returns undefined
const val3 = cache.get('c'); // returns 3, cache: { 'a': 1, 'c': 3 } (most recent: 'c')

Output:
val1 = 1
cache state after val1 = { 'b': 2, 'a': 1 }
cache state after put('c', 3) = { 'a': 1, 'c': 3 }
val2 = undefined
val3 = 3
cache state after val3 = { 'a': 1, 'c': 3 }

Explanation:
The cache starts with capacity 2. 'a' and 'b' are added. Getting 'a' makes it the most recent. When 'c' is added, 'b' (the least recently used) is evicted. Getting 'b' returns undefined as it was evicted. Getting 'c' returns its value and makes it the most recent.

Example 2:

Input:
capacity = 1

const cache = new LruCache({ capacity: 1 });
cache.put('x', 10); // cache: { 'x': 10 } (most recent: 'x')
const val1 = cache.get('x'); // returns 10, cache: { 'x': 10 } (most recent: 'x')
cache.put('y', 20); // evicts 'x', cache: { 'y': 20 } (most recent: 'y')
const val2 = cache.get('x'); // returns undefined

Output:
val1 = 10
cache state after put('y', 20) = { 'y': 20 }
val2 = undefined

Explanation:
With a capacity of 1, adding 'y' immediately evicts 'x' because 'x' was the only item and is now considered least recently used after 'y' is put.

Constraints

• capacity will be a non-negative integer.
• Keys will be strings.
• Values can be of any type.
• The component should be reasonably efficient, aiming for average O(1) time complexity for get and put operations.

Notes

• Consider how you will maintain the order of accessed items. A common approach involves using a doubly linked list in conjunction with a hash map (or JavaScript Map).
• You will need to leverage Vue's reactivity system if you want the cache's contents to be observable or if you plan to display its state within a Vue template. For this challenge, focus on the core LRU logic within the component's methods.
• The challenge is to implement the logic of the LRU cache within a Vue component, not necessarily to build a visually interactive UI for it, although that would be a good extension.