Re: [algogeeks] Re: Frequency Sort Algo
@Gene :
sorting given input will give:-
1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
consider 2-d array;
4 3 5 2 1 - frequency of corresponding unique data at position arr[1][]
1 2 3 4 5 - unique data
min-heapify arr[0][] - first row and keep track of
the corresponding frequency.
now extract-min and expand it accordingly
for example extract 5 , corresponding frequency found is 1 ,so insert 5 in
array.
or
we can represent each node:-
struct node{
int unique_data;
int frequency;
};
so no need of scanning all values for each extract_min operation.
thats what i was trying to say before.
On Mon, Dec 26, 2011 at 7:49 PM, Gene wrote:
> Any reasonable algorithm is goingto compute a histogram of the data
> then sort into frequency order to produce the output.
>
> The histogram (map from data values to frequency counts) can be stored
> in a simple array if the data are small integers as in the example.
> If the data are not nice, then a hash table is a good choice.
>
> Run time will be O(n + N log N) where n is the number of input data
> and N is the number of unique data values. If you have many data but
> only a few ( O(1 / log n) ) unique values, the run time is linear. If
> you have O(n) unique values, it's n log n. I think this bound is
> tight.
>
> Note: It does not make much sense to use heaps in this problem (unless
> you're sorting with heapsort) as some have proposed because you can't
> use the min or max frequency values until you've scanned all the
> input.
>
>
> On Dec 24, 12:27 pm, Ankur Garg wrote:
> > how can one do frequency sort .
> >
> > Suppose we have an integer array like
> >
> > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3
> >
> > Then 1 is appearing 4 times
> > 2 - 3
> > 3- 5
> > 4-2
> > 5-1
> >
> > Then if we sort by frequency we shud have this as result
> >
> > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3
> >
> > How to do it
>
> --
> 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.
[algogeeks] Re: Frequency Sort Algo
@Gene: I am wondering about the the N log N factor. I agree with the log N component, but, can u clarify on the first component in N * log N (N being no. of unique numbers) we still check for each element in the input (n), the binary search among 'N' unique values. Isn't this n log N n - input size. N- unique numbers. -- 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/-/7zKgmBKQZRkJ. 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.
Re: [algogeeks] Re: Frequency Sort Algo
This problem is very old and O(NlgN) may be the best runtime . -- 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.
[algogeeks] Re: Frequency Sort Algo
Any reasonable algorithm is goingto compute a histogram of the data then sort into frequency order to produce the output. The histogram (map from data values to frequency counts) can be stored in a simple array if the data are small integers as in the example. If the data are not nice, then a hash table is a good choice. Run time will be O(n + N log N) where n is the number of input data and N is the number of unique data values. If you have many data but only a few ( O(1 / log n) ) unique values, the run time is linear. If you have O(n) unique values, it's n log n. I think this bound is tight. Note: It does not make much sense to use heaps in this problem (unless you're sorting with heapsort) as some have proposed because you can't use the min or max frequency values until you've scanned all the input. On Dec 24, 12:27 pm, Ankur Garg wrote: > how can one do frequency sort . > > Suppose we have an integer array like > > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 > > Then 1 is appearing 4 times > 2 - 3 > 3- 5 > 4-2 > 5-1 > > Then if we sort by frequency we shud have this as result > > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 > > How to do it -- 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.
Re: [algogeeks] Re: Frequency Sort Algo
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 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 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 > > wrote: >> >>> any better approach than O(N log N) time? >>> >>> maintain a heap of nodes >>> 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.
Re: [algogeeks] Re: Frequency Sort Algo
@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 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 > wrote: > >> any better approach than O(N log N) time? >> >> maintain a heap of nodes >> 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.
Re: [algogeeks] Re: Frequency Sort Algo
fpr the nos with same frequency , the one having lower value shud come first For ex 3,1,1,3,1,3,2 Here 1 should come first so 2,1,1,1,3,3,3 On Sun, Dec 25, 2011 at 11:18 AM, top coder wrote: > What about the case of the numbers having same frequency? > Which one should come first? > > On Dec 24, 11:18 pm, atul anand wrote: > > first sort the given array , you will get > > > > 1,1,1,1,2,2,2,3,3,3,3,3,4,4,5 > > > > now count frequency of each number and insert it into min heap. > > each node contain 2 variable. > > 1) frequency > > 2) number > > > > now do extract min operation. > > > > and expand , for eg:- > > for node 5 > > frequency = 0 > > number =5; > > write 5 to the given array > > > > for node 4 > > frequency = 2 > > number =4 > > write 4,4 to array. > > > > for node 2 > > frequency = 3 > > number =2 > > > > write 2,2,2 to the given array... > > > > > > > > On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg > wrote: > > > how can one do frequency sort . > > > > > Suppose we have an integer array like > > > > > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 > > > > > Then 1 is appearing 4 times > > > 2 - 3 > > > 3- 5 > > > 4-2 > > > 5-1 > > > > > Then if we sort by frequency we shud have this as result > > > > > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 > > > > > How to do it > > > > > -- > > > 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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.
Re: [algogeeks] Re: Frequency Sort Algo
@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 wrote: > any better approach than O(N log N) time? > > maintain a heap of nodes > 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.
[algogeeks] Re: Frequency Sort Algo
What about the case of the numbers having same frequency? Which one should come first? On Dec 24, 11:18 pm, atul anand wrote: > first sort the given array , you will get > > 1,1,1,1,2,2,2,3,3,3,3,3,4,4,5 > > now count frequency of each number and insert it into min heap. > each node contain 2 variable. > 1) frequency > 2) number > > now do extract min operation. > > and expand , for eg:- > for node 5 > frequency = 0 > number =5; > write 5 to the given array > > for node 4 > frequency = 2 > number =4 > write 4,4 to array. > > for node 2 > frequency = 3 > number =2 > > write 2,2,2 to the given array... > > > > On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg wrote: > > how can one do frequency sort . > > > Suppose we have an integer array like > > > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 > > > Then 1 is appearing 4 times > > 2 - 3 > > 3- 5 > > 4-2 > > 5-1 > > > Then if we sort by frequency we shud have this as result > > > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 > > > How to do it > > > -- > > 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.- Hide quoted text - > > - Show quoted text - -- 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.
Re: [algogeeks] Re: Frequency Sort Algo
Hashmapping O(n) On 25-Dec-2011 2:15 AM, "sravanreddy001" wrote: > any better approach than O(N log N) time? > > maintain a heap of nodes > 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.
[algogeeks] Re: Frequency Sort Algo
any better approach than O(N log N) time? maintain a heap of nodes 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.
