Implementing Cache Strategies in Go

Caching is a crucial technique for optimizing performance in many applications by storing frequently accessed data in a faster-access location. This challenge asks you to implement several common caching strategies in Go, demonstrating your understanding of cache eviction policies and their impact on performance. Successfully completing this challenge will provide a solid foundation for building efficient and scalable Go applications.

Problem Description

You are tasked with implementing a generic cache in Go that supports different eviction strategies. The cache should store key-value pairs, allowing retrieval, insertion, and deletion of data. The core requirement is to implement three eviction strategies: Least Recently Used (LRU), First-In, First-Out (FIFO), and Least Frequently Used (LFU).

What needs to be achieved:

1. Create a generic Cache interface that defines the basic cache operations: Get(key string) (interface{}, bool), Put(key string, value interface{}), and Delete(key string).
2. Implement three concrete cache structures: LRUCache, FIFOCache, and LFUCache, each conforming to the Cache interface.
3. Each cache implementation should utilize its respective eviction strategy when the cache reaches its maximum capacity.

Key Requirements:

• Genericity: The cache should be able to store any type of value.
• Concurrency Safety: The cache implementations should be thread-safe, allowing concurrent access from multiple goroutines. Use appropriate locking mechanisms (e.g., sync.Mutex).
• Capacity Limit: Each cache should have a maximum capacity.
• Eviction Strategies:
  • LRU: Evicts the least recently used item.
  • FIFO: Evicts the oldest item (first one added).
  • LFU: Evicts the least frequently used item.
• Return Values: Get should return the value associated with the key and a boolean indicating whether the key exists in the cache.

Expected Behavior:

• Put should add a new key-value pair to the cache. If the cache is full, it should evict an item based on the chosen eviction strategy before adding the new pair.
• Get should return the value associated with the key if it exists. If the key doesn't exist, it should return nil and false.
• Delete should remove the key-value pair associated with the key.

Edge Cases to Consider:

• Cache capacity of 0.
• Concurrent access from multiple goroutines.
• Retrieving a non-existent key.
• Adding duplicate keys (should overwrite the existing value).
• Deleting a non-existent key (should be a no-op).

Examples

Example 1: LRU Cache

Input: capacity = 2, operations = [Put("A", 1), Put("B", 2), Get("A"), Put("C", 3), Get("B")]
Output: [1, nil, 2] (representing the return values of Get("A") and Get("B"))
Explanation: The LRU cache initially stores "A" and "B".  Getting "A" makes it the most recently used.  Adding "C" evicts "B" because it was the least recently used.  Getting "B" returns nil because it was evicted.

Example 2: FIFO Cache

Input: capacity = 2, operations = [Put("A", 1), Put("B", 2), Get("A"), Put("C", 3), Get("B")]
Output: [1, nil]
Explanation: The FIFO cache initially stores "A" and "B". Getting "A" doesn't affect the order. Adding "C" evicts "A" because it was the first one added. Getting "B" returns nil because "A" was evicted.

Example 3: LFU Cache

Input: capacity = 2, operations = [Put("A", 1), Get("A"), Put("B", 2), Get("A"), Get("B"), Put("C", 3)]
Output: [1, 1, 2, nil]
Explanation: The LFU cache initially stores "A" with a frequency of 1 and "B" with a frequency of 1. Getting "A" increases its frequency to 2. Adding "C" evicts "B" because it has a frequency of 1, which is lower than "A"'s frequency of 2.

Constraints

• Cache capacity will be a positive integer.
• Keys will be strings.
• Values can be of any type (interface{}).
• The number of operations will be within a reasonable range (e.g., less than 1000).
• The implementation should be reasonably efficient. While absolute performance isn't the primary focus, avoid excessively inefficient data structures or algorithms. O(1) or O(log n) for Get, Put, and Delete are desirable.

Notes

• Consider using appropriate data structures like linked lists, maps, and counters to implement the eviction strategies efficiently.
• Think carefully about how to handle concurrency safely. Use mutexes to protect shared data structures.
• The Cache interface provides a clear contract for your cache implementations.
• Focus on correctness and clarity of code. Well-commented code is appreciated.
• You can assume that the input operations are valid (e.g., keys are not nil).
• You don't need to implement persistence (saving the cache to disk). The cache should reside in memory.
• Consider using a struct to hold the cache data and the mutex.