[Amazon Question] Top K frequent Words

Problem: Given an array of strings. Return the top k frequent strings in the input array in descending order. If frequency matches then the word with lower alphabetical order should come first.

Example:

Input: ["i", "love", "cricket", "i", "love", "tennis"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 1
Output: ["i"]

Approach: Its similar to the problem of getting top k frequent integers. We will use quick select here too but in the end we need to sort the output of quick select to make sure in case of frequency matches, word with lower alphabetical comes first.

Implementation in C#:

    public IList<string> TopKFrequent(string[] words, int k) 

    {

        Dictionary<string, int> frequencyMap = new Dictionary<string, int>();

        foreach (string word in words)

        {

            if (!frequencyMap.ContainsKey(word))

            {

                frequencyMap[word] = 0;

            }

            ++frequencyMap[word];

        }

        string[] uniqueWords = frequencyMap.Keys.ToArray();

        string[] kFrequentWords = this.TopKFrequentQuickSelect(uniqueWords, uniqueWords.Length - k + 1, 0, uniqueWords.Length - 1, frequencyMap, k);

        Array.Sort(kFrequentWords, (w1, w2) => {

            int firstCompare = frequencyMap[w2].CompareTo(frequencyMap[w1]);

            if (firstCompare != 0)

            {

                return firstCompare;

            }

            return w1.CompareTo(w2);

        });

        return new List<string>(kFrequentWords);

    }

    

    private string[] TopKFrequentQuickSelect(string[] uniqueWords, int k, int start, int end, Dictionary<string, int> frequencyMap, int length)

    {

        if (k > 0 && k <= end - start + 1)

        {

            int pos = this.RandomPartition(uniqueWords, start, end, frequencyMap);

            if (pos - start + 1 == k)

            {

                return this.Subarray(uniqueWords, pos, length);

            }

            else if (pos - start + 1 > k)

            {

                return this.TopKFrequentQuickSelect(uniqueWords, k, start, pos - 1, frequencyMap, length);

            }

            return this.TopKFrequentQuickSelect(uniqueWords, k - (pos - start + 1), pos + 1, end, frequencyMap, length);

        }

        return new string[] {};

    }

    

    private int RandomPartition(string[] uniqueWords, int start, int end, Dictionary<string, int> frequencyMap)

    {

        int index = new Random().Next(start, end);

        this.SwapElements(uniqueWords, index, end);

        return this.Partition(uniqueWords, start, end, frequencyMap);

    }

    

    private int Partition(string[] uniqueWords, int start, int end, Dictionary<string, int> frequencyMap)

    {

        string x = uniqueWords[end];

        int i = start;

        for (int j = start; j < end; ++j)

        {

            if ((frequencyMap[uniqueWords[j]] < frequencyMap[x]) 

                || (frequencyMap[uniqueWords[j]] == frequencyMap[x] && string.Compare(uniqueWords[j], x) > 0))

            {

                this.SwapElements(uniqueWords, i, j);

                ++i;

            }

        }

        this.SwapElements(uniqueWords, i, end);

        return i;

    }

    

    private void SwapElements(string[] uniqueWords, int i, int j)

    {

        string temp = uniqueWords[i];

        uniqueWords[i] = uniqueWords[j];

        uniqueWords[j] = temp;

    }

    

    private string[] Subarray(string[] uniqueWords, int start, int length)

    {

        string[] subArray = new string[length];

        Array.Copy(uniqueWords, start, subArray, 0, length);

        return subArray;

    }

Complexity: O(n + klogk)