Counter: Implement a Thread-Safe Multi-Key Counter with Atomic Increment and Reset

Question

## Problem

Implement a `Counter` class that maps string keys to integer counts. It must support: `increment(key, amount=1)`, `decrement(key, amount=1)`, `reset(key)`, `get(key)`, and `top_k(k)` (returns k keys with highest counts). All operations must be thread-safe.

```python
from collections import defaultdict
import threading

class Counter:
    def __init__(self): ...
    def increment(self, key: str, amount: int = 1) -> None: ...
    def decrement(self, key: str, amount: int = 1) -> None: ...
    def reset(self, key: str) -> None: ...
    def get(self, key: str) -> int: ...
    def top_k(self, k: int) -> list[tuple[str, int]]: ...
```

**Example:**
```
c = Counter()
c.increment("api_calls", 5)
c.increment("errors")
c.increment("api_calls", 3)
c.get("api_calls")  -> 8
c.top_k(1)          -> [("api_calls", 8)]
c.reset("api_calls")
c.get("api_calls")  -> 0
```

## Follow-ups

1. Why is a plain `dict` not thread-safe in CPython even with the GIL, and when does that assumption break?
2. How would you implement `top_k` in O(n log k) time using a min-heap of size k?
3. How would you make this counter distributed across multiple processes using Redis atomic commands?
4. If you need to track counts per time window (e.g., last 60 seconds), what data structure replaces the plain counter?

Counter: Implement a Thread-Safe Multi-Key Counter with Atomic Increment and Reset

Question Details

Full Details

Topics

More from Uber