Write a simple in-memory fixed-window rate limiter for interview purposes.

Implement Allow(string key) for a process-local fixed-window limiter with a permit limit, window duration, injected TimeProvider, and a maximum number of tracked keys. Return true when the request is allowed and false when the key has exhausted its permits or the bounded key table cannot accept a new key.

Limit 3 per minute for key user-1: first three calls return true, fourth call in the same minute returns false, a call after the window resets returns true.

• Blank keys are rejected.
• Each key has an independent counter.
• When elapsed time reaches the window duration, start a new window.
• Expired keys are removed and the key table has an explicit upper bound.
• This is a thread-safe, process-local interview implementation, not a distributed production limiter.

I keep one counter per key and use TimeProvider so elapsed time is deterministic in tests. Under one lock, I periodically remove expired counters, reset the current key when its window expires, and enforce a maximum tracked-key count before accepting a new key. That bounds stale and adversarial key growth while keeping the example focused. It is still process-local; multiple app instances need a shared limiter or gateway policy.

public sealed class FixedWindowRateLimiter
{
    private const int SweepInterval = 256;
    private readonly int _permitLimit;
    private readonly int _maxTrackedKeys;
    private readonly TimeSpan _window;
    private readonly TimeProvider _timeProvider;
    private readonly object _gate = new();
    private readonly Dictionary<string, Counter> _counters =
        new(StringComparer.Ordinal);
    private int _requestsSinceSweep;

    public FixedWindowRateLimiter(
        int permitLimit,
        TimeSpan window,
        int maxTrackedKeys,
        TimeProvider? timeProvider = null)
    {
        if (permitLimit <= 0)
            throw new ArgumentOutOfRangeException(nameof(permitLimit));
        if (window <= TimeSpan.Zero)
            throw new ArgumentOutOfRangeException(nameof(window));
        if (maxTrackedKeys <= 0)
            throw new ArgumentOutOfRangeException(nameof(maxTrackedKeys));

        _permitLimit = permitLimit;
        _window = window;
        _maxTrackedKeys = maxTrackedKeys;
        _timeProvider = timeProvider ?? TimeProvider.System;
    }

    public bool Allow(string key)
    {
        if (string.IsNullOrWhiteSpace(key))
            return false;

        var now = _timeProvider.GetTimestamp();
        lock (_gate)
        {
            if (++_requestsSinceSweep >= SweepInterval)
                RemoveExpired(now);

            _counters.TryGetValue(key, out var existing);
            Counter? counter = existing;
            if (counter is not null &&
                _timeProvider.GetElapsedTime(counter.WindowStart, now) >= _window)
            {
                _counters.Remove(key);
                counter = null;
            }

            if (counter is null)
            {
                if (_counters.Count >= _maxTrackedKeys)
                {
                    RemoveExpired(now);
                    if (_counters.Count >= _maxTrackedKeys)
                        return false;
                }
                counter = new Counter(now, 0);
            }

            if (counter.Count >= _permitLimit)
                return false;

            _counters[key] = counter with { Count = counter.Count + 1 };
            return true;
        }
    }

    private void RemoveExpired(long now)
    {
        foreach (var key in _counters
            .Where(pair =>
                _timeProvider.GetElapsedTime(pair.Value.WindowStart, now) >= _window)
            .Select(pair => pair.Key)
            .ToArray())
        {
            _counters.Remove(key);
        }
        _requestsSinceSweep = 0;
    }

    private sealed record Counter(long WindowStart, int Count);
}

Counter lookup and updates are O(1) average time. A periodic sweep is O(k) for k tracked keys, so occasional calls pay cleanup cost. Space is O(min(a, m)), where a is the number of active keys in the current window and m is maxTrackedKeys. Reaching the bound rejects unseen keys rather than allowing memory to grow without limit.

• Blank key.
• First request for a key.
• Request exactly at the window boundary.
• Multiple independent keys.
• Many unique keys causing memory growth.

• Inject a fake TimeProvider and advance exactly to the boundary.
• Use two keys interleaved to verify independent counters.
• Advance past expiry and verify stale keys no longer consume capacity.
• Fill maxTrackedKeys with active keys and verify a new key is rejected.
• Invoke Allow concurrently and verify the permit limit is not exceeded.

• Using local variables only and losing counters between calls.
• No thread-safety discussion.
• Not having any cleanup story for many old keys.
• Claiming this in-memory version works across multiple servers.