OOD Counter Class

Design an expiring counter that tracks how many unexpired copies of each element are currently stored. Implement the Counter class:

• Counter(int window) Initializes the counter with an expiration window of window seconds.
• void put(int timestamp, string element) Adds one copy of element at timestamp.
• int getCount(int timestamp, string element) Returns the number of unexpired copies of element at timestamp.
• int getTotalCount(int timestamp) Returns the total number of unexpired elements across the entire counter at timestamp. An inserted element remains valid at query time timestamp only when timestamp - insertedTimestamp < window. You may assume all calls are made in non-decreasing timestamp order. Follow-up note: If the system receives millions of inputs per second, storing one queue entry per event can become too expensive. A common optimization is to batch by second, keeping one time bucket per second and aggregating counts per element inside that bucket so expiration still happens lazily at bucket granularity.

Counter counter = new Counter(10); counter.put(1, "a"); counter.put(3, "a"); counter.put(5, "b"); counter.getCount(6, "a"); // return 2 counter.getTotalCount(6); // return 3 counter.getCount(12, "a"); // return 1 counter.getTotalCount(12); // return 2

Two values inserted at the same timestamp are both valid until the window boundary is reached. At timestamp 3 with window 2, both entries from timestamp 1 have expired.

Reported for an Uber software engineer phone screen as an expiring counter class with lazy deletion. A common follow-up asks how to handle roughly one million inputs per second by batching counts into per-second aggregates.