Re: [algogeeks] Re: Extract Top K elements from a List of N elements based on frequency
Can't we do this using map library function..mapping the integer with their frequency count?? On Sun, May 15, 2011 at 10:15 PM, Dave dave_and_da...@juno.com wrote: @Akshata: Yes. In my response of May 7, I proposed an algorithm using hashing. On May 9, Apoorve asked if there was an in-place O(n) solution. I take it that in-place means with only O(1) extra space. That is the question to which I was responding. Your suggestion of using a hashmap is non-responsive since it uses more than O(1) extra space. Dave On May 15, 9:49 am, Akshata Sharma akshatasharm...@gmail.com wrote: hash all the elements. Keys are stored in hashmap in sorted order based on values. just iterate thru the hashmap extracting the first k keys. m I missing something? On Thu, May 12, 2011 at 2:50 AM, Dave dave_and_da...@juno.com wrote: @Apoorve: I don't believe that you can determine the frequency counts in-place in O(n). Dave On May 9, 8:42 am, Apoorve Mohan apoorvemo...@gmail.com wrote: @Dave: Can there be an in-place O(n) solution to this??? On Mon, May 9, 2011 at 7:01 PM, Dave dave_and_da...@juno.com wrote: @Ashish: By compress, I meant to transfer the active entries in the hash table into contiguous elements of an array. Since the hash table itself is probably stored in an array, it just means to go through the hash table array and move the active entries to the front of the array. Dave On May 9, 1:14 am, Ashish Goel ashg...@gmail.com wrote: Dave, w.r.t statement, After all integers are processed, compress out the unused hash table entries and find the Kth largest element, I could not understand the compress concept...are you saying something on counting sort philosophy? say the list is 5 4 4 3 3 3 2 2 2 2 1 1 1 1 1 so the hash map will have 5,1 5 is 1 time 4,2,4 is two time 3,3,... 2,4,... 1,5... so if the question is to find say 3rd largest element based on frequency, it would be 4 This essentially means that we probably need dynamic order statistics where the node contains the starting rank for a particular entry in the RBTree. Each RBTree node contains the number, its frequency and rank. then this becomes O(n) +O(lgn) i.e. O(n) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, May 7, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Gaurav: As I understand your solution, you are finding the K largest integers based on value, rather than the K with the highest frequency of occurrence. @Amit: Hash the integers into a hash table that includes a field for the frequency count. When a new entry is made, set the frequency count to 1. When an integer already is in the table, increment its count. After all integers are processed, compress out the unused hash table entries and find the Kth largest element. The overall algorithm can be done in O(n). Dave On May 7, 12:06 pm, Gaurav Aggarwal 0007gau...@gmail.com wrote: It can be done without sorting. Take the first element as pivot element. Calculate its position using Partition algorithm. If its new index is K, then on left side are top K integers. If indexK, apply algo on left side Else apply algo on right side. Best Case: O(1) Worst Case: O(n^2) But there are very less chances of worst case. It is when the list is already sorted. On Thu, May 5, 2011 at 1:06 AM, amit amitjaspal...@gmail.com wrote: Hi , We are give a list of integers now our task is to find the top K integers in the list based on frequency. Apart from sorting the data can there be any other algorithm? -- 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. -- Gaurav Aggarwal SCJP- 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
Re: [algogeeks] Re: Extract Top K elements from a List of N elements based on frequency
hash all the elements. Keys are stored in hashmap in sorted order based on values. just iterate thru the hashmap extracting the first k keys. m I missing something? On Thu, May 12, 2011 at 2:50 AM, Dave dave_and_da...@juno.com wrote: @Apoorve: I don't believe that you can determine the frequency counts in-place in O(n). Dave On May 9, 8:42 am, Apoorve Mohan apoorvemo...@gmail.com wrote: @Dave: Can there be an in-place O(n) solution to this??? On Mon, May 9, 2011 at 7:01 PM, Dave dave_and_da...@juno.com wrote: @Ashish: By compress, I meant to transfer the active entries in the hash table into contiguous elements of an array. Since the hash table itself is probably stored in an array, it just means to go through the hash table array and move the active entries to the front of the array. Dave On May 9, 1:14 am, Ashish Goel ashg...@gmail.com wrote: Dave, w.r.t statement, After all integers are processed, compress out the unused hash table entries and find the Kth largest element, I could not understand the compress concept...are you saying something on counting sort philosophy? say the list is 5 4 4 3 3 3 2 2 2 2 1 1 1 1 1 so the hash map will have 5,1 5 is 1 time 4,2,4 is two time 3,3,... 2,4,... 1,5... so if the question is to find say 3rd largest element based on frequency, it would be 4 This essentially means that we probably need dynamic order statistics where the node contains the starting rank for a particular entry in the RBTree. Each RBTree node contains the number, its frequency and rank. then this becomes O(n) +O(lgn) i.e. O(n) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, May 7, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Gaurav: As I understand your solution, you are finding the K largest integers based on value, rather than the K with the highest frequency of occurrence. @Amit: Hash the integers into a hash table that includes a field for the frequency count. When a new entry is made, set the frequency count to 1. When an integer already is in the table, increment its count. After all integers are processed, compress out the unused hash table entries and find the Kth largest element. The overall algorithm can be done in O(n). Dave On May 7, 12:06 pm, Gaurav Aggarwal 0007gau...@gmail.com wrote: It can be done without sorting. Take the first element as pivot element. Calculate its position using Partition algorithm. If its new index is K, then on left side are top K integers. If indexK, apply algo on left side Else apply algo on right side. Best Case: O(1) Worst Case: O(n^2) But there are very less chances of worst case. It is when the list is already sorted. On Thu, May 5, 2011 at 1:06 AM, amit amitjaspal...@gmail.com wrote: Hi , We are give a list of integers now our task is to find the top K integers in the list based on frequency. Apart from sorting the data can there be any other algorithm? -- 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. -- Gaurav Aggarwal SCJP- 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.-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. -- regards Apoorve Mohan- 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
Re: [algogeeks] Re: Extract Top K elements from a List of N elements based on frequency
@Dave: Can there be an in-place O(n) solution to this??? On Mon, May 9, 2011 at 7:01 PM, Dave dave_and_da...@juno.com wrote: @Ashish: By compress, I meant to transfer the active entries in the hash table into contiguous elements of an array. Since the hash table itself is probably stored in an array, it just means to go through the hash table array and move the active entries to the front of the array. Dave On May 9, 1:14 am, Ashish Goel ashg...@gmail.com wrote: Dave, w.r.t statement, After all integers are processed, compress out the unused hash table entries and find the Kth largest element, I could not understand the compress concept...are you saying something on counting sort philosophy? say the list is 5 4 4 3 3 3 2 2 2 2 1 1 1 1 1 so the hash map will have 5,1 5 is 1 time 4,2,4 is two time 3,3,... 2,4,... 1,5... so if the question is to find say 3rd largest element based on frequency, it would be 4 This essentially means that we probably need dynamic order statistics where the node contains the starting rank for a particular entry in the RBTree. Each RBTree node contains the number, its frequency and rank. then this becomes O(n) +O(lgn) i.e. O(n) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, May 7, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Gaurav: As I understand your solution, you are finding the K largest integers based on value, rather than the K with the highest frequency of occurrence. @Amit: Hash the integers into a hash table that includes a field for the frequency count. When a new entry is made, set the frequency count to 1. When an integer already is in the table, increment its count. After all integers are processed, compress out the unused hash table entries and find the Kth largest element. The overall algorithm can be done in O(n). Dave On May 7, 12:06 pm, Gaurav Aggarwal 0007gau...@gmail.com wrote: It can be done without sorting. Take the first element as pivot element. Calculate its position using Partition algorithm. If its new index is K, then on left side are top K integers. If indexK, apply algo on left side Else apply algo on right side. Best Case: O(1) Worst Case: O(n^2) But there are very less chances of worst case. It is when the list is already sorted. On Thu, May 5, 2011 at 1:06 AM, amit amitjaspal...@gmail.com wrote: Hi , We are give a list of integers now our task is to find the top K integers in the list based on frequency. Apart from sorting the data can there be any other algorithm? -- 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. -- Gaurav Aggarwal SCJP- 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.- 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. -- regards Apoorve Mohan -- 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: Extract Top K elements from a List of N elements based on frequency
On Mon, May 9, 2011 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote: Dave, w.r.t statement, After all integers are processed, compress out the unused hash table entries and find the Kth largest element, I could not understand the compress concept...are you saying something on counting sort philosophy? say the list is 5 4 4 3 3 3 2 2 2 2 1 1 1 1 1 so the hash map will have 5,1 5 is 1 time 4,2,4 is two time 3,3,... 2,4,... 1,5... so if the question is to find say 3rd largest element based on frequency, it would be 4 3rd largest element based on frequency should be 3 i think? This essentially means that we probably need dynamic order statistics where the node contains the starting rank for a particular entry in the RBTree. Each RBTree node contains the number, its frequency and rank. then this becomes O(n) +O(lgn) i.e. O(n) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, May 7, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Gaurav: As I understand your solution, you are finding the K largest integers based on value, rather than the K with the highest frequency of occurrence. @Amit: Hash the integers into a hash table that includes a field for the frequency count. When a new entry is made, set the frequency count to 1. When an integer already is in the table, increment its count. After all integers are processed, compress out the unused hash table entries and find the Kth largest element. The overall algorithm can be done in O(n). Dave On May 7, 12:06 pm, Gaurav Aggarwal 0007gau...@gmail.com wrote: It can be done without sorting. Take the first element as pivot element. Calculate its position using Partition algorithm. If its new index is K, then on left side are top K integers. If indexK, apply algo on left side Else apply algo on right side. Best Case: O(1) Worst Case: O(n^2) But there are very less chances of worst case. It is when the list is already sorted. On Thu, May 5, 2011 at 1:06 AM, amit amitjaspal...@gmail.com wrote: Hi , We are give a list of integers now our task is to find the top K integers in the list based on frequency. Apart from sorting the data can there be any other algorithm? -- 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. -- Gaurav Aggarwal SCJP- 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. -- Aamir Khan Indian Institute of Technology Roorkee, Roorkee, Uttarakhand, India , 247667 Phone: +91 9557647357 email: aami...@iitr.ernet.in aamir...@iitr.ernet.in ak4u2...@gmail.com -- 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: Extract Top K elements from a List of N elements based on frequency
Dave, w.r.t statement, After all integers are processed, compress out the unused hash table entries and find the Kth largest element, I could not understand the compress concept...are you saying something on counting sort philosophy? say the list is 5 4 4 3 3 3 2 2 2 2 1 1 1 1 1 so the hash map will have 5,1 5 is 1 time 4,2,4 is two time 3,3,... 2,4,... 1,5... so if the question is to find say 3rd largest element based on frequency, it would be 4 This essentially means that we probably need dynamic order statistics where the node contains the starting rank for a particular entry in the RBTree. Each RBTree node contains the number, its frequency and rank. then this becomes O(n) +O(lgn) i.e. O(n) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, May 7, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Gaurav: As I understand your solution, you are finding the K largest integers based on value, rather than the K with the highest frequency of occurrence. @Amit: Hash the integers into a hash table that includes a field for the frequency count. When a new entry is made, set the frequency count to 1. When an integer already is in the table, increment its count. After all integers are processed, compress out the unused hash table entries and find the Kth largest element. The overall algorithm can be done in O(n). Dave On May 7, 12:06 pm, Gaurav Aggarwal 0007gau...@gmail.com wrote: It can be done without sorting. Take the first element as pivot element. Calculate its position using Partition algorithm. If its new index is K, then on left side are top K integers. If indexK, apply algo on left side Else apply algo on right side. Best Case: O(1) Worst Case: O(n^2) But there are very less chances of worst case. It is when the list is already sorted. On Thu, May 5, 2011 at 1:06 AM, amit amitjaspal...@gmail.com wrote: Hi , We are give a list of integers now our task is to find the top K integers in the list based on frequency. Apart from sorting the data can there be any other algorithm? -- 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. -- Gaurav Aggarwal SCJP- 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: Extract Top K elements from a List of N elements based on frequency
ok, i got it.. ya i misunderstood it.. On Sat, May 7, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Gaurav: As I understand your solution, you are finding the K largest integers based on value, rather than the K with the highest frequency of occurrence. @Amit: Hash the integers into a hash table that includes a field for the frequency count. When a new entry is made, set the frequency count to 1. When an integer already is in the table, increment its count. After all integers are processed, compress out the unused hash table entries and find the Kth largest element. The overall algorithm can be done in O(n). Dave On May 7, 12:06 pm, Gaurav Aggarwal 0007gau...@gmail.com wrote: It can be done without sorting. Take the first element as pivot element. Calculate its position using Partition algorithm. If its new index is K, then on left side are top K integers. If indexK, apply algo on left side Else apply algo on right side. Best Case: O(1) Worst Case: O(n^2) But there are very less chances of worst case. It is when the list is already sorted. On Thu, May 5, 2011 at 1:06 AM, amit amitjaspal...@gmail.com wrote: Hi , We are give a list of integers now our task is to find the top K integers in the list based on frequency. Apart from sorting the data can there be any other algorithm? -- 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. -- Gaurav Aggarwal SCJP- 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. -- Gaurav Aggarwal SCJP -- 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.
