Overview

This problem challenges you to design a Least Recently Used (LRU) cache that manages items with varying memory sizes, instead of a fixed count. This requires the cache to consider total occupied capacity rather than just the number of entries when making eviction decisions. Implementing this CapacityAwareLRUCache will strengthen your understanding of hash maps and doubly linked lists for efficient cache management.

What you need to do / Task

Implement the CapacityAwareLRUCache class with the following methods:

1. constructor(capacity: number): Initializes the cache with a total byte capacity. This is the maximum sum of sizes of all items the cache can hold.
2. get(key: number): number: Retrieves the value associated with key. If key exists in the cache, return its value and mark it as recently used. Otherwise, return -1.
3. put(key: number, value: number, size: number): void: Inserts or updates an item in the cache. The size parameter indicates the memory footprint of the item.
   • If key already exists, update its value and size, then mark it as recently used.
   • If key does not exist, add the new key-value pair with its size.
   • Capacity constraint: If the size of a new item (or the new size of an updated item) is greater than the cache's total capacity, that item cannot be stored or updated. In such a case, for a new item, do nothing. For an existing item, its value and size should not be updated, and it remains in its current state and position.
   • Eviction policy: If adding or updating an item causes the total occupied capacity to exceed the cache's capacity, evict the least recently used items until enough space is freed. Items must be evicted one by one, starting from the least recently used.

Input & output

The problem requires you to implement a class CapacityAwareLRUCache.

Class Definition

class CapacityAwareLRUCache {
  constructor(capacity: number);
  get(key: number): number;
  put(key: number, value: number, size: number): void;
}

Example Operations

Operations will be provided as an array of method calls, and parameters as an array of arrays.

Input Format: operations = ["CapacityAwareLRUCache", "put", "put", "get", ...], params = [[capacity], [key, value, size], [key, value, size], [key], ...]

Output Format: An array of results for get operations, or null for constructor and put operations.

Clarifications

• Q: What are the valid ranges for key, value, size, and capacity?
  • key, value, size, and capacity will be positive integers, except for capacity which can be 0.
• Q: What happens if capacity is 0?
  • If capacity is 0, the cache cannot store any items. put operations will effectively do nothing, and get operations will always return -1.
• Q: How should tie-breaking be handled if multiple items have the same 'least recently used' status?
  • The LRU policy is strictly defined by the order of access. A doubly linked list is the standard way to maintain this order, where the head is most recently used and the tail is least recently used. There are no ties in this context.
• Q: If an item's new size (during a put operation for an existing item) is smaller than its old size, does it still count as being 'recently used'?
  • Yes, any put or get operation on an existing key marks it as recently used, moving it to the front of the LRU order, as long as the update is valid (i.e., new size doesn't exceed total capacity).