Design a Hit Counter (with Per-Element Counts)

Problem Statement

Design a hit counter that tracks hits for different elements. Implement:

1. put(element) — Record a hit for the given element
2. getCount(element) — Return the total number of hits recorded for that element
3. getTotalCount() — Return the total number of hits across ALL elements

All operations should be efficient (aim for O(1)).

Constraints

• Elements can be any hashable key (int or string)
• At most 10^5 operations
• getCount and getTotalCount should be O(1)

Example

HitCounter hc = new HitCounter();
hc.put("a");
hc.put("b");
hc.put("a");
hc.getCount("a");     // returns 2
hc.getCount("b");     // returns 1
hc.getTotalCount();   // returns 3
hc.getCount("c");     // returns 0

What the Interviewer Expects

1. HashMap for per-element counts — element → count. O(1) put and getCount.
2. Running total variable — maintain a totalCount incremented on every put. O(1) getTotalCount (don't sum the map each time).
3. Clean, production-ready code — Uber emphasizes modular, well-structured implementations.
4. Thread safety discussion — if multiple threads call put concurrently, how do you keep counts consistent? (atomic counters, concurrent map)

Follow-ups

1. What if you need hits only within the last 5 minutes (time-windowed hit counter)?
2. What if you need the top-K most-hit elements?
3. How would you scale this across multiple servers (distributed counting)?
4. How do you handle counter overflow for very high-traffic elements?