LSD Radix sort can be used: - First, it will sort the no. This will take O(k.n) (k: max no of digits in a number; n: no of integers) - Second, since the no are now sorted, scan all the integers and get their frequency count. O(n) - Use radix sort again to sort the frequency count in decreasing order. O(k'.n) (k' < k)
Overall, O(k.n). Whether it can be better depends on following: 1. Are all of the numbers single digit, if yes, then k=1 and thus first step will take O(n). Overall it will be O(k'.n). Value of k' will depend on how huge is the original list of numbers 2. Even if the numbers are not single digit and if k < logn, then O(k.n) < (n.logn) So, basically giving presenting both the solutions in the interview can be good along with the analysis that which algo can perform better in which scenario. On Sun, Dec 25, 2011 at 12:17 PM, atul anand <atul.87fri...@gmail.com>wrote: > @ankur : if i am able to figure out a better solution , i will post.but i > guess nlogn is the best we can get. > > > On Sun, Dec 25, 2011 at 4:50 PM, Ankur Garg <ankurga...@gmail.com> wrote: > >> @Atul..your solution is correct and would do the job but its complexity >> wud be nlogn . >> >> Any better way of solving it ? >> >> Regards >> Ankur >> >> >> On Sun, Dec 25, 2011 at 2:10 AM, sravanreddy001 <sravanreddy...@gmail.com >> > wrote: >> >>> any better approach than O(N log N) time? >>> >>> maintain a heap of nodes <value, count> >>> for each element, if already present increase the count. Else add the >>> elements. >>> >>> Max-Heap --> fetch the node, print it count number of times, (time to >>> search in heap -- log N) >>> doing this for N elements. >>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/rJMBHTFmv8IJ. >>> >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Piyush Kansal -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
