Practice question · Select all that apply
For 'find the k most frequent words in a huge text', select every design decision the lesson endorses.
Hints
- The design deliberately avoids one of these, and does not need another.
- Sorting everything is what the heap is there to avoid; counting is not a DP problem.
Show the answer
- C. Select the top k with a heap of size k
- D. Count frequencies with a hash table
- E. Justify the design by analysing its complexity
Why
Hash-table counting, size-k heap selection, and complexity justification are the endorsed decisions. A full sort is what the heap avoids, and counting words is a simple pass, not a DP problem.
Practise Integrated Algorithm Design Practice
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Integrated Algorithm Design Practice
- A problem is shown to be NP-complete. Why is that useful news rather than merely bad news?
- Given a new problem, an experienced programmer often recognises it as a variant of something known - shortest…
- The fastest algorithm for a problem in the abstract is the right choice regardless of the data and…
- Order the first five steps of the design workflow the lesson recommends.
- Match each data structure to the hot operation it makes fast.