DSA interview question

C++ STL: Top K Frequent Words

Easy · Algorithms · Topics: stl, collections

The problem

Your team's search box logs every query word, and product wants a small leaderboard of the k most frequent words, with ties broken alphabetically so the list is stable between refreshes. Writing it with raw arrays would mean hand-rolling a hash table and a sort; with the C++ Standard Template Library it takes a few lines. The task is a practical tour of the containers and algorithms you'll use in almost every DSA problem: unordered_map for counting, vector<pair> for results, sort with a custom comparator, and, as a bonus, set, priority_queue, lower_bound and map.

Example: words ["apple", "banana", "apple", "cherry", "banana", "apple"], k = 2 → [("apple", 3), ("banana", 2)].

Function signature

vector<pair<string, int>> topKFrequent(const vector<string>& words, int k);
// sorted by count descending, then word ascending; at most k entries

Test cases

Input `(words, k)`	Output	Explanation
`(["apple","banana","apple","cherry","banana","apple"], 2)`	`apple=3 banana=2`	Highest counts first
`(["b","a","c","a","b","c"], 3)`	`a=2 b=2 c=2`	All tied, so alphabetical order
`(["x"], 5)`	`x=1`	k larger than the number of distinct words
`(["dog","cat","dog"], 1)`	`dog=2`	Only the top entry

(Confirm: 1 ≤ k; ties are broken alphabetically; if there are fewer than k distinct words, return them all.)

How interviewers phrase it

"Return the k most frequent words" (LeetCode 692) or "top k frequent elements" (LeetCode 347).
STL knowledge questions in C++ interviews: "map vs unordered_map?", "How do you make a min-heap with priority_queue?", "What does lower_bound return?"
Implicitly, in every problem: interviewers watch whether you reach for the right container.

Clarifying questions to ask

How should ties be ordered?
What if there are fewer than k distinct words?
How many words, and how many distinct ones? (Decides whether a full sort or a heap is better.)
Are words case-sensitive?

Follow-ups to expect

"map vs unordered_map?"
"Can you do better than sorting all distinct words?"
"How do you make a min-heap?"
"What does lower_bound do?"
"set vs multiset?"
"What's iterator invalidation?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview