Re: [algogeeks]
Use hash maps... On Mon, Aug 16, 2010 at 10:06 PM, ashita dadlani ash@gmail.com wrote: You have a string say foobarfoo in which fo and oo aree repeated twice.You have to find all such repeated pairs in O(n) time,The string can only have alphanumeric elements in it. -- 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. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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: Data Structure for URL matching
http://www.ahhf45.com/info/Data_Structures_and_Algorithms/resources/technical_artile/ternary_search_tree/terstree.htm Refer this link. On Mon, Aug 16, 2010 at 10:29 PM, Chi c...@linuxdna.com wrote: I'm not sure what you want. I have post a solution to search for wildcards in tries. Now you claim to do it better with TS-Trees. Do you know who to compute a reverse TS-Tree? And why don't you try first to code a radix-tree, which is a compressed trie and build then the reverse radix-tree? Here is a solution to code a radix-tree, crit-bit- tree, pat-tree with mininmal understanding of comupter science: http://www.codeproject.com/KB/string/pat_and_huff.aspx IMHO I'm not sure why a Ternary-Search-Tree should be faster then a Radix-Tree? If a radix tree is already a binary-tree version of the trie, then can you explain me the advantage of a ternary-search-tree? On Aug 15, 8:31 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Seems a gud idea . I have read we can do better with Ternary Search Trees .Can anybody has any idea about it? On Sun, Aug 15, 2010 at 11:44 PM, Chi c...@linuxdna.com wrote: What you may need is a reverse trie. You may take a look at this: http://phpir.com/tries-and-wildcards On Aug 15, 3:21 pm, amit amitjaspal...@gmail.com wrote: In our indexes, we have millions of URLs each of which has a link to some page contents, that is, URL-contents. Now, suppose a user types a query with wild cards *, which represent 0 or multiple occurrences of any characters, how do you build the indexes such that such a type of query can be executed efficiently by finding all corresponding URLs-contents efficiently. For example, given a queryhttp://www.*o*ve* ou.com. You need to find iloveyou.com, itveabcu.com, etc. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- 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. -- Amit Jaspal Btech IT IIIT- 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] Re: Median of two arrays..
@maxim . my algo is for array of equal sizes.Sorry I didn't notice the unequal thing. On Tue, Aug 17, 2010 at 10:09 AM, Maxim Mercury maxim.merc...@gmail.comwrote: above algo isnt handling unequal length arrays, On Aug 13, 10:06 pm, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Check this code int med1,med2; void func(int a[], int x1, int x2, int b[], int y1, int y2){ int midx,midy; if((y2-y1+1)==2) { med1=max(a[x1],b[y1]); med2=min(a[x2],b[y2]); return;} midx=(x1+x2)/2; midy=(y1+y2)/2; if(a[midx]b[midy]){ x2=x2-(midy-y1); y1=midy; }else{y2=y2-(midx-x1); x1=midx;} func(a,x1,x2,b,y1,y2); } med1 and med2 are two medians. -- 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.
[algogeeks] Re: Data Structure for URL matching
Hi Amit, it is not proven that a ternary-search-tree is faster: http://nicolas.lehuen.com/category/pytst/ From the article: The difference between pytst and ctst This gives 11 nodes for 7 strings. I won’t waste time to draw the ternary search tree equivalent, so you’ll have to trust me, but you would need at least 25 nodes. Of course the node don’t contain the same things, but the payload/overhead ratio is highly in favor of ctst. Maybe it is a little faster but it has a bigger space consumption. On Aug 17, 12:24 am, Amit Jaspal amitjaspal...@gmail.com wrote: http://www.ahhf45.com/info/Data_Structures_and_Algorithms/resources/t... Refer this link. On Mon, Aug 16, 2010 at 10:29 PM, Chi c...@linuxdna.com wrote: I'm not sure what you want. I have post a solution to search for wildcards in tries. Now you claim to do it better with TS-Trees. Do you know who to compute a reverse TS-Tree? And why don't you try first to code a radix-tree, which is a compressed trie and build then the reverse radix-tree? Here is a solution to code a radix-tree, crit-bit- tree, pat-tree with mininmal understanding of comupter science: http://www.codeproject.com/KB/string/pat_and_huff.aspx IMHO I'm not sure why a Ternary-Search-Tree should be faster then a Radix-Tree? If a radix tree is already a binary-tree version of the trie, then can you explain me the advantage of a ternary-search-tree? On Aug 15, 8:31 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Seems a gud idea . I have read we can do better with Ternary Search Trees .Can anybody has any idea about it? On Sun, Aug 15, 2010 at 11:44 PM, Chi c...@linuxdna.com wrote: What you may need is a reverse trie. You may take a look at this: http://phpir.com/tries-and-wildcards On Aug 15, 3:21 pm, amit amitjaspal...@gmail.com wrote: In our indexes, we have millions of URLs each of which has a link to some page contents, that is, URL-contents. Now, suppose a user types a query with wild cards *, which represent 0 or multiple occurrences of any characters, how do you build the indexes such that such a type of query can be executed efficiently by finding all corresponding URLs-contents efficiently. For example, given a queryhttp://www.*o*ve* ou.com. You need to find iloveyou.com, itveabcu.com, etc. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- 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. -- Amit Jaspal Btech IT IIIT- 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] Time complexity - is anybody bothered about it anyway?
Greetings How many of you guys calculate the time complexity of an algorithm before implementing it on a day to day basis? When you review your code, before committing it to the live source code base, does anybody discuss the time complexity? Would love to hear your interesting experiences.. Regards Ashutosh -- 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] Time complexity - is anybody bothered about it anyway?
yes ofcourse.the efficiency of my code is always a concern to me... On 17 August 2010 18:54, Ashutosh Tamhankar asshuto...@gmail.com wrote: Greetings How many of you guys calculate the time complexity of an algorithm before implementing it on a day to day basis? When you review your code, before committing it to the live source code base, does anybody discuss the time complexity? Would love to hear your interesting experiences.. Regards Ashutosh -- 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] Adobe Question : Convert a number given in base B1 to a number in base B2 without using any intermediate base
I had proposed an algorithm of repeatedly subtracting 1 from the given number and subsequently adding 1 to the new number initialised to 0, till the given number becomes 0. However as soon as the digit reaches the limit , the digit becomes 0 and you add 1 to the next digit. I was not able to code it properly as i had to use int data type only. It would have been easy if the array of integers was allowed to use. Pls suggest the code for the same or some better algo. Thanx Lakshaya -- 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] BFS
Cud any1 tell me hw to implement BFS without a queue?! -- 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] BFS
Cud any1 tell hw 2 implement BFS of a tree without queue?! -- 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: BFS
@Giri: Could anyone tell how to spell could, anyone, how, and to? On Aug 17, 11:23 am, Giri giri.pe...@gmail.com wrote: Cud any1 tell hw 2 implement BFS of a tree without queue?! -- 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: Time complexity - is anybody bothered about it anyway?
For 30 years, I developed mathematical software (linear equation solvers, eigenvalue routines, fast Fourier transforms, etc.) on a wide variety of high-performance computers with interesting architectures. For those, the optimal-order algorithms are well known. My principal goal was to implement a variant of the best algorithm that made the constant as small as possible. Dave On Aug 17, 8:24 am, Ashutosh Tamhankar asshuto...@gmail.com wrote: Greetings How many of you guys calculate the time complexity of an algorithm before implementing it on a day to day basis? When you review your code, before committing it to the live source code base, does anybody discuss the time complexity? Would love to hear your interesting experiences.. Regards Ashutosh -- 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: BFS
the point here is not the language.. when you could understand what those words mean, it serves the purpose.. then sorry itz Breadth First Traversal ofa tree without using queue.. got it?! -- 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: BFS
What you want is a php-traversal of a file-system: http://devzone.zend.com/article/1235#Heading7 On Aug 17, 7:24 pm, Giri giri.pe...@gmail.com wrote: the point here is not the language.. when you could understand what those words mean, it serves the purpose.. then sorry itz Breadth First Traversal ofa tree without using queue.. got it?! -- 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: BFS
Or do you mean without a recursion, without a stack!? On Aug 17, 7:40 pm, Chi c...@linuxdna.com wrote: What you want is a php-traversal of a file-system: http://devzone.zend.com/article/1235#Heading7 On Aug 17, 7:24 pm, Giri giri.pe...@gmail.com wrote: the point here is not the language.. when you could understand what those words mean, it serves the purpose.. then sorry itz Breadth First Traversal ofa tree without using queue.. got it?! -- 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: Addition Of numbers in SLL
The Solution is pretty straight forward when you long number is represented in reverse order in linked list. If the number is not in reverse order, We need an Explicit stack or we must Use Recursion . Other way around this is to construct another parallel linked list along with Sum(linked list) for maintaining the carry information and use multiple passes until the Carry linked list completely vanishes. Whenever you find the sum digit , Use sum-digit = (list1-digit + list2-digit + Carry-next-digit) % 10 Carry-digit = (list1-digit + list2-digit + Carry-digit) / 10 On Mon, Aug 16, 2010 at 8:03 AM, Ashish Goel ashg...@gmail.com wrote: int add(struct node* pL1, struct node * pl2,int gap/*no of digits in l1 -no of digits in l2*/) { //assumption, # of nodes in L1 is # of nodes in L2, make sure this before calling this, counting nodes is less costlier than reversal if (!(pl1) || !(pl2)) return 0; if (gap0) { carry = add(pL1-next, pL2, gap-1); carry = (pl1-data+carry)/10; pl1-data =(pl1-data+carry) %10; return carry; } else { carry = add(pL1-next, pl2-next, gap -1); carry = (pl1-data+pl2-data+carry)/10; pl1-data =(pl1-data+pl2-data+carry) %10; return carry; } } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Aug 15, 2010 at 12:19 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: @Dave..Can u provide a small snippet for ur explanation pls.. -- 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] Array Problem
Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- 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] Longest SubSequence with Sum K
Given an array, find the longest subarray which the sum of the subarray less or equal then the given MaxSum int[] FindMaxSumArray(int[] array, int maxsum) for example, given array: {1, -2, 4, 5, -2, 6, 7} maxsum=7 the result would be: {1,-2, -2, 6} -- 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] Brent's algorithm
hi..i wanna know what is brent's algorithm n whether it can be used to detect loops in linked list.If yes..is it better than Floyd's cycle finding algo? -- 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: BFS
Tree *node for(i=1;i=height;i++) { levelorder(node,i); } void levelorder(Tree *node,int level) { if(level==1) printf(node-value); else levelorder(node-left,level-1) levelorder(node-right,level-1); } -- 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] Find conflicting meetings
Given an array of meetings: struct meeting { start_time; end_time; bool conflict; } Set conflict = True for all meetings that conflict with some other meeting. Can anyone give a solution of O(NlogN) or less? -- Shuaib -- 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.