Implementing Cache Strategies in Go

Caching is a fundamental technique for improving the performance of applications by storing frequently accessed data in a faster, more accessible location. This challenge will test your ability to implement and manage different caching strategies in Go, focusing on common patterns like Least Recently Used (LRU) and First-In, First-Out (FIFO). A well-implemented cache can significantly reduce latency and database load.

Problem Description

You are tasked with building a generic cache system in Go that supports different eviction policies. The cache should be able to store key-value pairs, where keys and values can be of any type. You need to implement at least two common cache eviction strategies:

1. Least Recently Used (LRU): When the cache reaches its capacity, the item that has not been accessed for the longest time is evicted.
2. First-In, First-Out (FIFO): When the cache reaches its capacity, the item that was added to the cache first is evicted, regardless of its usage.

Your implementation should provide the following operations:

• NewCache(capacity int, strategy string) (*Cache, error): Constructor to create a new cache with a specified capacity and eviction strategy. It should return an error if the strategy is invalid or capacity is non-positive.
• Set(key, value interface{}): Adds or updates a key-value pair in the cache. If the cache is full, an item will be evicted according to the chosen strategy before adding the new item.
• Get(key interface{}) (interface{}, bool): Retrieves a value associated with a key. Returns the value and true if the key exists, otherwise returns nil and false. For LRU, accessing a key should mark it as recently used.
• Delete(key interface{}): Removes a key-value pair from the cache.
• Len() int: Returns the current number of items in the cache.

Key Requirements:

• The cache must be thread-safe. Multiple goroutines should be able to access and modify the cache concurrently without data corruption.
• The strategy parameter in NewCache should accept "lru" and "fifo" (case-insensitive).
• The Get operation for LRU must update the "recency" of the accessed item.

Edge Cases:

• Setting a key that already exists should update its value and, for LRU, reset its recency.
• Getting a non-existent key should return nil, false.
• Deleting a non-existent key should be a no-op.
• Cache capacity of 0 or negative should result in an error.
• An unknown eviction strategy should result in an error.

Examples

Example 1: LRU Cache

Input:
capacity = 2
strategy = "lru"
cache := NewCache(capacity, strategy)

cache.Set("a", 1) // Cache: {"a": 1}
cache.Set("b", 2) // Cache: {"a": 1, "b": 2}

val, ok := cache.Get("a") // val: 1, ok: true. Accessing "a" makes it most recently used.
// Cache state after Get("a"): {"b": 2, "a": 1} (logical order of recency: a, b)

cache.Set("c", 3) // Cache is full. "b" is least recently used, so it's evicted.
// Cache: {"a": 1, "c": 3}

val, ok = cache.Get("b") // val: nil, ok: false. "b" was evicted.

Example 2: FIFO Cache

Input:
capacity = 2
strategy = "fifo"
cache := NewCache(capacity, strategy)

cache.Set("a", 1) // Cache: {"a": 1}
cache.Set("b", 2) // Cache: {"a": 1, "b": 2}

cache.Set("c", 3) // Cache is full. "a" was added first, so it's evicted.
// Cache: {"b": 2, "c": 3}

val, ok := cache.Get("a") // val: nil, ok: false. "a" was evicted.

val, ok = cache.Get("b") // val: 2, ok: true.

Example 3: Edge Case - Updating and Deleting

Input:
capacity = 3
strategy = "lru"
cache := NewCache(capacity, strategy)

cache.Set("x", 10)
cache.Set("y", 20)
cache.Set("z", 30) // Cache: {"x": 10, "y": 20, "z": 30}

cache.Set("x", 100) // Update value of "x". For LRU, "x" becomes most recently used.
// Cache: {"y": 20, "z": 30, "x": 100} (logical order of recency: x, z, y)

cache.Delete("y") // Delete "y".
// Cache: {"z": 30, "x": 100}

val, ok := cache.Get("y") // val: nil, ok: false.

Constraints

• Cache capacity will be an integer between 1 and 100,000.
• Keys and values can be any Go interface{} type.
• The number of Set and Get operations per test case will not exceed 1,000,000.
• The cache operations (Set, Get, Delete) should aim for an average time complexity of O(1).

Notes

• For the LRU strategy, you'll likely need a data structure that allows efficient tracking of access order. A combination of a map for O(1) lookups and a doubly linked list for O(1) insertions/deletions/reordering might be suitable.
• For the FIFO strategy, a map for lookups and a queue (e.g., using a slice or container/list) for tracking insertion order would be effective.
• Remember to use mutexes (e.g., sync.RWMutex) to ensure thread safety for all cache operations.
• Consider how to handle the case where a nil key or value is passed to Set or Get. The problem statement implies interface{}, so nil is a valid value.
• Case-insensitivity for the strategy string is important.