7. Design an LRU cache and a rate limiter

public sealed class LruCache<TKey, TValue>(int capacity) where TKey : notnull
{
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _map = [];
    private readonly LinkedList<(TKey Key, TValue Value)> _order = new();   // front = most recent
    private readonly Lock _lock = new();

    public bool TryGet(TKey key, out TValue value)
    {
        lock (_lock)
        {
            if (_map.TryGetValue(key, out var node))
            {
                _order.Remove(node); _order.AddFirst(node);        // mark as recently used
                value = node.Value.Value; return true;
            }
            value = default!; return false;
        }
    }

    public void Put(TKey key, TValue value)
    {
        lock (_lock)
        {
            if (_map.TryGetValue(key, out var existing)) _order.Remove(existing);
            else if (_map.Count == capacity) { _map.Remove(_order.Last!.Value.Key); _order.RemoveLast(); }   // evict least recent
            _map[key] = _order.AddFirst((key, value));
        }
    }
}

public sealed class TokenBucket(int capacity, double refillPerSecond, TimeProvider clock)
{
    private double _tokens = capacity;
    private DateTimeOffset _last = clock.GetUtcNow();
    private readonly Lock _lock = new();

    public bool TryTake()
    {
        lock (_lock)
        {
            var now = clock.GetUtcNow();
            _tokens = Math.Min(capacity, _tokens + (now - _last).TotalSeconds * refillPerSecond);
            _last = now;
            if (_tokens < 1) return false;
            _tokens -= 1; return true;
        }
    }
}

public sealed class RateLimiter(Func<TokenBucket> create)
{
    private readonly ConcurrentDictionary<string, TokenBucket> _buckets = new();
    public bool Allow(string userId) => _buckets.GetOrAdd(userId, _ => create()).TryTake();
}