Return Kth most occurring word


  • 1
    B
    1. Given a String [] words, return the Kth most occurring word
      to solve this
      1.1) Using HashMap
      a). we can use a HashMap, to keep track of occurrence
      b). sort it in descending order
      c). remove K-1 and return Kth element

    Now, runtime of this is
    For put and get Docs say constant time(don’t know what it), say O(1).
    Sorting (nLogn)
    remove K. So it will be O(1)+ nLogn+k = nLogn

    1.2) Using TreeMap
    We can use TreeMap, passing the comparator for desc order.
    based on the doc put, get, remove will Logn for N times it will be nLogn

    So for this problem, based on runtime we can use any one of them right, as both of them have same runtime ?. Please correct me if I am wrong.

    For HashMap, Java Doc says constant time, it uses hash address to put and get data, for this we can say it spends O(1) unit of time, to perform this operation on N items it will be O(N) it is not constant right ?


  • 0
    B

    Hi,

    Could some one shed some light on this.


  • 0
    G
                Console.WriteLine("Enter k:\n");
                int k = Convert.ToInt32(Console.ReadLine());
                Dictionary<string,int> d = new Dictionary< string,int>();
                for (int i = 0; i < s.Length; i++)
                {
                    if (d.ContainsKey(s[i]))
                    {
                        d[s[i]] = d[s[i]] + 1;
                    }
                    else
                        d.Add( s[i],1);
                   
                }
                foreach (KeyValuePair<string, int> pair in d)
                {
                    if(pair.Value==k)
                    Console.WriteLine("{0}, {1}", pair.Key, pair.Value);
                }
                Console.ReadLine();

  • 0
    E

    @githika.cs-gmail.com Elegant solution, I think this way we get the string that occurred k times not kth most occured.
    Tha last foreach loop should probably be something like this.

    var list=d.Keys.ToList();
    list.Sort();
    int value=1;
    int returnValue=-1;
    foreach(var v in list)
    {
    if(value==k)
    {
    return returnValue=d[v];
    }
    }
    return returnValue;

  • 0
    G

    You are right @enigma. Thanks for the clarification.


  • 0
    T

    @brainyak said in Return Kth most occurring word:

    You are right. Both of them will have the same time complexity. However, note that TreeMap would sort based on the key and not on the value.

    One possible solution:
    Insert N elements to the HashMap with the value as the frequency
    Iterate over the HashMap and store each entry in a TreeMap<String, List<String>> initialised with a decreasing order comparator. The frequency would be the key and the value would be a list of words.
    Iterate over the TreeMap to get the kth value. The list would contain the kth most occurring words.


  • 0
    R

    @tourniquet What will be the running time for this approach? Will this be efficient if done on a big scale?


  • 0
    M

    @brainyak TreeMap is similar to HashMap except TreeMap has data stored in ascending order of the key. I would do the following:

    • Create a TreeMap where the key is the frequency of the word and value is the word.
    • Retrieve the TreeMap[TreeMap.size - k] element. That will be the kth frequent word.

    Since TreeMaps stored keys in asc order,
    TreeMap[TreeMap.size - 1] would be the 1st frequent word,
    TreeMap[TreeMap.size - 2] would be the 2nd most frequent word and so on.
    ...
    ...
    TreeMap[TreeMap.size - k] would be the kth most frequent word.

    [Note: Since the key cannot be duplicate, it will ignore subsequent words with the same frequencies. So, it will only report one word per frequency. It seems the question is not looking for all the words anyways.]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.