LRU Cache Implementation with Concurrency Considerations

Design and implement an in-memory Least Recently Used (LRU) cache data structure.

Core Requirements

The cache must adhere to the following specifications:

• Fixed Capacity: It should have a fixed capacity N, specified during construction.
• Key-Value Pairs: Stores key-value pairs where both keys and values are integers, simplifying the implementation.
• Performance: All operations (get and put) must achieve an average time complexity of O(1).

Operations

get(key)

• If key exists in the cache, return its associated value and update its status to be the most recently used.
• If key does not exist, return -1.

put(key, value)

• Inserts or updates the key with the given value.
• If inserting a new key causes the total number of keys to exceed the fixed capacity N, the least recently used key must be evicted from the cache before the new key is inserted.

Implementation & Analysis

1. Describe the underlying data structures you would choose to achieve the O(1) average time complexity for both get and put operations.
2. Implement the LRUCache class, including its constructor (capacity), get(key), and put(key, value) methods.
3. Explain the time and space complexity of your implemented solution.

Follow-up: Concurrency and Thread Safety

1. How would you modify your LRU cache to ensure it is safe for use from multiple threads concurrently?
   • Discuss various approaches such as coarse-grained locking, fine-grained locking, or leveraging concurrent data structures.
   • Analyze the trade-offs associated with each approach, considering factors like simplicity, potential for contention, and overall performance.
2. Identify specific race conditions or consistency issues that could arise if multiple threads simultaneously invoke get and put operations on your cache. Explain how your proposed concurrent design effectively prevents these issues.