Amazon Interview Question

Given a string, find the kth most frequent words in that string.

Interview Answer

Anonymous

Feb 11, 2019

After converting strings into words, hash into histogram. Sorting histogram by value would be slow. This is the brute force approach. Instead put the first 7 keys value into a min heap by value. Iterate through the rest of the dictionary key value pair. If a value is > the root of the heap, use it to replace root. You can perform both of the above processes in one loop, so time is O(n).