Re: [algogeeks] Check if 2 linked lists are identical
merge sort both lists: O(nlogn) Now, for both lists to be identical, just compare the corresponding elements in the lists i.e. L1(1) == L2(1), L1(2) == L2(2) ... = O(n) --Sundeep. On Wed, Jun 2, 2010 at 10:47 PM, Raj N rajn...@gmail.com wrote: @Antony: The 2 lists should have the same elements as well the number must be equal On Wed, Jun 2, 2010 at 5:38 PM, Antony Vincent Pandian.S. sant...@gmail.com wrote: @Raj What do you mean by identical? You are just concerned about the presence of one element in another LL or you are concerned about the equality of number of elements too? On 6/2/10, Raj N rajn...@gmail.com wrote: @sharad kumar: But don't you think this'll consume a lot of space. Merge sort will give O(nlogn) complexity when a separate LL is used to store the sorted elements but if we disbuild the same LL it'll be O(n2). And also wat do u mean by combining LL can u explain On Wed, Jun 2, 2010 at 6:48 AM, sharad kumar aryansmit3...@gmail.com wrote: @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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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.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
construct bst from both list and check if the bst are equal by printing their inorder traversal. On 2 June 2010 22:47, Raj N rajn...@gmail.com wrote: @Antony: The 2 lists should have the same elements as well the number must be equal On Wed, Jun 2, 2010 at 5:38 PM, Antony Vincent Pandian.S. sant...@gmail.com wrote: @Raj What do you mean by identical? You are just concerned about the presence of one element in another LL or you are concerned about the equality of number of elements too? On 6/2/10, Raj N rajn...@gmail.com wrote: @sharad kumar: But don't you think this'll consume a lot of space. Merge sort will give O(nlogn) complexity when a separate LL is used to store the sorted elements but if we disbuild the same LL it'll be O(n2). And also wat do u mean by combining LL can u explain On Wed, Jun 2, 2010 at 6:48 AM, sharad kumar aryansmit3...@gmail.com wrote: @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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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.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, Just to clarify, same elements refer to copy of identical data or link list members pointing to same data ? On Wed, Jun 2, 2010 at 10:47 PM, Raj N rajn...@gmail.com wrote: @Antony: The 2 lists should have the same elements as well the number must be equal On Wed, Jun 2, 2010 at 5:38 PM, Antony Vincent Pandian.S. sant...@gmail.com wrote: @Raj What do you mean by identical? You are just concerned about the presence of one element in another LL or you are concerned about the equality of number of elements too? On 6/2/10, Raj N rajn...@gmail.com wrote: @sharad kumar: But don't you think this'll consume a lot of space. Merge sort will give O(nlogn) complexity when a separate LL is used to store the sorted elements but if we disbuild the same LL it'll be O(n2). And also wat do u mean by combining LL can u explain On Wed, Jun 2, 2010 at 6:48 AM, sharad kumar aryansmit3...@gmail.com wrote: @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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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.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] Implementing 2 stacks within a single linear array
for three stacks u can use indices 0 3 6 etc for stack1. 1 4 7 for stack 2 and 2 5 8 etc for stack 3. now if any of the stack overflows but there is still space in array as other stacks have few element then now u can grow ur stack in reverse direction as shown below : indices of array : 0 1 2 3 4 5 6 7 8 9 10 11 12 contents 1 2 3 1 1 1 1 / \ \ top2top3 top1 here 1 represents element of stack1 2 for stack 2 and so on. now if u want to insert more element in stack 1 it will overflow while 2 and 3 have space so wat u can do now is grow stack 1 in reverse direction. ie now place elements for stack 1 in index 11 and so now top1 will point to 11 and so on. u can indicate this behaviour of stack1 by using some tag. i hope this will work.. -- 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
three or more stacks can be made by using linked array representation -- 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
u have not sorted the array . first sort the array nd then apply the approach. u ll get the ryt ans On 1 June 2010 21:32, Jitendra Kushwaha jitendra.th...@gmail.com wrote: 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.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] Re: Can you solve this?
same question as wat i asked in partioning of array such that the diff is min. On 31 May 2010 22:07, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Same question with interesting answers in stackoverflow : http://stackoverflow.com/questions/890171/algorithm-to-divide-a-list-of-numbers-into-2-equal-sum-lists On Mon, May 31, 2010 at 5:54 PM, Anurag Sharma anuragvic...@gmail.comwrote: Well, in that case, then just forget the balancing the number of elements in the 2 teams portion of my solution above :) Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Mon, May 31, 2010 at 10:38 AM, Nik_nitdgp nikhil.bhoja...@gmail.comwrote: This problem is like 2 processor job scheduling problem ,We may get an optimal solution for different instances using different algorithm apart from brute force.Whereas Brute force covers all possible subsets but may take years to complete if N is large. above algo fails in the following example. Eg. 2 2 2 3 3 above algo gives: T1: 2 2 3 =7 T2: 2 3 =5 But closest distribution is T1=2 2 2=6 T2 3 3=6 On May 31, 9:30 am, W Karas wka...@yahoo.com wrote: Is this the same problem as: http://groups.google.com/group/algogeeks/browse_frm/thread/26c31cc253. .. ? Or can the teams have different numbers of players? On May 30, 2:28 pm, Veer Sharma thisisv...@rediffmail.com wrote: Hi Friends, This is my first post to this forum. A Hi to all of you and here is my first problem... Giiven int n, the total number of players and their skill-point. Distribute the players on 2 evenly balanced teams. Lets see who gives the best solution (least space complexity / least time complexity or both...) -- 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.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.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] Removing extra parentheses in an infix string
1.calculte the postfix of given expression. 2.now remove a particular parenthesis from expression and check if the postfix of this expression is equal to the postfix of original expression. if yes then the parenthesis we have removed were extra. if no then the parenthesis were not exta. 3 now remove other parenthesis as step 2 and repeat till u have done this for all parenthesis On 1 June 2010 20:12, Raj N rajn...@gmail.com wrote: How to remove extra parentheses in an infix string. For example if it is A+(B*C) parentheses for * is not required as it has higher precedence. Can someone suggest a good routine for this? -- 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] Re: partion of array
@divya: but still haven't you seen Jagadish's example? It is a counterexample to your greedy approach. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
You can restore the infix expression from the postfix expression calculated, only add parenthesis when necessary in each step. On 2010-6-3 15:35, divya jain wrote: 1.calculte the postfix of given expression. 2.now remove a particular parenthesis from expression and check if the postfix of this expression is equal to the postfix of original expression. if yes then the parenthesis we have removed were extra. if no then the parenthesis were not exta. 3 now remove other parenthesis as step 2 and repeat till u have done this for all parenthesis On 1 June 2010 20:12, Raj N rajn...@gmail.com mailto:rajn...@gmail.com wrote: How to remove extra parentheses in an infix string. For example if it is A+(B*C) parentheses for * is not required as it has higher precedence. Can someone suggest a good routine for this? -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%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. -- 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
oh...okay... good example... On 3 June 2010 13:23, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya: but still haven't you seen Jagadish's example? It is a counterexample to your greedy approach. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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] Re: Can you solve this?
@Divya: nope, your Q requires equal count too whereas this doesn't. On Thu, Jun 3, 2010 at 1:06 PM, divya jain sweetdivya@gmail.com wrote: same question as wat i asked in partioning of array such that the diff is min. On 31 May 2010 22:07, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Same question with interesting answers in stackoverflow : http://stackoverflow.com/questions/890171/algorithm-to-divide-a-list-of-numbers-into-2-equal-sum-lists On Mon, May 31, 2010 at 5:54 PM, Anurag Sharma anuragvic...@gmail.comwrote: Well, in that case, then just forget the balancing the number of elements in the 2 teams portion of my solution above :) Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Mon, May 31, 2010 at 10:38 AM, Nik_nitdgp nikhil.bhoja...@gmail.comwrote: This problem is like 2 processor job scheduling problem ,We may get an optimal solution for different instances using different algorithm apart from brute force.Whereas Brute force covers all possible subsets but may take years to complete if N is large. above algo fails in the following example. Eg. 2 2 2 3 3 above algo gives: T1: 2 2 3 =7 T2: 2 3 =5 But closest distribution is T1=2 2 2=6 T2 3 3=6 On May 31, 9:30 am, W Karas wka...@yahoo.com wrote: Is this the same problem as: http://groups.google.com/group/algogeeks/browse_frm/thread/26c31cc253. .. ? Or can the teams have different numbers of players? On May 30, 2:28 pm, Veer Sharma thisisv...@rediffmail.com wrote: Hi Friends, This is my first post to this forum. A Hi to all of you and here is my first problem... Giiven int n, the total number of players and their skill-point. Distribute the players on 2 evenly balanced teams. Lets see who gives the best solution (least space complexity / least time complexity or both...) -- 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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Removing extra parentheses in an infix string
Will this work ?
consider A+(B*C)
have an operator stack to hold the operators. As we scan elements from left
to right,push the operators in operator stack.
when you encounter a '(' , then scan to find the first operator that comes
after '(' (in this case *).
If this operator has a higher precedence than the operator @ top of stack
(in this case +). Then we can safely remove the parenthesis. Else we cant
remove the brackets
On Thu, Jun 3, 2010 at 1:05 PM, divya jain sweetdivya@gmail.com wrote:
1.calculte the postfix of given expression.
2.now remove a particular parenthesis from expression and check if the
postfix of this expression is equal to the postfix of original expression.
if yes then the parenthesis we have removed were extra. if no then the
parenthesis were not exta.
3 now remove other parenthesis as step 2 and repeat till u have done this
for all parenthesis
On 1 June 2010 20:12, Raj N rajn...@gmail.com wrote:
How to remove extra parentheses in an infix string. For example if it
is A+(B*C) parentheses for * is not required as it has higher
precedence. Can someone suggest a good routine for this?
--
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.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] Valid permutation of the brackets
The question is that you have to print all the valid permutations of
the given number of brackets
for example for input 3 we have the output
1 ((()))
2 (()())
3 (())()
4 ()(())
5 ()()()
total five valid permutation
this can be solved in O( 2^(2n) ) where n is number of brackets .
Algo will be like this
1. Try '(' and ')' in every position and print the correct
permutation.Neglect all other permutation
As catalon number is far less then exponential growth ,can anybody
suggest some better algorithm
--
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
@Raj N : You are right overflow is top2-(top1+1)==0 @Anand : The oveflow condition is dependent how underflow condition are implemented. Considering underflow above condition for overflow suffice For 3 stacks a efficient algo is not easy to think in a single array , yet we can optimise according the usage. For example lets say out of 3 stack we know the growth of 2nd stack more closely and we know its variations boundary of 2nd stack more clearly than others two. In such case make stack 2 static giving it its particular location. For the rest two apply same as implementation of two stack | stack2 |1st 3rd---| __ for n stacks make n/2 such intervals. If n is odd, one interval will be for a single 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.
Re: [algogeeks] Valid permutation of the brackets
@jitendra
#includeiostream
using namespace std;
void parens(int pairs)
{
int i, j, s, n = 2*(pairs - 1);
for (i = 0; i 1 n; i++) {
for (s = 1, j = 0; (j n) (s = 0) (s = pairs); j++)
s += ((i j) 1) ? 1 : -1;
if ((j != n) || (s != 1))
continue;
cout(;
for (j = 0; j n; j++)
((i j) 1) ? putchar('(') : putchar(')');
cout)endl;
}
}
int main()
{
parens(3);
cin.sync();
cin.get();
return 0;
}
On Thu, Jun 3, 2010 at 1:45 PM, Jitendra Kushwaha
jitendra.th...@gmail.comwrote:
The question is that you have to print all the valid permutations of
the given number of brackets
for example for input 3 we have the output
1 ((()))
2 (()())
3 (())()
4 ()(())
5 ()()()
total five valid permutation
this can be solved in O( 2^(2n) ) where n is number of brackets .
Algo will be like this
1. Try '(' and ')' in every position and print the correct
permutation.Neglect all other permutation
As catalon number is far less then exponential growth ,can anybody
suggest some better algorithm
--
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.
Re: [algogeeks] Re: Can you solve this?
Still the solution will be similar and actually a bit simpler. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
A*(B+C*D) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
So there is a prob algoose A*(B*C) and a*(b*c+d) i hope you understood -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
why don't you make use of the optimal substructure. You can easily use the recurrence relation as DP @all : people don't just paste your code. Words are better than code -- 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
simple in place O(n lg n) solution. Choose a pivot in first array and partition it like in quicksort. Find the pivot in second array and partition. Now recurse on both halves. At any point if no of elements in array are not equal... Abort! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
A recursive way of filling each position is better, so we can cut it down
when its invalid and not proceed further. Something like below,
// 1-based indexing
- global n , A[2*n+1]
- go( ci , cs ) // cur.index , cur.sum
{
if( ci == 2n+1 ) print A with [ 1 = '(', -1 = ')' ]
toFill = 2*n - ci + 1;
if( cs toFill ) { A[ci] = 1; go( ci+1 , cs+1 ); }
if( cs 0 ) { A[ci] = -1; go( ci+1 , cs-1 ); }
}
- in main A[1] = 1; go(2,1);
-- AK
On Thu, Jun 3, 2010 at 1:45 PM, Jitendra Kushwaha
jitendra.th...@gmail.comwrote:
The question is that you have to print all the valid permutations of
the given number of brackets
for example for input 3 we have the output
1 ((()))
2 (()())
3 (())()
4 ()(())
5 ()()()
total five valid permutation
this can be solved in O( 2^(2n) ) where n is number of brackets .
Algo will be like this
1. Try '(' and ')' in every position and print the correct
permutation.Neglect all other permutation
As catalon number is far less then exponential growth ,can anybody
suggest some better algorithm
--
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.
--
Anil Kishore
--
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] Valid permutation of the brackets
Discard illegal prefix as soon as possible, and only proceed with legal one.
* For some position, if the number of '(' and ')' are equal, then do not
try ')' on that position.
* If the number of '(' reaches n, fill the rest positions with ')' to
get a valid permutation.
On 2010-6-3 16:15, Jitendra Kushwaha wrote:
The question is that you have to print all the valid permutations of
the given number of brackets
for example for input 3 we have the output
1 ((()))
2 (()())
3 (())()
4 ()(())
5 ()()()
total five valid permutation
this can be solved in O( 2^(2n) ) where n is number of brackets .
Algo will be like this
1. Try '(' and ')' in every position and print the correct
permutation.Neglect all other permutation
As catalon number is far less then exponential growth ,can anybody
suggest some better algorithm
--
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: Can you solve this?
yep, constraints are fewer here but in terms of problem statement 'same' and 'similar' can create diversions. On Thu, Jun 3, 2010 at 6:01 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Still the solution will be similar and actually a bit simpler. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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
But perhaps the elements in lists may not be in order. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Thu, Jun 3, 2010 at 6:38 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: simple in place O(n lg n) solution. Choose a pivot in first array and partition it like in quicksort. Find the pivot in second array and partition. Now recurse on both halves. At any point if no of elements in array are not equal... Abort! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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] Re: Can you solve this?
This should be solvable by dp as in knapsack problem where value = weights and W = S/2. where S = sum of all elements in the array. The claim here is diff in sum of two subsets will be minimum when one maximizes a sub-set sum (say s) where sum (s) is closest to S/2. Divya's problem is looking for balanced sets which may or may not be feasible using a modified form of this. On Thu, Jun 3, 2010 at 7:06 PM, saurabh gupta sgup...@gmail.com wrote: yep, constraints are fewer here but in terms of problem statement 'same' and 'similar' can create diversions. On Thu, Jun 3, 2010 at 6:01 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Still the solution will be similar and actually a bit simpler. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Valid permutation of the brackets
@Jitendra: Catalan number grows at least exponentially: http://mathworld.wolfram.com/CatalanNumber.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] Removing extra parentheses in an infix string
Thats right !!! On Thu, Jun 3, 2010 at 6:08 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: So there is a prob algoose A*(B*C) and a*(b*c+d) i hope you understood -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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] Removing extra parentheses in an infix string
If the base logic follows the below rule, it should work. If any operator within parenthesis is of less precedence to the operator before the opening parenthesis, the parenthesis can not be removed. For cases of equal precedence of operators before parenthesis and within parenthesis, transitivity condition should be checked. If transitive, parenthesis can be removed else should be retained. Eg: parenthesis cannot be removed for division operator while can be removed for multiplicative or addition or subtraction operator. On 6/3/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: So there is a prob algoose A*(B*C) and a*(b*c+d) i hope you understood -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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
Consider two linked lists l1 and l2. Create 2 hash maps,h1 and h2, one for each list with the format, element, number of occurrence. Traverse one element in each list at a time. For each element in list l1, check whether it is present in h2. If yes, remove the element from h2 if the number of occurrence is 1 else reduce the number of occurrence of that element in hash map, h2. If the element is not present in hashmap, h2, insert the element in hashmap, h1 with number as occurrence as 1. Do the same with the other linklist, l2. Iterate over both the lists simultaneously. If a case is hit where we have some more elements in one list and we dont have in another list, abort since length of the list itself is not identical. If the length of both the lists are same, and we hit the end of the lists, check whether both the hash maps, h1 and h2 are empty. If empty, both lists are identical else they are not. The time complexity is less in this case, though the space complexity may be high especially when the lists are equal with no common elements between each lists. On 6/3/10, Anurag Sharma anuragvic...@gmail.com wrote: But perhaps the elements in lists may not be in order. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Thu, Jun 3, 2010 at 6:38 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: simple in place O(n lg n) solution. Choose a pivot in first array and partition it like in quicksort. Find the pivot in second array and partition. Now recurse on both halves. At any point if no of elements in array are not equal... Abort! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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.
