Loading page…
Practice problem · medium
A search engine keeps a cache of recent queries. Each entry holds a query id, and the same query can sit in the cache many times.
You must evict exactly k entries to free memory. Afterward the cache should hold as few distinct queries as possible, because each distinct query costs an index slot. You may choose which entries to evict.
Write fewest_distinct(values, k).
values[i] is the query id of the i-th cache entry.k entries, and you choose which ones.Input: values = [4, 3, 1, 1, 3, 3, 2], k = 3
Output: 2The trace counts each query, sorts the counts, and then spends k on the smallest counts first.
| Step | State | Remaining k | Distinct left |
|---|---|---|---|
| 1 | Counts: 4: 1, 3: 3, 1: 2, 2: 1 | 3 | 4 |
| 2 | Sorted counts: 1, 1, 2, 3 | 3 | 4 |
| 3 | Remove query 4 (count 1) | 2 | 3 |
| 4 | Remove query 2 (count 1) | 1 | 2 |
| 5 | Next count is 2, more than 1: stop | 1 | 2 |
Evicting all entries of the two rarest queries leaves 2 distinct queries. The remaining 1 eviction comes from any other entry and does not change the count. The output is 2.
Input: values = [5, 5, 4], k = 1
Output: 1With k = 1, evict one of the two entries of query 5 or the entry of query 4. Only the entry of query 4 removes a whole query, so 1 distinct query is left.
Input: values = [2, 1, 1, 3, 3, 3], k = 1
Output: 2With k = 1, the query 2 has exactly one entry. Removing it leaves queries 1 and 3, so the answer is 2.
1 ≤ values.length ≤ 100,000 (cache entries)1 ≤ values[i] ≤ 10^9 (query ids)0 ≤ k ≤ values.lengthTrying every way to choose k entries is far too many. Counting how often each query appears takes n steps, and sorting the d distinct counts takes d log d, about 1.7 million at most. The greedy choice, removing the smallest groups first, is correct and needs only the counts.
fewest_distinct · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.