Re: [algogeeks] Re: Amazon Question
i think that we have to generate substrings from the given string such that the similarity is above 50% for eg. word =foo we have to generate the strings which must be greater than half of the given string length {fo,oo} (in this case) after this operation we have the following string set {foo,fo,oo} then we can doselect* from product where name like '%foo%'select* from product where name like '%fo%'. select* from product where name like '%oo%' please do correct me if i am wrong On Mon, Sep 13, 2010 at 1:01 PM, SVIX saivivekh.swaminat...@gmail.comwrote: select * from product where name like '%foo%' and len(name) =6; btw, how do u define similarity? i'm guessing it wouldn't be this simple... On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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. -- By B. Praveen -- 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: Amazon Question
you will have to use the concept of edit distance .. google for edit distance and you may find too many good articles on it. Levenshtein distance is one such algorithm for measuring the amount of difference between two sequences [edit distance] On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar praveen200...@gmail.comwrote: i think that we have to generate substrings from the given string such that the similarity is above 50% for eg. word =foo we have to generate the strings which must be greater than half of the given string length {fo,oo} (in this case) after this operation we have the following string set {foo,fo,oo} then we can doselect* from product where name like '%foo%'select* from product where name like '%fo%'. select* from product where name like '%oo%' please do correct me if i am wrong On Mon, Sep 13, 2010 at 1:01 PM, SVIX saivivekh.swaminat...@gmail.comwrote: select * from product where name like '%foo%' and len(name) =6; btw, how do u define similarity? i'm guessing it wouldn't be this simple... On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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. -- By B. Praveen -- 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 , Anuj Maurice -- 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: Amazon Question
No, best way is to use a trie, or a suffix-trie. Look here: http://phpir.com/tries-and-wildcards On Sep 13, 12:32 pm, anuj maurice anuj.maur...@gmail.com wrote: you will have to use the concept of edit distance .. google for edit distance and you may find too many good articles on it. Levenshtein distance is one such algorithm for measuring the amount of difference between two sequences [edit distance] On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar praveen200...@gmail.comwrote: i think that we have to generate substrings from the given string such that the similarity is above 50% for eg. word =foo we have to generate the strings which must be greater than half of the given string length {fo,oo} (in this case) after this operation we have the following string set {foo,fo,oo} then we can do select* from product where name like '%foo%'select* from product where name like '%fo%'. select* from product where name like '%oo%' please do correct me if i am wrong On Mon, Sep 13, 2010 at 1:01 PM, SVIX saivivekh.swaminat...@gmail.comwrote: select * from product where name like '%foo%' and len(name) =6; btw, how do u define similarity? i'm guessing it wouldn't be this simple... On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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. -- By B. Praveen -- 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 , Anuj Maurice -- 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: Amazon Question
cant it be like '%f%' On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar praveen200...@gmail.comwrote: i think that we have to generate substrings from the given string such that the similarity is above 50% for eg. word =foo we have to generate the strings which must be greater than half of the given string length {fo,oo} (in this case) after this operation we have the following string set {foo,fo,oo} then we can doselect* from product where name like '%foo%'select* from product where name like '%fo%'. select* from product where name like '%oo%' please do correct me if i am wrong On Mon, Sep 13, 2010 at 1:01 PM, SVIX saivivekh.swaminat...@gmail.comwrote: select * from product where name like '%foo%' and len(name) =6; btw, how do u define similarity? i'm guessing it wouldn't be this simple... On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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. -- By B. Praveen -- 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: On random number generation
So finally which answer is correct ? There are many answers and I'm doubtful abt there correctness !! -- 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: Amazon Question
Well, no, it is not told that you are given the binaries for the database, too. On Sep 13, 1:27 pm, sharad kumar aryansmit3...@gmail.com wrote: cant it be like '%f%' On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar praveen200...@gmail.comwrote: i think that we have to generate substrings from the given string such that the similarity is above 50% for eg. word =foo we have to generate the strings which must be greater than half of the given string length {fo,oo} (in this case) after this operation we have the following string set {foo,fo,oo} then we can do select* from product where name like '%foo%'select* from product where name like '%fo%'. select* from product where name like '%oo%' please do correct me if i am wrong On Mon, Sep 13, 2010 at 1:01 PM, SVIX saivivekh.swaminat...@gmail.comwrote: select * from product where name like '%foo%' and len(name) =6; btw, how do u define similarity? i'm guessing it wouldn't be this simple... On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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. -- By B. Praveen -- 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: Yahoo Question:Greatest Sub-sequential sum
what is the complexity of this problem I think its O(n*n!) but confused or O(n!) or O(n^2) right me if i m wrong.its necessary to check the complexity REPLY is appreciated from every algogeek #include stdio.h #includeconio.h #includeiostream.h #includestdlib.h int main() { int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1}; int length = 11; int begin, end, beginmax, endmax, maxsum, sum, i; sum = 0; beginmax = 0; endmax = -1; maxsum = 0; for (begin=0; beginlength; begin++) { sum = 0; for(end=begin; endlength; end++) { sum += a[end]; if(sum maxsum) { maxsum = sum; beginmax = begin; endmax = end; } } coutsum\t; } coutendl; for(i=beginmax; i=endmax; i++) { printf(%d\n, a[i]); } getch(); } its has time complexity O(n^2) ..does better solution exist -- 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: Amazon Question
How would you define 50% or more similarity ? On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote: trie On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote: pagerank algo On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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 . 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: Amazon Question
What does 50% or more similarity means?? Trie will work only if prefix is equal. On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote: trie On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote: pagerank algo On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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 . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Bharath -- 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: On random number generation
All of them are correct. You need to verify that the probability of getting each of the numbers from 0 to 7 are same. In the example given by Gene, here is the explanation below: rand04()rand04()5*rand04() Sum Sum/3 0 0 0 0 0 1 0 0 1 0 2 0 0 2 0 3 0 0 3 1 4 0 0 4 1 0 1 5 5 1 1 1 5 6 2 2 1 5 7 2 3 1 5 8 2 4 1 5 9 3 0 2 10 10 3 1 2 10 11 3 2 2 10 12 4 3 2 10 13 4 4 2 10 14 4 0 3 15 15 5 1 3 15 16 5 2 3 15 17 5 3 3 15 18 6 4 3 15 19 6 0 4 20 20 6 1 4 20 21 7 2 4 20 22 7 3 4 20 23 7 4 4 20 24 8 As you can see, each of the numbers from 0 to 7 can come 3 times hence they have equal probability. In the other approach in the link I put, the user has tried to use a number system to the base 2. On Sep 13, 5:21 pm, Krunal Modi krunalam...@gmail.com wrote: So finally which answer is correct ? There are many answers and I'm doubtful abt there correctness !! -- 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: Given an array, find out if there exists a pair of nos. that adds up to a sum 'x'
use mapint,bool S when you encounter a particular number check S[x-num] is true, if so return that pair. else S[num]=true On Sat, Sep 11, 2010 at 1:09 PM, topojoy biswas topojoy.bis...@gmail.comwrote: put all the numbers in a hash table( which demands O(n) space) and then pick each number in the array and check in the hashtable whether x-chosen number is present. this would take O(1) per search. Do it for all the numbers in the array. It wold take O(n). On Fri, Sep 10, 2010 at 11:00 PM, jagadish jagadish1...@gmail.com wrote: Hi, O(n) solution is possible if the array is presorted! Else i think it is NOT. 1.Have two ptrs (one from first and other to track the array from last) 2.s=a[left]+a[right] 3.if(ssum) left++; else if(ssum) right--; else print sum found On Sep 10, 10:19 pm, bittu shashank7andr...@gmail.com wrote: Q Given an array, find out if there exists a pair of nos. that adds up to a sum 'x' in O(n) possible,, -- 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. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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] number of inversion pairs
Given an array of n integers find all the inversion pairs in O(n) Inversion pair is one where a[i]a[j], ij -- 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] uva toolkit
http://xrds.acm.org/ http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html http://www.uvatoolkit.com/problemssolve.php Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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] cyclic String
Concatenate the string to itself and if the given string is a substring of the new concatenated string then it is a cyclic string On Sat, Sep 11, 2010 at 3:38 PM, Ashim Kapoor ashimkap...@gmail.com wrote: I can do it in 2 O(n)sweeps if all elements are distinct. 12345 23451 Sweep one to find the 1st element of string 1 in string 2. Sweep 2 to compare each element of the 2 strings from the position mod n found in the 1st sweep. I dont know how to do it if elements are repeated. but the way Praveen does it is really cool i think. Sat, Sep 11, 2010 at 1:54 PM, Praveen Baskar praveen200...@gmail.comwrote: str=hello; str1=lloeh; if (str+str).subString(str1) is true then the string is cyclic string of another On Sat, Sep 11, 2010 at 1:52 PM, bittu shashank7andr...@gmail.comwrote: How will you check if a string is cyclic string of another solution O(n)..???/?? or even less compraiosn.. -- 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. -- By B. Praveen -- 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] Re: uva toolkit
sorry please discard the above mail On 13 September 2010 21:11, Priyanka Chatterjee dona.1...@gmail.com wrote: http://xrds.acm.org/ http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html http://www.uvatoolkit.com/problemssolve.php Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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:Yahoo Question:Greatest Sub-sequential sum
#include stdio.h #includeconio.h #includeiostream.h #includestdlib.h int max_so_far = 0; int max_ending_here = 0; int main()/// its also O(n) solution chk out this { int a[]={5, 7, -3, 1, -11, 8, 12};//{-2, 1, -3, 4, -1, 2, 1, -5, 4}; O(n) Best Algo int size=sizeof(a)/sizeof(int); for(int i=0;isize;i++) { max_ending_here = 0max_ending_here + a[i]? 0 : max_ending_here + a[i];//(a b) ? a : b. max_so_far = max_so_farmax_ending_here? max_so_far : max_ending_here; } cout max_so_far; getch(); } -- 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:Given an array, find out if there exists a pair of nos. that adds up to a sum 'x'
#include stdio.h #includeconio.h #includeiostream.h #includestdlib.h /// //sorted sequense O(n) what we have 2 do for unsorted xcept sorting int main() { int a[]={1,2,3,4,5}; int x=5; int left=0; int right=5; int sum=0; while ( sum !=x (left right) ) { sum=a[left]+a[right]; if(sumx) right--; else if(sumx) left++; else break; } coutLEFT :a[left]\t RIGHT:a[right]endl; coutwhose sum issum; getch(); } -- 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] Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square
Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square in O(n) is solution possible in O(logn) Regards Shashank -- 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: Amazon Question
50% should be define like this: select * from product where name like '%foo%' and len(name) =6; On Sep 13, 9:18 am, Bharath bharath1...@gmail.com wrote: What does 50% or more similarity means?? Trie will work only if prefix is equal. On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote: trie On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote: pagerank algo On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- 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 . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Bharath -- 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] Free Download Lectures of Data Structure Algorithm,Programming and many more
For free Download Collection of Lectures and Presentation of Programming and Algorithm and many more related to the field of Computer Science.Visit http://computerscienceppt.blogspot.com/ This blog contains more then 50 subjects related to the field of Computer Science. This blog will help computer science teachers as well as students in their educational career. -- 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: number of inversion pairs
yes, but in O(n)? How? in O(n^2) its easy. For every int, if successive ints are lesser, you've found a pair. How can you find all pairs in o(n) time? On Sep 13, 9:05 am, sharad kumar aryansmit3...@gmail.com wrote: linear decreasing sub sequence problem On Mon, Sep 13, 2010 at 9:10 PM, Raj N rajn...@gmail.com wrote: Given an array of n integers find all the inversion pairs in O(n) Inversion pair is one where a[i]a[j], ij -- 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] number of inversion pairs
My two cents If you were asked in O(n log n) you have to modified the merge sort algorithm for count the number of inversion! Wladimir Araujo Tavares http://www.si.ufc.br/~wladimir http://www.si.ufc.br/%7Ewladimir/ Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos. On Mon, Sep 13, 2010 at 1:05 PM, sharad kumar aryansmit3...@gmail.comwrote: linear decreasing sub sequence problem On Mon, Sep 13, 2010 at 9:10 PM, Raj N rajn...@gmail.com wrote: Given an array of n integers find all the inversion pairs in O(n) Inversion pair is one where a[i]a[j], ij -- 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.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] Google Interview Question-Snake and Ladder Design
Hi, can anyody tell how to approach these types of questions . This was asked in google interview that how would you design a Snake and Ladder Game. Which data will be private and all. If anybody can provide any links to any good tutorial then it would be helpful. -- 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] sql queries
can anybody tell me how to command on sql queries? please refer books and sites where i can practice important queries.! -- 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:Given an array, find out if there exists a pair of nos. that adds up to a sum 'x'
Hi, Given : List l,Sum s --- Sort the Given array Now iterate from beginning... for each element e find if(e s/2) { perform a binary serach. over the remaining elements... } Does it work.. please correct me.. -- 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: Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square
You don't really need a program. Only one number, 9, can be added to 16 to make a perfect square, so 16 must be at one end of the list. Through a sequence of forced choices, you can build the list 16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3. At this point, you can choose either 1 or 6. Trying 1, you can choose either 8 of 15. 8 leads to a dead end -- no unused number can add to 8 giving a perfect square. 15 leads to the continuation 15, 10, 6, but then the only remaining number, 8, doesn't work. Reverting to choosing 6 instead of 1, the sequence continues 6, 10, 15, 1, 8. Thus, the sequence is 16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8. Or its reverse. If you insist on a program, I suppose you could write that sequence in a print statement and give an O(1) solution. Dave On Sep 13, 3:53 pm, bittu shashank7andr...@gmail.com wrote: Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square in O(n) is solution possible in O(logn) Regards Shashank -- 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: Amazon Question
The Final and Finest Answer is select name form product where name like %foo% and len(name)=6 ; length should be the =6 because of constraints ..given that 50% and more foo can occure anywhere in word as footba probability of occurance of foo is 50% byfoot foofoo 100% its wouldn't give result for word fo,fuo,fou etc..i think this is good..xplaination but about word footbal , food,fool .these also similer having foo but don't have len=6 which our contraints right me if i m wrong Regards Shashank -- 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] sql queries
SQL, PL/SQL by Ivan Bayross... It's the best book for learning you may refer that With Thanks Regards, *Prakash Chandra Mishra,* * * * * *~*~ When u think u have reached the end, think again it may be a new beginning.~* ~* On Tue, Sep 14, 2010 at 6:50 AM, Ayush Mittal ayushmittal2...@gmail.comwrote: can anybody tell me how to command on sql queries? please refer books and sites where i can practice important queries.! -- 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.