Find top/bottom-k words in list or stream

You are given words (strings) either as a finite list or as an unbounded stream. 1) **List version**: Given an array `words` and an integer `k`, return: - the `k` most frequent distinct words, and - the `k` least frequent distinct words. Specify how you break ties (e.g., lexicographically, or any order). 2) **Stream version (online)**: Design a data structure that supports: - `ingest(word)`: process the next word in the stream - `topK(k)`: return the `k` most frequent distinct words seen so far - `bottomK(k)`: return the `k` least frequent distinct words seen so far Discuss time/space complexity and how you would implement these operations efficiently. 3) **Variant (discuss/design)**: Extend the stream design to support returning the **first `k`** and/or **last `k`** words that are currently **non-repeating** (i.e., words with frequency exactly 1) according to stream arrival order. ### Precise Practice Contracts The original design above permits discussing tie policies. For these practice variants, use the existing deterministic policy: higher frequency first for `topK`, lower frequency first for `bottomK`, and lexicographically smaller words first when frequencies tie in either result. Return distinct words, not one entry per occurrence. Do not reverse the tie order when switching from top to bottom. **Finite list.** Implement `solution(words, k)` and return `[most_frequent, least_frequent]`. The bounds are `0 <= len(words) <= 200000` and `0 <= k <= 200000`; each word is a nonempty string. Comparison is case-sensitive. If `k` exceeds the number of distinct words, each result contains all distinct words in its own ranking order. An empty input or `k = 0` produces `[[], []]`. For `words = ["pear", "ant", "pear", "bee", "ant", "cat"]` and `k = 2`, return `[["ant", "pear"], ["bee", "cat"]]`. **Online ranking.** Support `ingest(word)`, `topK(k)` and `bottomK(k)` on the prefix received so far. A bounded operation-list form contains between 1 and 200000 operations. Each is a two-string list: `['ingest', word]`, `['topK', str(k)]` or `['bottomK', str(k)]`, with `0 <= k <= 200000`. Return one word list for each query, in query order; ingestion produces no result entry. Queries before any ingestion return `[]`. Oversized `k` returns all words seen so far, using the requested ranking. The original unbounded-stream design has no fixed prefix length; analyze its storage over a finite prefix. No lowercase or ten-character limit is imposed on the original stream design. **Current non-repeating words.** Extend the same stream behavior with `firstK(k)` and `lastK(k)`. A word qualifies only while its total count in the entire received prefix is exactly one. A second occurrence removes it from consideration; it cannot become non-repeating later in an insertion-only stream. Order qualifying words by their occurrence's arrival time, not lexically. `lastK` selects the last `k` qualifying words but returns those selected words in forward arrival order, not reversed. If fewer than `k` qualify, return all of them. A bounded operation list uses `['ingest', word]`, `['firstK', str(k)]` or `['lastK', str(k)]` with the same operation-count and `k` bounds, returning results only for queries. After ingesting `"a"`, `"b"`, `"c"`, `"b"` in that order: | Query | Result | | --- | --- | | `topK(2)` | `["b", "a"]` | | `bottomK(2)` | `["a", "c"]` | | `firstK(1)` | `["a"]` | | `lastK(2)` | `["a", "c"]` | | `lastK(1)` | `["c"]` | The written Python reference uses Python's case-sensitive string order for lexical comparisons, without case folding or locale-specific normalization. The saved practice interfaces remain unchanged. ### Bounded Top-k Method Implement `Solution.topKFrequent(words, k)` (C++: `vector<string> topKFrequent(vector<string>& words, int k)`) and return only the most frequent word list, ordered by frequency descending and then lexicographically ascending. This method has separate input guarantees: - `1 <= len(words) <= 500`. - Each word has between 1 and 10 characters, all lowercase English letters. - `1 <= k <=` the number of distinct words. For `words = ["i", "love", "study", "i", "love", "coding"]`, `k = 2`, return `["i", "love"]`. Both occur twice, and `"i"` comes first lexically. For `words = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"]`, `k = 4`, return `["the", "is", "sunny", "day"]`, with frequencies 4, 3, 2 and 1. The method does not return a bottom-k list, and its nonempty, lowercase, bounded-word guarantees do not replace the broader list and stream contracts above. ### Clarifying Questions - Does frequency alone determine the boundary of the selected `k` words? No; lexical order resolves ties at that boundary too. - Is the bottom list the reverse of the top list? Not generally; equal-frequency words still appear in lexical ascending order. - Do singleton queries mean words that were once unique? No; they must have count exactly one now. ### What a Strong Answer Covers - Implements both finite-list outputs, online frequency queries, and current-singleton queries under their respective order rules. - Handles empty prefixes, zero or oversized `k`, frequency ties, and a singleton's second occurrence. - Preserves the bounded method's exact signature and one-list result. - Explains update costs, query costs and output size separately, and accounts for growth in distinct words and exact counts over an unbounded stream. ### Follow-up Questions For the bounded top-k method, can you achieve `O(n log(k + 1))` time and `O(n)` extra space, where `n = len(words)`? This is the usual `O(n log k)` target for `k >= 2`, with a nonzero bound at `k = 1`.