Combining frequency map + selection, and the bucket-sort optimization.
Count frequencies in a map. Then either a size-k heap (O(n log k)), or bucket sort by frequency (index = count) for O(n): frequencies can't exceed n, so bucket into an array of lists and read from the high-frequency end. Bucket sort is the slick optimal answer. The key realization is that the count itself is a bounded integer in [1, n], which is exactly the precondition for counting/bucket sort to beat comparison sorts. If the interviewer adds 'return them in sorted order within a frequency tier', you layer a sort inside each bucket — but the O(n) bucket pass is what they're fishing for.
'K most/least frequent' → frequency map, then heap or frequency-bucket sort.
Time O(n) with buckets · Space O(n)