[algogeeks] call google search from a java program
Hi , I am working on a project where i need to call Google search form a Java servlet program.1 string containing the query is supposed to pass to the Google search engine and results must display through my program .I am also trying to copy the top results and some text(first 2-3 lines what Google display ),url form that result in my data base. Please provide guideline how i should proceed. Thanks to all. -- 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: find duplicate and missing element
Thanks Dave but i want best On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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: ternary numbers
Or directly get the last digits from (-1, 0, 1)
100 = 33 * 3 + 1
33 = 11 * 3 + 0
11 = 4 * 3 + (-1)
4 = 1 * 3 + 1
1 = 0 * 3 + 1
Collect those digits together, we get 11X01_3
On 2010-8-31 23:40, Dave wrote:
352/9 = 39-1/9
= 27 + 9 + 3 + 1/9
= 1*3^3 + 1*3^2 + 1*3^1 + 0*3^0 + 0*3^(-1) + 1*3^(-2)
= 1110.01_3
Another example, where -1 comes into play:
Using ordinary ternary {0,1,2} representation:
100 = 1*3^4 + 0*3^3 + 2*3^2 + 0*3^1 + 1*3^0
= 10201_3{0,1,2}
Now transform into the {0,1,-1} representation by replacing 2 with -1
and adding 1 to the place digit to the left, propagating a carry if
necessary. I.e., if as you add 1 to the digit to the left it becomes
2, then you repeat the transformation on that digit as well. I'll
write 1 bar as X.
= 11X01_3{0,1,-1}
Dave
On Aug 30, 6:46 pm, Raj Nrajn...@gmail.com wrote:
In ternary number representation, numbers are represented as 0,1,-1.
(Here -1 is represented as 1 bar.) How is 352/9 represented in ternary
number 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.
[algogeeks] Amazon intern Question
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find duplicate and missing element
@Raj: Best what? Dave On Sep 1, 12:08 am, Raj Jagvanshi raj.jagvan...@gmail.com wrote: Thanks Dave but i want best On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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 intern Question
HI Arun, This is the edit distance problem which can be solved using DP. Calculate the cost for each product on the fly and return the top products with the least edit cost! On Sep 1, 5:15 pm, Arun yourarunb...@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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find duplicate and missing element
can you explain on your algorithm. Are you using any extra array. On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das dedhriti...@gmail.comwrote: Given a array, A[1..n], do the following. Start from i=1 and try placing each number in its correct position in the array. If the number is already in its correct position, go ahead. if (A[i] == i) , i++ else if the number was already restored to its correct position, then it is a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup = A[i], i++ ; else swap the elements at the current index i and that at A[i]'s correct position in the array. continue this until all numbers are placed in their correct position in the array Finally, A[missing] will be dup. O(n) On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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: call google search from a java program
Google provides many APIs that are fairly well-documented: http://code.google.com/more/ Make sure to read the licence requirements. On Sep 1, 12:42 am, Debajyoti Sarma sarma.debajy...@gmail.com wrote: Hi , I am working on a project where i need to call Google search form a Java servlet program.1 string containing the query is supposed to pass to the Google search engine and results must display through my program .I am also trying to copy the top results and some text(first 2-3 lines what Google display ),url form that result in my data base. Please provide guideline how i should proceed. Thanks to all. -- 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 intern Question
Edit distance is one way to determine similarity. It assumes all differences are typographic. Amazon is probably interested in many other forms of similarity. When someone types audio system in the Amazon search, you want them to see receivers, speakers, tuners, etc. It's very possible this question is designed to see how well you think, not how well you can cite the standard computer science answer. On Sep 1, 9:36 am, jagadish jagadish1...@gmail.com wrote: HI Arun, This is the edit distance problem which can be solved using DP. Calculate the cost for each product on the fly and return the top products with the least edit cost! -- 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] Amazon intern Question
trie On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@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. -- 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] Could anyone explain how this code works?????????!!!!
Simple run-length encoding of a ascii picture.
On 2010-9-1 3:49, Albert wrote:
#includestdio.h
main()
{
int a,b,c;
int count = 1;
for (b=c=10;a=- FIGURE?, UMKC,XYZHello Folks,\
TFy!QJu ROo TNn(ROo)SLq SLq ULo+\
UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\
NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\
HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\
T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\
Hq!WFs XDt! [b+++21]; )
This is the encoding of the picture, each charactor ch 64 (from the
32nd byte, ie. the second row)
represent the length of a sequence of '!' or ' '. (len = ch - 64)
for(; a-- 64 ; )
putchar ( ++c=='Z' ? c = c/ 9:33^b1);
print a sequence of '!' (if b is even) or ' '(if b is odd) with length
(a-64), beginning with sequence of ' ' (b=11),
and alternatively output sequence of '!' and sequence of ' '.
c controls the line wrap by increase from 10 to 90, then rewind to 10
and output a linefeed,
so exactly 80 bytes on each line.
return 0;
}
It just contains two for loop but i cant understand the how it is
working???
help me please.
--
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] Subsequence
U can choose the linear search option for it ,then arrange the it according to the priority of the numbers and so on Sent from my iPod On Aug 25, 2010, at 9:31 PM, Raj N rajn...@gmail.com wrote: @Rahul: Input: 5 4 6 7 3 2 9 8 and if k=3 should the output be 4+6+7=11 ? Is that what you mean by non-decreasing ? On Wed, Aug 25, 2010 at 9:27 PM, Raj N rajn...@gmail.com wrote: @Jaswanth: Your code nowhere checks the non-decreasing sequence On Tue, Aug 24, 2010 at 7:16 PM, Jashwant Raj jashuu...@gmail.com wrote: hope i got d logic right On Tue, Aug 24, 2010 at 9:55 AM, Rahul rv.wi...@gmail.com wrote: How to find out Non-Decreasing subsequence of length k with maximum sum in an array of n integers ? -- 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. -- 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] Amazon intern Question
I guess, you should be using a suffix tree. On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@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. -- Thanks Regards, Chakravarthi. -- 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: call google search from a java program
http://code.google.com/apis/ajaxsearch/web.html It is possible to use this with Java. On Aug 31, 9:42 pm, Debajyoti Sarma sarma.debajy...@gmail.com wrote: Hi , I am working on a project where i need to call Google search form a Java servlet program.1 string containing the query is supposed to pass to the Google search engine and results must display through my program .I am also trying to copy the top results and some text(first 2-3 lines what Google display ),url form that result in my data base. Please provide guideline how i should proceed. Thanks to all. -- 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] Amazon intern Question
I think DS will be somewhere between suffix and trie DS On Wed, Sep 1, 2010 at 9:35 AM, jaladhi dave jaladhi.k.d...@gmail.comwrote: trie On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@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. -- 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, Saurabh -- 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] Amazon intern Question
@Gene, it isn't about related words, its abt matching words! On Wed, Sep 1, 2010 at 8:26 PM, saurabh singh saurabh.n...@gmail.comwrote: I think DS will be somewhere between suffix and trie DS On Wed, Sep 1, 2010 at 9:35 AM, jaladhi dave jaladhi.k.d...@gmail.comwrote: trie On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@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. -- 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, Saurabh -- 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, Chakravarthi. -- 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: Subsequence
Very Nice soln Dhritiman.
The solution to the standard LCS problem only needs O(n^2) time and O(n)
space.
And you have very intelligently solved its variation also in the same time
and space complexity.
I fell this is the correct solution.
Nikhil Jindal
On Tue, Aug 31, 2010 at 2:13 AM, Dhritiman Das dedhriti...@gmail.comwrote:
This is, drawing on the idea of LCS using DP. Think, this works.
Given array A[1..n] and k, fill up two more arrays ,
lcs[j] = max_{i=1 to j-1} lcs[i] , where A[i] = A[j]
maxPrevindex[j] = i , where A[i] is max among all A[i], such that A[i]
= A[j] and i ranging over 1 to j-1
This can be done in O(n^2).
Now compute
maxSum[j] = A[j] if lcs[j] == 1
= A[j]+ maxSum[ maxPrevindex[j] ] otherwise
if( lcs[j] = k for all j )
answer = MAX ( maxSum[j] ) , lcs[j] == k
else
for all j, st. lcs[j] k
move down the maxPrevindex[j] chain k times , to say
j'
update maxSum[j] = maxSum[j] - maxSum[j']
end for
answer = MAX ( maxSum[j] ) , lcs[j] = k
end if
O(n^2) time, O(n) 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.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: find duplicate and missing element
in ur algo i confuse in solving eqn On Wed, Sep 1, 2010 at 6:31 PM, Dave dave_and_da...@juno.com wrote: @Raj: Best what? Dave On Sep 1, 12:08 am, Raj Jagvanshi raj.jagvan...@gmail.com wrote: Thanks Dave but i want best On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: Amazon intern Question
Even if you're only matching words, there are different kinds of similarity. Check out the soundex algorithm, for example. Levenshtein distance. The Hungarian algorithm. What does 50% similarity mean anyway? I know of no accepted meaning. My point is that if you're in an interview situation and you ask intelligent questions about the question you're asked, you are more likely to get the job. At least I would be more likely to give it to you. I've been responsible for hiring quite a few people. On Sep 1, 11:52 am, Chakravarthi Muppalla chakri...@gmail.com wrote: @Gene, it isn't about related words, its abt matching words! On Wed, Sep 1, 2010 at 8:26 PM, saurabh singh saurabh.n...@gmail.comwrote: I think DS will be somewhere between suffix and trie DS On Wed, Sep 1, 2010 at 9:35 AM, jaladhi dave jaladhi.k.d...@gmail.comwrote: trie On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@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. -- 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, Saurabh -- 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, Chakravarthi. -- 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 interview Question (Array yet again!)
Okay. First, you can make the DP more efficient than the one I gave
earlier. You don't need to scan the whole previous column when
calculating costs of decrementing. Rather there are only two
possibilities.
I will add that rahul patil's solution looks correct, but it's
exponential time. DP is better for this problem.
Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing
sequence with the last element being no more than m. And we always
draw m from the set V of values in a.
So here is the new DP:
C(1, m) = max(a[1] - m, 0) // first row only decrement is possible
C(n, m) = min (
a[n] + C(n - 1, m), // delete
(a[n] = m) ? C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement
)
In case you don't follow, the //delete line is saying that we
already know the cost of making everything up to element n-1 non-
decreasing and no more than m. This, by recursive assumption, is just
C(n-1,m). The additional cost of deleting a[n] is a[n].
The //decrement line is similar, but there are 2 cases. If a[n] is
more than m, we must decrement it. The cost here consists of making
everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m).
Plus we have the cost of chopping a[n] down to m, which is a[n]-m.
In the other case, a[n] is m or less. So there's no need to
decrement, but we must get the elements a[1..n-1] to be no more than
a[n]. Again by recursive assumption this cost is C(n-1,a[n]).
Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. The
least cost here is obtained by decrementing the 5 to 1 (cost 4) and
deleting the final 1 (cost 1) for a total cost of 5.
So let's try the algorithm. (You must view this with a fixed font.)
Table of C(n, m) values:
m = 1 3 5
n = 1 : 4 2 0
n = 2 : 4 3* 1*
n = 3 : 4 4 2*
n = 4 : 4 4 3*
n = 5 : 6m 4 4
n = 6 : 6 5* 5*
Here * means C resulted from decrementing and m means that a
decrement was based on the value of m rather than a[n].
We take the answer from C(6,5) = 5.
Implementing this is a little tricky because m values are drawn from
V. You could use a hash table for the m-axis. But it's more
efficient to store V in an array and convert all the values of m in
the DP into indices of V. Because all the indices lie in [ 1 .. |
V| ], we can use simple arrays rather than hash tables to represent
the rows of the table C.
We only need 2 rows at a time, so O(|V|) storage does the job.
For C, we also need to convert all the indices to origin 0.
So here's the final O(n^2) code. I think this is a correct
implementation. If anyone has an example that breaks it, I'd like to
see.
#include stdio.h
#define NMAX 1
int cost(int *a, int N)
{
int i, j, max, Nv;
int V[NMAX], A[NMAX], B[NMAX];
int *Cm = A, *Cn = B; // (n-1)'th and n'th rows of C
// Compute set V with no duplicates.
// Remember where max element is.
Nv = max = 0;
for (i = 0; i N; i++) {
for (j = 0; j Nv; j++)
if (a[i] == V[j])
break;
if (j == Nv) {
V[Nv++] = a[i];
if (V[j] V[max])
max = j;
}
a[i] = j; // Convert a to indices.
}
// Fill in first row of C.
for (i = 0; i Nv; i++)
Cm[i] = (V[a[0]] = V[i]) ? V[a[0]] - V[i] : 0;
// Fill in the rest of the rows of C.
for (i = 1; i N; i++) {
for (j = 0; j Nv; j++) {
int del = Cm[j] + V[a[i]];
int dec = (V[a[i]] = V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j];
Cn[j] = (del dec) ? del : dec;
}
// Swap row buffers so current becomes previous.
int *tmp = Cn; Cn = Cm; Cm = tmp;
}
return Cm[max];
}
int main(void)
{
static int a[] = { 5, 1, 1, 1, 3, 1 };
printf(Min cost = %d\n, cost(a, sizeof a / sizeof a[0]));
return 0;
}
On Aug 30, 9:19 pm, vikash jain vikash.ro...@gmail.com wrote:
@gene ..if u just give an example herethat will make things more
clear...
--
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: find duplicate and missing element
1. First find the sum of all given elements.: sum 2. find the sum of elements in the given range. : sum_1 3. Find the duplicates.: d 4. Missing Number: sum-sum_1+d. http://codepad.org/77Nr9Hay http://codepad.org/77Nr9Hay On Wed, Sep 1, 2010 at 9:50 AM, Raj Jagvanshi raj.jagvan...@gmail.comwrote: in ur algo i confuse in solving eqn On Wed, Sep 1, 2010 at 6:31 PM, Dave dave_and_da...@juno.com wrote: @Raj: Best what? Dave On Sep 1, 12:08 am, Raj Jagvanshi raj.jagvan...@gmail.com wrote: Thanks Dave but i want best On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: find duplicate and missing element
According to me we can apply the equatin method : Let the missing number be y. Let the duplicated no. be x. 1. then find the product of the 1 to 100 and the sum 1 to 100 :A Product would be of the form...1 *2*3x*..y*100 : B Sum : 1+2+3.+x+y.+100 2. find the prduct of array elements : P find the sum of array elemnts : S 3. then A/P = y/x B-S = y-x Now solve the equations -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find duplicate and missing element
@Raj: It is just algebra. Dave On Sep 1, 11:50 am, Raj Jagvanshi raj.jagvan...@gmail.com wrote: in ur algo i confuse in solving eqn On Wed, Sep 1, 2010 at 6:31 PM, Dave dave_and_da...@juno.com wrote: @Raj: Best what? Dave On Sep 1, 12:08 am, Raj Jagvanshi raj.jagvan...@gmail.com wrote: Thanks Dave but i want best On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: find duplicate and missing element
On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das dedhriti...@gmail.comwrote: Given a array, A[1..n], do the following. Start from i=1 and try placing each number in its correct position in the array. If the number is already in its correct position, go ahead. if (A[i] == i) , i++ else if the number was already restored to its correct position, then it is a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup = A[i], i++ ; else swap the elements at the current index i and that at A[i]'s correct position in the array. continue this until all numbers are placed in their correct position in the array Finally, A[missing] will be dup. O(n) *...@dharitiman, good solution man. No expensive computation, no extra memory required. Only problem is it will change the input array to sorted order which may not be desired. * On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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: find duplicate and missing element
@Dinesh, Yes, we can't apply this method, if that's not allowed. On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal bansal...@gmail.com wrote: On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das dedhriti...@gmail.comwrote: Given a array, A[1..n], do the following. Start from i=1 and try placing each number in its correct position in the array. If the number is already in its correct position, go ahead. if (A[i] == i) , i++ else if the number was already restored to its correct position, then it is a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup = A[i], i++ ; else swap the elements at the current index i and that at A[i]'s correct position in the array. continue this until all numbers are placed in their correct position in the array Finally, A[missing] will be dup. O(n) *...@dharitiman, good solution man. No expensive computation, no extra memory required. Only problem is it will change the input array to sorted order which may not be desired. * On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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] Take 5 digit number and find 2 power that number.............
Program that takes a 5 digit number and calculates 2 power that number and prints it and should not use the Big-integer and Exponential Function's. -- 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: Take 5 digit number and find 2 power that number.............
a 5 digit number is of order 10^5 which is 10^16 of which int in C is of size. Just multiply both numbers. On Sep 2, 10:39 am, prasad rao prasadg...@gmail.com wrote: Program that takes a 5 digit number and calculates 2 power that number and prints it and should not use the Big-integer and Exponential Function's. -- 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: Take 5 digit number and find 2 power that number.............
Maybe you misunderstand the question. The question is how to compute 2^X where 0 = X = 9? How? On Wed, Sep 1, 2010 at 10:48 PM, Ruturaj rutura...@gmail.com wrote: a 5 digit number is of order 10^5 which is 10^16 of which int in C is of size. Just multiply both numbers. On Sep 2, 10:39 am, prasad rao prasadg...@gmail.com wrote: Program that takes a 5 digit number and calculates 2 power that number and prints it and should not use the Big-integer and Exponential Function's. -- 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.
