Top K Frequent Word Problem

Given a list of String word, get the top k frequent word

Define function List<String> topK(List<String> words, int k)

Solution:

Bucket sort:

O(n) Time Complexity

O(max(Frequent)) Space Complexity

a. Count the word using a hashmap

b. Find the most frequent word and it's frequency maxFrequency

c. create a new LinkedList array of size maxFrequency

d. traverse through the hashmap. For each of the word, get it's frequency and append the word to corresponding linkedlist in the array

e. collect the top k frequent word from the end of the array

Example:

var hash = {
  "I" : 13,
  "like" : 3,
  "meow" : 3,
  "geek" : 3,
  "burger" : 2,
  "cat" : 1,
  "foo" : 100,
  ...
  ...

  0   1      2            3                100
[[ ],[ ],[burger],[like, meow, geek],[]...[foo]]

HashMap + MinHeap

O(nlgk) Time complexity

O(n) Space complexity

a. count the word using a hashmap

b. keep a k size minHeap

c. traverse through the hashmap, add the word to the minHeap

Quick Selection

a. apply quick selection to find the unordered top k frequent words

b. Use heapsort/mergesort/quicksort to sort the top k words