Specify the operation contract
Before implementing an LRU cache, define key/value behavior, capacity zero, replacement, concurrency and whether expired entries count toward capacity. A map and recency list are one design because their strengths complement each other. Explain the consistency invariant and the sequence of changes on hit, insert and eviction. Tests should check structure consistency, not only a few successful returned values.
Scheduling requires a claim boundary
A delayed-task scheduler needs identity, due time, lifecycle state and execution ownership. A min-heap finds the next due task, but removing an arbitrary task may require a linear search unless the heap is indexed. Cancellation must define whether it prevents a task already claimed by a worker. Tombstones simplify cancellation but require a cleanup bound. Persisted scheduling introduces recovery and duplicate-execution questions beyond an in-memory class.
Rate limiting is an atomic decision
A token bucket tracks capacity, refill rate, tokens and last refill time. Refill from elapsed monotonic time, cap at capacity and atomically consume on admission. For multiple application instances, per-process buckets do not enforce a global user quota. An atomic shared store or a deliberate partitioned policy is needed. Bound retained user buckets and avoid holding a local lock during slow external work.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
// Single-process sketch: synchronization covers refill AND consume.
synchronized boolean allow(long nowNanos) {
double elapsed = (nowNanos - lastNanos) / 1_000_000_000.0;
tokens = Math.min(capacity, tokens + elapsed * tokensPerSecond);
lastNanos = nowNanos;
if (tokens < 1) return false;
tokens -= 1;
return true;
}Walkthrough
Assume validated positive capacity/rate, initialized fields and monotonic calls for one bucket. The synchronized boundary prevents two callers from spending the same token. This code does not implement global fleet limits, inactive-user cleanup or fair waiting. Inject a monotonic clock for deterministic tests instead of sleeping in tests.
Practice it yourself
Design tests for capacity two and refill one token per second using a fake clock.
Check your reasoning
At initial time, admit two and reject a third. Advance half a second and still reject if no full token is available; advance another half and admit one. Verify capacity caps after a long idle period and that concurrent calls cannot admit more than available tokens.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.