Re: [algogeeks] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. You don't need to scan hash table again. Keep track of max while inserting. Update max when ever freq of some character is more than max. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
This question has already been discussed here.There are 4-5 methods to do this ,best is 'Moore voting algorithm' . refer: http://geeksforgeeks.org/?p=503 On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
see this .vote majority algorithm.. http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
This is a different problem, where the requested number with maximum frequency is not necessary majority. On 2010-6-1 13:19, harit agarwal wrote: see this .vote majority algorithm.. http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html http://userweb.cs.utexas.edu/%7Emoore/best-ideas/mjrty/index.html -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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] Implementing 2 stacks within a single linear array
Hi all, Can someone suggest me an efficient way to implement 2 stacks within a single linear array assuming neither of the stack overflows and an entire stack is never shifted to a different location within the array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: partion of array
Using subset sum method we can solve this. It actually DP check out Paybill question and its solution on topcoder website link : http://www.topcoder.com/stat?c=problem_statementpm=3114rd=5865 you will have a better understanding of subset sum problem after this -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Implementing 2 stacks within a single linear array
Hi, the stacks can implemented in the array one is starting at the begin and other is starting at the end growing in opposite directions. If the stack tops are colloid then there is no space left; means no room for extra elemnts. Thanks Sudarshan. On Tue, Jun 1, 2010 at 2:11 PM, Raj N rajn...@gmail.com wrote: Hi all, Can someone suggest me an efficient way to implement 2 stacks within a single linear array assuming neither of the stack overflows and an entire stack is never shifted to a different location within the array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sudarshan Reddy M -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Implementing 2 stacks within a single linear array
Start the first stack from the starting of the array and the second array from the end as shown below -- 0 n now for underflow condition will be stack 1 if (top1 == 0) stack 2 if (top2 == n) and overflow condition will be if (top2-top1+1 == 0) thats it correct me if anything wrong On Tue, Jun 1, 2010 at 2:11 PM, Raj N rajn...@gmail.com wrote: Hi all, Can someone suggest me an efficient way to implement 2 stacks within a single linear array assuming neither of the stack overflows and an entire stack is never shifted to a different location within the array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Check if 2 linked lists are identical
Hi all, Can someone suggest an efficient algorithm to check if 2 linked lists are identical. If 2 lists have to be sorted then there'll be a lot of space consumption for 2 separate linked lists. Can the whole process be done O(n2) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Implementing 2 stacks within a single linear array
How to implement 3 stacks using the same? On Tue, Jun 1, 2010 at 8:59 PM, Sudarshan Reddy M sudarsha...@gmail.comwrote: Hi, the stacks can implemented in the array one is starting at the begin and other is starting at the end growing in opposite directions. If the stack tops are colloid then there is no space left; means no room for extra elemnts. Thanks Sudarshan. On Tue, Jun 1, 2010 at 2:11 PM, Raj N rajn...@gmail.com wrote: Hi all, Can someone suggest me an efficient way to implement 2 stacks within a single linear array assuming neither of the stack overflows and an entire stack is never shifted to a different location within the array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sudarshan Reddy M -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
Hi Janak Thanks for your reply and good that we are exited. But if you see the problem, this approach is already known which has space complexity of O(n). But this if you are lucky that the array has numbers which are not more than n itself. If the given array is say 1000 size and it has numbers which can be anything, say a very large number 14556543 (lets forget max storage of int/long in various programing languages). Then it will be a tough job to keep insertion in your hash table O(1). There will be lots of hash classes and if you do not chose a good hash function (which can be better found by knowing the nature of the numbers in the aray and we done know about them) you may end up with O(n) insertion time. So lets think a less space expensive method. Tanks, Veer On Jun 1, 9:57 am, janak chandarana jac...@gmail.com wrote: On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. You don't need to scan hash table again. Keep track of max while inserting. Update max when ever freq of some character is more than max. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Check if 2 linked lists are identical
@Raj:sorting can be done in O(nlogn)..sort both and compare both.or use a hash map to store all elements of one LL and then compare it with otheror combine both the LL perform merge sort and start deleting adjacent elements.if adjacent elements in equal count then LL are equal and at end of process we get an empty list. On Tue, Jun 1, 2010 at 11:55 PM, Raj N rajn...@gmail.com wrote: Hi all, Can someone suggest an efficient algorithm to check if 2 linked lists are identical. If 2 lists have to be sorted then there'll be a lot of space consumption for 2 separate linked lists. Can the whole process be done O(n2) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Implementing 2 stacks within a single linear array
On Jun 1, 2:27 pm, Raj N rajn...@gmail.com wrote: How to implement 3 stacks using the same? On Tue, Jun 1, 2010 at 8:59 PM, Sudarshan Reddy M sudarsha...@gmail.comwrote: Hi, the stacks can implemented in the array one is starting at the begin and other is starting at the end growing in opposite directions. If the stack tops are colloid then there is no space left; means no room for extra elemnts. Thanks Sudarshan. On Tue, Jun 1, 2010 at 2:11 PM, Raj N rajn...@gmail.com wrote: Hi all, Can someone suggest me an efficient way to implement 2 stacks within a single linear array assuming neither of the stack overflows and an entire stack is never shifted to a different location within the array. Interleave them. If you need N stacks, use A(i), A(i+N), A(i+2N) ... for the i'th stack. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
