Top k most active symbols

Question

Given the full tape of traded symbols, return the k symbols that printed most often. Break ties alphabetically. You want to avoid a full sort of all distinct symbols when k is small.

tape = ["A", "A", "B", "C", "B", "A"], k = 2
-> ["A", "B"]      # A prints 3 times, B twice

Return the k highest-frequency symbols, ties broken alphabetically. Aim for $O(n + u \log u)$ or better.

Accepted Answer

Count each symbol, then place symbols into buckets indexed by their frequency, bucket f holds every symbol seen exactly f times. Since no symbol can appear more than n times, there are at most n + 1 buckets. Walk buckets from highest frequency down, emitting symbols (alphabetically within a bucket) until you have k. Tracing the example: counts are A: 3, B: 2, C: 1. Bucket 3 holds A, bucket 2 holds B. Walking down we emit A then B, stopping at k = 2. Time O(n + u \log u) in the worst case from the per-bucket sort (O(n) if ties are broken arbitrarily), space O(n). Edge cases: k larger than the …

Top k most active symbols

Your answer

More Coding questions