Word Counter: Fix, Configure, Rank

Medium·Tagsai-coding-interview3-phasestring-processingtop-k

Problem Statement

Three phases, roughly 60 minutes total. The codebase is a word-frequency counter used by an analytics pipeline. Texts are ingested, tokenized, and counted. The API exposes per-word counts, a snapshot, and a top-K query. Phase 1 (Fix the tokenizer, roughly 15 minutes). `WordCounter.ingest(text)` is supposed to split on whitespace and add each token to the counts. A failing test shows that `ingest("hello world")` followed by `countOf("hello")` returns 0 instead of 1. The bug is in the tokenizer: it splits on the wrong character. Find it and fix it. Phase 2 (Case-insensitive mode, roughly 20 minutes). Product wants an opt-in case-insensitive mode. The starter ships a second constructor `WordCounter(boolean caseInsensitive)` and a `caseInsensitive` field. When the flag is true, `ingest` must lowercase tokens before counting, and `countOf(word)` must lowercase the query before looking up. As a result, `"Hello"` and `"hello"` map to the same bucket. The default no-argument constructor preserves case-sensitive behaviour. Phase 3 (Top-K, roughly 25 minutes). Product wants `topK(int k)` to return the k most-frequent words in descending count order, with ties broken alphabetically (ascending). The starter ships the method as a stub that throws. The edge cases the validator covers: `topK(0)` returns an empty list; `topK(k)` where `k > distinct word count` returns all words; `topK` on an empty counter returns an empty list; `topK(-1)` throws `IllegalArgumentException`. The validator runs three scenarios. 1. phase1_tokenizer_correct: `ingest("hello world")` then `countOf("hello")` returns 1 (currently 0). Multiple ingests accumulate. 2. phase2_case_insensitive_mode: the case-insensitive constructor lowercases tokens AND lookups. The default constructor preserves case. 3. phase3_top_k: descending count order, alphabetical tie-break, plus the four edge cases (0, oversize, empty, negative).

Examples

Example 1

Input

var c = new WordCounter(); c.ingest("hello world hello"); c.countOf("hello")

Output

"2"

Why

Two occurrences of 'hello'. Phase 1 fix: split on whitespace, not on the broken delimiter.

Example 2

Input

var c = new WordCounter(true); c.ingest("Hello hello HELLO"); c.countOf("hello")

Output

"3"

Why

Phase 2: caseInsensitive=true lowercases tokens on ingest AND lowercases the lookup.

Example 3

Input

c.ingest("a b c b c c"); c.topK(2)

Output

"[\"c\", \"b\"]"

Why

Phase 3: 'c' appears 3 times, 'b' appears 2 times. The top 2 is [c, b] in descending count order. Ties such as b and a both at count 1 would be broken alphabetically.

Constraints

•Tokens are split on whitespace. Empty strings are not counted.
•Phase 2: caseInsensitive=true lowercases on both ingest AND lookup. The default constructor (no argument) is case-sensitive.
•Phase 3: topK returns the k most-frequent words in descending count order, with ties broken by alphabetical order ascending.
•topK(0) returns []; topK(k > distinct words) returns all words; topK on an empty counter returns []; topK(-1) throws IllegalArgumentException.
•snapshot() returns a defensive copy. Caller mutations must not affect internal state.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

Phase 1: text.split("\\s+") splits on one or more whitespace characters and avoids empty tokens between consecutive spaces. The bug is splitting on "," instead of whitespace.

Hint 2

Phase 2: in ingest, when caseInsensitive is true, do `token = token.toLowerCase()` before merging into the map. In countOf, do the same to `word` before getOrDefault. The two must agree. Lowercasing only on ingest leaves uppercase queries returning 0.

Hint 3

Phase 3: build entries from the count map, then sort with a Comparator. The primary key is count descending, and the secondary key is the entry key ascending. `entries.sort((a, b) -> { int c = b.getValue() - a.getValue(); return c != 0 ? c : a.getKey().compareTo(b.getKey()); })`. Then take the first `min(k, size)` keys.

Hint 4

Phase 3: validate k < 0 first (throw). Then handle k == 0. Then sort and take the prefix. The 'all words' case (k > distinct) falls out naturally from min(k, size).

Hint 5

Avoid reaching for a heap. The data set is small, so sorting once is simpler and correct. A heap is the right answer for streaming top-K, not for batch top-K on an in-memory counter.