Interview Question for Software Engineer at Google:

Hash all queries where key=word, value=prequency this will take O(n) amortized
Build a max heap out of the hash (according to the keys), this will also take O(n)
Do select max fron the heap k times. this will take O(Klogn)