Design and implement a **per-key call counter**: a component that tracks how many times each distinct key has been seen. The API is a single method, for example: ``` long incrementAndGet(String key) ``` Each call increments the count associated with `key` and returns the **new count for that key** — i.e. how many times that key has been passed to the method so far, including this call. Work through the design in increasing order of difficulty across the three Parts below. ### Constraints & Assumptions - Single host throughout. Part 3 is **cross-process on one machine**, not a distributed/multi-host system (no global clock or network partitions to reason about). - Keys are strings; the key space may be large and is not known up front. Treat it as potentially unbounded unless you state otherwise. - Each `incrementAndGet` must return the **exact** count after this call, not an approximate or eventually-consistent total. - Counts fit in a 64-bit signed integer; overflow is out of scope. - Unless you argue otherwise, in-memory state is acceptable for Parts 1–2; durability across restarts is a concern you may raise in Part 3. ### Clarifying Questions to Ask - What is the expected call rate and the read/write ratio — is this low-throughput, or a hot path with heavy contention? - How large is the key space, and do keys need to be evicted/expired, or do counts live forever? - Must counts survive a process restart or host reboot (durability), or is in-memory state acceptable? - Is introducing an external dependency (a database, a cache server) allowed in Part 3, or must the solution be self-contained? - Does the returned count have to be exact and strictly monotonic per key, or is an approximate/eventually-consistent total acceptable for some callers? ### Part 1 — Basic in-process counter Implement the counter for a **single-threaded, in-process** caller. Define the backing data structure and the `incrementAndGet` logic, and state explicitly why this version is not safe once multiple threads call it concurrently. ```hint Data structure A map from key → count is the natural backing store. The interesting part is what breaks when the read-modify-write (read the current value, add one, write it back) is interleaved across threads. ``` #### What This Part Should Cover - A correct single-threaded baseline: a map from key to a 64-bit count, with an unseen key defaulting to 0. - A precise account of *why* it breaks under concurrency — the read-modify-write is three separate steps, not one atomic action, so increments can be lost. - Recognition that the underlying non-thread-safe map can itself be corrupted (not just produce wrong counts), independent of the counting logic. ### Part 2 — Make it thread-safe, and compare approaches Make `incrementAndGet` correct under concurrent calls from many threads, on both the same key and different keys. Then **compare at least two or three distinct approaches** and articulate the trade-offs (correctness, contention/throughput, memory, complexity). State which you would choose by default and why. ```hint Where to start The whole read-modify-write must be atomic. A single coarse lock (a `synchronized` method or one `ReentrantLock`) is the simplest correct version — use it as your baseline, then argue about its cost. ``` ```hint Reduce contention A coarse lock serializes *unrelated* keys against each other. Can you make the unit of atomicity per-key instead of global, so updates to different keys never block one another? Think about what each key's value would have to be for its own increment to be atomic without a shared lock. ``` ```hint The subtle bug "Check if a key is absent, then insert a new counter" is two operations and races — two threads can each create a separate counter for the same key. How could the find-or-create step be collapsed into one atomic action? And once you settle on a per-key accumulator, check whether it can return the *exact* post-increment value or only an eventually-consistent total. ``` #### What This Part Should Cover - Two or three genuinely different thread-safe strategies — not restatements of one — compared along correctness, contention/throughput, memory, and complexity. - Recognition that a single coarse lock serializes *all* keys, and a strategy that restores per-key independence. - The non-atomic "create on first sight" race, and how to collapse find-or-create into a single atomic step. - Awareness that some high-throughput accumulators trade exactness for speed, and a judgment on whether that trade-off is acceptable given the stated exact-count requirement. - A default recommendation, justified specifically against the exact-count contract. ### Part 3 — Share the counter across multiple processes on one host Now several **independent applications/processes on the same host** must all observe and update the same counter values. The in-process techniques from Part 2 no longer suffice. Propose how to make this work, compare a few options, and recommend one for a given set of requirements. ```hint Why Part 2 fails Separate processes don't share a heap, so a lock, an atomic integer, or a concurrent map in one process is invisible to the others. The shared state has to live *outside* any single process — name the candidates for "outside." ``` ```hint Options to weigh Don't jump to one mechanism — sketch the spectrum from "one process owns the counter and everyone asks it," to "a shared store enforces the atomic update for you," to "processes share memory directly and coordinate with their own lock." Weigh each on durability, throughput, operational complexity, and crash-safety, and let the requirements pick the winner. ``` #### What This Part Should Cover - A clear jump from "in-process synchronization" to "shared state outside any single process," with an explanation of *why* the Part 2 primitives are invisible across address spaces. - Multiple viable mechanisms across the spectrum (single-owner service, shared store with atomic increment, embedded DB, file lock, shared memory) with their respective failure modes. - A recommendation conditioned on requirements (throughput, durability, allowed dependencies) rather than one absolute answer. - Operational concerns: single points of failure, durability across restarts, and crash recovery. ### What a Strong Answer Covers These dimensions span all three Parts and should hold regardless of which Part is being discussed: - Each escalation preserves the **exact post-increment return value** contract — no Part quietly degrades to an approximate or eventually-consistent total. - Atomicity is reasoned about explicitly at every level: read-modify-write within a thread, find-or-create across threads, and the update across processes. - Trade-offs are weighed along a consistent axis set (correctness, contention/throughput, memory, complexity, durability) rather than asserting one universal "best." - Awareness of unbounded key growth and the need for an eviction/TTL story at any tier. ### Follow-up Questions - How would you bound memory if the key space is effectively unbounded — what eviction or TTL policy, and how does eviction interact with the "exact count" guarantee? - If this had to scale **across multiple hosts** (not just processes on one host), what changes, and how do you keep increments atomic and counts consistent then? - Your Part 3 local service is a single point of failure. How would you make it durable and restart-safe without losing or double-counting increments? - Under extreme contention on a few hot keys, how would you sustain throughput while still returning an exact per-call count?