[algogeeks] Re: [Google question]
@vikas I believe that if we generalize the question saying that there are N students and K schools, such that each school can accommodate at max (N/K) students (which means each school needs to accommodate exactly (N/K) students. Given this we need to find the minimum distance. By O(n^3), in this case it means O((N/K ^ 3)) . Am I right ? On 1 Aug, 11:48, vikas rai vikasloves...@gmail.com wrote: There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: [Google question]
@ above small correction.. /* By O(n^3), in this case it means O((N/K ^ K)) . */ Therefore, N = 9, K=3.. hence (9/3)^3 = 27 On Aug 4, 4:24 am, Lucifer sourabhd2...@gmail.com wrote: @vikas I believe that if we generalize the question saying that there are N students and K schools, such that each school can accommodate at max (N/K) students (which means each school needs to accommodate exactly (N/K) students. Given this we need to find the minimum distance. By O(n^3), in this case it means O((N/K ^ 3)) . Am I right ? On 1 Aug, 11:48, vikas rai vikasloves...@gmail.com wrote: There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: [Google question]
What is N? This is a fixed-size problem so by definition, every solution will be constant time. Don On Aug 1, 2:48 am, vikas rai vikasloves...@gmail.com wrote: There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question Invoice -bills
Atul, I think that your approach will work, although it may take a huge amount of time. One way to potentially make it faster is to select the invoices with the smallest number of combinations first. If you first select all of the invoices with exactly one possible combination, this will prevent you from wasting a lot of time considering combinations for other invoices which require those bills. After assigning all of the invoices with exactly one possible combination, you can clear out all combinations for the other invoices which use any of the assigned bills. That might result in more invoices with exactly one possible combination, but it will almost certainly narrow down the options significantly for the rest of the problem. This approach doesn't ensure a faster solution. I could come up with a diabolical input set which would defeat it. But in most cases it should speed things up a lot. Don On Mar 26, 11:32 pm, atul anand atul.87fri...@gmail.com wrote: @ankush: i told one approach above , but may i want clear . i am not saying this is the best approach to do so but it is one naive soln i came up with. so find all possible combination for each invoice and save it in some data structure. now start from 1st invoice and select 1st invoice combination say for invoice 80 = 50 + 30 now search in next invoice(210) combination , if there is any combination for this invoice which does not include 50 and 30 if yes there is one say 210= 10 + 10 +20 + 70 + 100 , we have a hit and do similar with other invoice . every time you move fwd make sure that you should search for combination which does not include any of those bill used in prev finding. if no, then we know that there is no point of moving fwd , so select another combination from prev invoice in this case its 80 and follow same as above. On Mon, Mar 26, 2012 at 5:56 PM, ankush.bago...@gmail.com wrote: ** You can use dp to find subsets . But how is dp used for the overall probkem Sent from BlackBerry® on Airtel -- *From: * atul anand atul.87fri...@gmail.com *Sender: * algogeeks@googlegroups.com *Date: *Mon, 26 Mar 2012 16:52:08 +0530 *To: *algogeeks@googlegroups.com *ReplyTo: * algogeeks@googlegroups.com *Subject: *Re: [algogeeks] Google Question Invoice -bills @umer : dp approach is given in above post. On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote: Well, they have specified in the question that you are dealing with big-data sets. So, recursion won't be a good option I guess. Can we solve it with dynamic programming technique? On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.comwrote: one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find combination for 210. i guess there can be better way to solve this.. On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@googlegroups.com. To unsubscribe
Re: [algogeeks] Re: google question
@Dave : is it a working code?? i have executed your code but getting wrong output...and value of s is becoming -ve inside loops. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: google question
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote:
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left parent's outflow and r is the right parent's.
So you are always computing the h'th row in terms of the (h-1)'th.
For many DPs this means you'll need 2 row buffers. In this one you
only need 1 element back in the current row. You can save this element
in a single variable and get by with one buffer. I.e. note l for a
given value of i is always the previous value of r. And for i=0, l is
always 0 because there is no left parent.
So you end up with
f[0] = L; // fill in the first row
for (ih = 1; ih = h; ih++) { // loop thru rest of rows
double l = 0; // left parent outflow at ii=0 is always 0.
for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii ih f[ii] C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
}
}
return (0 = i i = h) ? f[i] : 0;
This is doing the same as Dave's code for all practical purposes. It's
untested but ought to work.
On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) + G(h - 1, i)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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: google question
Well the OP is not clear. You could be right. I solved this problem
once before, and there the glasses were arranged in a pyramid like
they do at weddings in my country (this will only look right if you
set the fixed-width font in Groups:
U
U U
U U U
U U U U
U U U U U
---
You pour in the wine at the top and each glass trickles down to the 2
below it. So in this version I assumed the OP meant the children were
the ones below and to the right. I could be wrong.
On Feb 28, 8:46 am, Ashish Goel ashg...@gmail.com wrote:
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote:
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left parent's outflow and r is the right parent's.
So you are always computing the h'th row in terms of the (h-1)'th.
For many DPs this means you'll need 2 row buffers. In this one you
only need 1 element back in the current row. You can save this element
in a single variable and get by with one buffer. I.e. note l for a
given value of i is always the previous value of r. And for i=0, l is
always 0 because there is no left parent.
So you end up with
f[0] = L; // fill in the first row
for (ih = 1; ih = h; ih++) { // loop thru rest of rows
double l = 0; // left parent outflow at ii=0 is always 0.
for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii ih f[ii] C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
}
}
return (0 = i i = h) ? f[i] : 0;
This is doing the same as Dave's code for all practical purposes. It's
untested but ought to work.
On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) + G(h - 1, i)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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: google question
The previous proposed solutions all seem far too complicated. It is
not necessary to use a graph data structure. We can simply use an
array to store the quantities of the cups in a row, and update the
array to move to the next row. It would look something like this:
double cupQuan(double L, double C, int h, int i)
// h is the row number of the cup in question, the top cup has h = 1.
// i is the index of the cup in question; the first cup in a row has i
= 0.
{
int j, k;
double r, s;
double* p;
if( (L = 0) || (C = 0) || (h = 0) || (i 0) || (i = h) )
return 0.0;
p = malloc(h * sizeof(double));
p[0] = L;// all liquid into top cup
for( j = 1 ; j h ; ++j )// advance from row j to j+1
{
r = 0.0; // nothing coming in from the
left
for( k = 0 ; k j ; ++k )
{
s = p[k] - C;
if( s = 0.0 )
{// if this cup does not
overflow
p[k] = r; // only overflow from previous
cup
r = 0.0; // no overflow to next cup in
row
}
else
{ // if this cup does
overflow
p[k] = 0.5 * s + r; // overflow from this cup and
previous
r = 0.5 * s; // overflow to next cup in row
}
p[j] = r; // overflow into last cup in
row
}
}
s = p[i] = C ? p[i] : C; // result, but not C
free(p);
return s;
}
Dave
On Feb 25, 5:35 am, Ravi Ranjan ravi.cool2...@gmail.com wrote:
|_|
|_| |_|
|_| |_| |_|
|_| |_| |_| |_|
|_| |_| |_| |_| |_|
Each cup has capacity C and once a cup gets full, it drops half extra
amount to left child and half extra amount to right child
for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
will be divided equally to left and right child cup of next level
i.e. C/2 to left child and C/2 to right child
Write a function which takes input parameter as amount of liquid poured at
top (L) and height of particular cup (h) index of that cup (i) and it
should return amount of liquid absorbed in that cup.
source
http://www.careercup.com/question?id=12770661
whats exactly the qestion???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: google question
Dave, why the assumption that nothing is coming from left side. Every cup gets something from cup left above and right above itself when they have something extra? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote: // nothing coming in from the left -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: google question
@Ashish: I didn't make any assumption that nothing comes from the left. Does my code give the wrong answer? Dave On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote: Dave, why the assumption that nothing is coming from left side. Every cup gets something from cup left above and right above itself when they have something extra? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote: // nothing coming in from the left -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: google question
Dave's code is good. Here is a more abstract way of thinking about
it. Maybe helpful?
Number the rows starting at the top with h=0, and the left i=0. Then
the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When
h0, i0 or i h, the parent does not exist.
Let F(h, i) be the amount that has flowed in to cup(h,i) after L went
in at the top and let G(h, i) be the amount that has flowed out.
So note that what flowed out is either what flowed in minus C or else
nothing if less than C has flowed in. It's also zero if cup(h,i)
doesn't exist:
G(h,i) = { F(h, i) - C if 0 = i = h and F(h, i) C
{ 0 otherwise
Now note that what flows in is equal to half of what flowed out of
each parent unless we have the top cup, which means L flowed in!
F(h, i) = { L if h = i = 0
{ 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) otherwise
The answer we want is given by F. Dave's code is a nice
implementation of this DP.
On Feb 27, 5:23 pm, Dave dave_and_da...@juno.com wrote:
@Ashish: I didn't make any assumption that nothing comes from the
left. Does my code give the wrong answer?
Dave
On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote:
Dave, why the assumption that nothing is coming from left side.
Every cup gets something from cup left above and right above itself when
they have something extra?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote:
// nothing coming in from the
left
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: google question
Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: google question
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
fillCup(root-right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: google question
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.
You'll have to admit that my data structure, an array, is simpler than
your graph.
Dave
On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity); // pour 1/2 to the left
fillCup(root-right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: google question
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left parent's outflow and r is the right parent's.
So you are always computing the h'th row in terms of the (h-1)'th.
For many DPs this means you'll need 2 row buffers. In this one you
only need 1 element back in the current row. You can save this element
in a single variable and get by with one buffer. I.e. note l for a
given value of i is always the previous value of r. And for i=0, l is
always 0 because there is no left parent.
So you end up with
f[0] = L; // fill in the first row
for (ih = 1; ih = h; ih++) { // loop thru rest of rows
double l = 0; // left parent outflow at ii=0 is always 0.
for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii ih f[ii] C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
}
}
return (0 = i i = h) ? f[i] : 0;
This is doing the same as Dave's code for all practical purposes. It's
untested but ought to work.
On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) + G(h - 1, i)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: google question
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.
You'll have to admit that my data structure, an array, is simpler than
your graph.
Dave
On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right
child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled
cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
fillCup(root-right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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: google question
@Gene , @dave : +1 +1
On Tue, Feb 28, 2012 at 10:49 AM, atul anand atul.87fri...@gmail.comwrote:
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.
You'll have to admit that my data structure, an array, is simpler than
your graph.
Dave
On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right
child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled
cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
fillCup(root-right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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: google question
You are assuming is to be a binary tree, its not. Some nodes will
share a common pour.
On Feb 25, 9:24 pm, atul anand atul.87fri...@gmail.com wrote:
i guess this would work...
n=number of nodes
h=height;
pour=quantity poured;
capacity = capacity of each cup
n=pow(2,h+1) -1;
call(capacity,pour,0,n)
node* fillCup(float capacity,float pour,int left,int right)
{
node *root;
int mid;
if(left right)
return NULL;
root=(node *)malloc(sizeof(node));
if(left==right)
{
if(pour =capacity)
root-data=capacity;
else
root-data=pour;
root-left=root-right=NULL;}
else
{
mid=left+(right-left)/2;
if(pour = capacity)
{
root-data=capacity;
pour=pour-capacity;
pour=pour/2;}
else
{
root-data=pour;
root-left=root-right=NULL;
return root;
}
root-left=fillCup(capacity,pour,left,mid-1);
root-right=fillCup(capacity,pour,mid+1,right);
}
return root;
}
On Sat, Feb 25, 2012 at 5:05 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote:
|_|
|_| |_|
|_| |_| |_|
|_| |_| |_| |_|
|_| |_| |_| |_| |_|
Each cup has capacity C and once a cup gets full, it drops half extra
amount to left child and half extra amount to right child
for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
will be divided equally to left and right child cup of next level
i.e. C/2 to left child and C/2 to right child
Write a function which takes input parameter as amount of liquid poured at
top (L) and height of particular cup (h) index of that cup (i) and it
should return amount of liquid absorbed in that cup.
source
http://www.careercup.com/question?id=12770661
whats exactly the qestion???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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: google question
@all same doubt qstn appears to be of binary tree DS but the diagram given in between qstn is not like Binary tree so sharing is there so how sharing is done plz explain?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: google question
@Ravi: checkout this code...i have created tree where there is sharing of
nodes..
here is my code :-
please let me know is case you find any bug.
#includestdio.h
typedef struct tree{
int idx;
float data;
struct tree *left;
struct tree *right;
}node;
node *createNode(int index)
{
node *temp;
temp=(node *)malloc(sizeof(node));
temp-idx=index;
temp-data=0.0;
temp-left=temp-right=NULL;
return temp;
}
void inorder(node *root)
{
if(root!=NULL)
{
inorder(root-left);
printf(%d ) %f \n,root-idx,root-data);
inorder(root-right);
}
}
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0)
{
root-data=capacity;
pour=pour-capacity;
}
else
{
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);
fillCup(root-right,pour/2,capacity);
}
int main()
{
node *root;
float pour,capacity;
root=createNode(1);//1
root-left=createNode(2);//2
root-right=createNode(3);//3
root-left-left=createNode(4);//4
root-left-left-left=createNode(7);//7
root-right-right=createNode(6);//6
root-right-right-right=createNode(10);//10
root-left-right=createNode(5);//5
root-right-left=root-left-right;
root-left-left-right=createNode(8); // 8
root-left-right-left=root-left-left-right;
root-left-right-right=createNode(9);//9
root-right-right-left=root-left-right-right;
printf(\nEnter capacity = );
scanf(%f,capacity);
printf(\nEnter quantity poured = );
scanf(%f,pour);
fillCup(root,pour,capacity);
printf(\nPrinting tree\n\n);
inorder(root);
printf(\n\n);
return 1;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: Google Question--Suggest Algo
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size
of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly
selected
elements from the k subarrays. Basically means that we will
want to
split
the array in such way such that the sum
[algogeeks] Re: Google Question--Suggest Algo
O(N*K)
On Nov 28, 1:04 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size
of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing
[algogeeks] Re: Google Question--Suggest Algo
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
I don't think it is O(N*K)
It is O(N^2)
Just to confirm if i have understood correctly
Lets say n and k are given and are global to all subproblems
Subproblem Definition
F[i,j] - maximum expected sum that we can get by partitioning array from 0
to i into j subarrays. Each subarray satisfies the size bound
[ceiling(n/2k),floor(3n/2k)]
F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
subarray from i-r+1 to i}
So to calculate every subsequent subproblem we need to check solutions to
O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2)
On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution.
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
I don't think it is O(N*K)
It is O(N^2)
Just to confirm if i have understood correctly
Lets say n and k are given and are global to all subproblems
Subproblem Definition
F[i,j] - maximum expected sum that we can get by partitioning array from 0
to i into j subarrays. Each subarray satisfies the size bound
[ceiling(n/2k),floor(3n/2k)]
F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
subarray from i-r+1 to i}
So to calculate every subsequent subproblem we need to check solutions to
O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2)
On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time will be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
I don't think it is O(N*K)
It is O(N^2)
Just to confirm if i have understood correctly
Lets say n and k are given and are global to all subproblems
Subproblem Definition
F[i,j] - maximum expected sum that we can get by partitioning array from 0
to i into j subarrays. Each subarray satisfies the size bound
[ceiling(n/2k),floor(3n/2k)]
F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
subarray from i-r+1 to i}
So to calculate every subsequent subproblem we need to check solutions to
O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2)
On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution.
[algogeeks] Re: Google Question--Suggest Algo
Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source - http://stackoverflow.com/questions/8189334/google-combinatorial-optim... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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: Google Question--Suggest Algo
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote:
You have an array with *n* elements. The elements are either 0 or 1. You
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k n. After you split the array into k subarrays. One element of each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to split
the array in such way such that the sum of all the expected values for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
Source -
http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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: Google Question--Suggest Algo
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the sum of all the expected values
for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
Source -
http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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 algogeeks@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: Google Question--Suggest Algo
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the sum of all the expected values
for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4
Re: [algogeeks] Re: Google Question--Suggest Algo
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly
selected
elements from the k subarrays. Basically means that we will want
to
split
the array in such way such that the sum of all the expected
values
for the
elements selected from each subarray is maximum.
You can assume
Re: [algogeeks] Re: GOOGLE QUESTION
since its a phone number storing problem, you can sort the numbers and store the differences. That way you can generate the required number on the go On Thu, Jun 30, 2011 at 4:39 AM, juver++ avpostni...@gmail.com wrote: @Navneet Please read problem again - it is about memory efficient storing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-hsmsOgm2YUJ. To post to this group, send email to algogeeks@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 algogeeks@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: GOOGLE QUESTION
In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | NULL I hope now you get how it saves a lot memory :) | a- 123454321 On Wed, Jun 29, 2011 at 11:31 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: GOOGLE QUESTION
Sorry for the previous post it got a mistake here take a look again :- In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | a-123454321 | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | a- 123454321 | NULL I hope now you get how it saves a lot memory :) On Thu, Jun 30, 2011 at 12:21 PM, sagar pareek sagarpar...@gmail.comwrote: In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | NULL I hope now you get how it saves a lot memory :) | a- 123454321 On Wed, Jun 29, 2011 at 11:31 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: GOOGLE QUESTION
I wonder why people have discarded the idea of Hash map here. Searching is obviously the most important task here and if we are to assume that names can be uniformly hashed over a table of 1000 rows with each row containing 1000 names each. Further optimization can be achieved by having names stored in binary search tree for each row. (So it will take max 10 comparisons to search a name) (Need to Keep it a balanced tree) So in all, a total of max 11 operations - 1 Hash + 10 comparisons will be used to search for any phone number. In the above, hashing is to be done on names obviously. On Thu, Jun 30, 2011 at 12:24 PM, sagar pareek sagarpar...@gmail.com wrote: Sorry for the previous post it got a mistake here take a look again :- In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | a-123454321 | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | a- 123454321 | NULL I hope now you get how it saves a lot memory :) On Thu, Jun 30, 2011 at 12:21 PM, sagar pareek sagarpar...@gmail.com wrote: In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | NULL I hope now you get how it saves a lot memory :) | a- 123454321 On Wed, Jun 29, 2011 at 11:31 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: GOOGLE QUESTION
@samby You are wrong anyway. Main problem is to reduce memory while storing phone numbers. We have 1 million of phones, they have many common prefixes which can be addressed by trie. For storing names, you may use any data structure which is best for the particular problem. Key is name, and value is a leaf node in trie which represents desired phone number. If one want improve memory usage, they can build ternary trie based on already sorted phones, so it makes it balanced. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/r3vvzArkr1kJ. To post to this group, send email to algogeeks@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: GOOGLE QUESTION
@Navneet Please read problem again - it is about memory efficient storing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-hsmsOgm2YUJ. To post to this group, send email to algogeeks@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: GOOGLE QUESTION
if u have known the answer u would have probably answered rather than writing this thing..:| On Jun 29, 5:40 pm, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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: GOOGLE QUESTION
u r right buddy but problem is to save memory On Jun 29, 7:33 pm, ankit sambyal ankitsamb...@gmail.com wrote: Hey guys, phone usually has comparatively very less memory. So, we can't afford to have pointers for each phone no. So, the idea of having a tree is rooted out. The best way can be to use a fixed array with circular indexing which is sorted by name, because the most frequent query is to search a person by name. Though the addition and deletion are expensive, but these are operations are very rare. On Wed, Jun 29, 2011 at 7:25 AM, rajeev bharshetty rajeevr...@gmail.com wrote: @MONSIEUR Use Binary Search Tree as the data Structure to store the values for the Phone numbers because insertion and deletion is easy plus you will get the additional advantage of sorted list of phone numbers . So Binary search tree is better than using hash data structure . Regards Rajeev N B I Blog @www.opensourcemania.co.cc On Wed, Jun 29, 2011 at 6:27 PM, Anantha Krishnan ananthakrishnan@gmail.com wrote: How we will get phone number of a particular person? Thanks Regards, Anantha Krishnan On Wed, Jun 29, 2011 at 6:22 PM, sudheer kumar chigullapallysudh...@gmail.com wrote: USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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 algogeeks@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 algogeeks@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: GOOGLE QUESTION
trie uses more space On Jun 29, 5:52 pm, sudheer kumar chigullapallysudh...@gmail.com wrote: USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: GOOGLE QUESTION
Please explain why you think TRIE use more space? To my knowledge TRIE says lot of memory as the common numbers are saved only once.. If you have any good reason then please explain and don't make any single line statements. On Wed, Jun 29, 2011 at 9:21 PM, MONSIEUR monsieur@gmail.com wrote: trie uses more space On Jun 29, 5:52 pm, sudheer kumar chigullapallysudh...@gmail.com wrote: USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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: GOOGLE QUESTION
@Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
1,2,43,41,5 , 6 Start at a[3] and a[5] Swap them up . Reversing it , we get 1,2,43,5,6,41 This does not work . On Jun 23, 9:05 pm, Swathi chukka.swa...@gmail.com wrote: We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-Hidequoted 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 algogeeks@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.- 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 algogeeks@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: Google Question
http://anandtechblog.blogspot.com/2011/06/bitonic-merge.html On Fri, Jun 24, 2011 at 2:17 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: 1,2,43,41,5 , 6 Start at a[3] and a[5] Swap them up . Reversing it , we get 1,2,43,5,6,41 This does not work . On Jun 23, 9:05 pm, Swathi chukka.swa...@gmail.com wrote: We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926*-Hidequoted 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 algogeeks@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.- 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 algogeeks@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 algogeeks@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: Google Question
@Anand : Plz explain ur algo ??? On Fri, Jun 24, 2011 at 10:55 AM, Anand anandut2...@gmail.com wrote: http://anandtechblog.blogspot.com/2011/06/bitonic-merge.html On Fri, Jun 24, 2011 at 2:17 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: 1,2,43,41,5 , 6 Start at a[3] and a[5] Swap them up . Reversing it , we get 1,2,43,5,6,41 This does not work . On Jun 23, 9:05 pm, Swathi chukka.swa...@gmail.com wrote: We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-Hidequoted 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 algogeeks@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.- 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 algogeeks@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 algogeeks@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 algogeeks@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: Google Question
@piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-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 algogeeks@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: Google Question
We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-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 algogeeks@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 algogeeks@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: Google Question
@Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*- 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 algogeeks@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: Google Question
I heard somewhere in some online video lecture that sites like tinyurl
change the address using more than base three {base 6 } and then apply
hash
On 6/4/11, bittu shashank7andr...@gmail.com wrote:
well i can speak much on these question.as these algorithms are part
of web crawler ..but do u mean we have to detect the duplicate files,
by file having same size are duplicates..??
also same question raised by me few days back Detecting Duplicate
Documents but no one seems to interested u can search previous
threads..
Thanks
Shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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.
--
Rahul
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: Google Question
@Nate...Both TinyUrl Bit.ly Fails in case of our web address is less then length of their(tinyurl/bit.ly) names.. example if u will try http://www.a.com/a (num of chars 18) in tinyurl.com it will convert http://tinyurl.com/cl3nc4 which 25 chars long surly greater then original url length so these service are not good for small length of urls..its my observation so their purpose to make large url into tiny they are surely either using hash function of base 36(26chars=10 digits) or base 62 chars (26+26+10) in case of case sensitive as A is differ from a or they are using random number generation by converting between 0 to 10. if we need all possible shortest url possible then we can count ascii chars of base 256 or unicode characters. as we know each url is unique in world of internet. every long URL is associated with a unique key, which is the part after http://top-level domain name/mypage.html , for example http://tinyurl.com/m3q2xt has a key of m3q2xt. so basically we have to generate the unique key as shown in example from string after top level domain so hash function obvious choice as urls are unique key will be unique for example www.google.com/abc www.google.com/bac will generate different key thus unique any other approach Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
well i can speak much on these question.as these algorithms are part of web crawler ..but do u mean we have to detect the duplicate files, by file having same size are duplicates..?? also same question raised by me few days back Detecting Duplicate Documents but no one seems to interested u can search previous threads.. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
i also thought its relative to database but ultimately it also depends on the data structure Algorithms used by database to implement the particularly query. The simpler implementation of this service is to store, in a database table, a data pair (id, url) where your id has the autoincrement option, e.g. 1 - www.facebook.com 2 - www.otherurl.com/path/complete/to/the/page.php 3 - ... so on So when a user ask for http://tinyurlservice.com/1 you simply do a select into your table (select url from urlstable where id = '1') and then you do a redirect to that url. You could refine this, looking before if a certain url was already 'tinyurled' (so you prevent multiple insertions of the same url), you could add a date field in your table and delete the older entries with a stored procedure or with a cronjob or with an admin panel... and so on. 1 have another approach using temp. array of all chars that a url can contains will explorer later.. Hope this will be useful for you., Correct me if anything wrong Thanks Shashank CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
Suppose I press As only throughout . We will have the number of As as A*(number of keystrokes) .This is the least we can get provided we play stupidly enough . On Jan 29, 9:16 pm, Saikat Debnath saikat@gmail.com wrote: @ Sankalp : plz explain this line of yours : No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As On Jan 29, 5:32 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
@ Sankalp : plz explain this line of yours : No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As On Jan 29, 5:32 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
Nishant's soln is incorrect because he assumes, ctrlA and ctrlC are pressed
each time ctrlV is pressed.
As saikat has pointed out, this is incorrect.
According to me:
*buff = 0; //keeps track of last ctrlC*
*for each i*
*{*
* dp(i)=max(dp(i-1)+1, 2*dp(i-3), dp(i-1) + buff)*
* if(dp(i)==2*dp(i-3)) { buff = dp(i-3);}*
*}*
@saikat: for n=10, this gives dp(10) = 20 :D
An O(n) soln.
Cheers
Nikhil Jindal
Delhi College of Engineering (DCE),
Delhi.
On Wed, Jan 19, 2011 at 10:05 PM, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote:
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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: Google Question
@ Nikhil sir : I have coded the same solution, but was waiting for its
correctness to be proved... thanx.. :)
On Fri, Jan 28, 2011 at 1:01 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
Nishant's soln is incorrect because he assumes, ctrlA and ctrlC are pressed
each time ctrlV is pressed.
As saikat has pointed out, this is incorrect.
According to me:
*buff = 0; //keeps track of last ctrlC*
*for each i*
*{*
* dp(i)=max(dp(i-1)+1, 2*dp(i-3), dp(i-1) + buff)*
* if(dp(i)==2*dp(i-3)) { buff = dp(i-3);}*
*}*
@saikat: for n=10, this gives dp(10) = 20 :D
An O(n) soln.
Cheers
Nikhil Jindal
Delhi College of Engineering (DCE),
Delhi.
On Wed, Jan 19, 2011 at 10:05 PM, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote:
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Saikat Kumar Debnath
IIIrd year, Computer Science Deptt.,
Delhi Technological University,
(formerly Delhi College of Engineering)
Delhi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: Google Question
Following is the algorithm to ger max number of A's
set n[0] = 0
int get_max(int n)
{
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: Google Question
Following is the algorithm to get max number of A's .
it gives number = 20 for n=10
set buff = 0
call get_max(n)
int get_max(int i)
{
if (i=1 i=3)
{
n[i] = i
m[i] = 'A'
return n[i]
}
else
{
num_A = getmax(i-3);
max= MAX(num_A+3,2*num_A, num_A+3*buff)
n[i] = max
if max == 2*num_A
m[i-2] = ctrl-A , m[i-1]=ctrl-C ,m[i-2] = ctrl-V
buff = num_A
if (max == num_A + 3*buff)
m[i]=m[i-1]=m[i-2]='ctrl-v'
else if (max == num_A + 3)
m[i]=m[i-1]=m[i-2]='A'
return n[i]
}
return
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: Google Question
Following is the algorithm to get max number of A's .
it gives number = 20 for n=10
set buff = 0
call get_max(n)
int get_max(int i)
{
if (i=1 i=3)
{
n[i] = i
m[i] = 'A'
return n[i]
}
else
{
num_A = getmax(i-3);
max= MAX(num_A+3,2*num_A, num_A+3*buff)
n[i] = max
if max == 2*num_A
m[i-2] = ctrl-A , m[i-1]=ctrl-C ,m[i-2] = ctrl-V
buff = num_A
if (max == num_A + 3*buff)
m[i]=m[i-1]=m[i-2]='ctrl-v'
else if (max == num_A + 3)
m[i]=m[i-1]=m[i-2]='A'
return n[i]
}
return
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: Google Question
it will give m=15 for n=10,but actually m=16 On Jan 21, 10:58 am, Preetam Purbia preetam.pur...@gmail.com wrote: Hi, I think this method will work: Possible Number of A's = N/2(1+R) where R=N-(N/2+3) assuming 11/2 = 5 Thanks Preetam On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote: but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. Try this on a notepad. you will only 15A's On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote: According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.com wrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg roups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Preetam Purbiahttp://twitter.com/preetam_purbia -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
//get n;
if(n%3==0)
{
v=6;
pw=(n-3)/3;
}
else if(n%3==1)
{
v=4;
pw=(n-1)/3;
]
else
{
v=5;
pw=(n-2)/3;
}
maxtimes=(v)*pow(2,pw);
sequence is pressing 'A' v times followed by (select+copy+paste=3
operations) pw times which means 3*pw;
total 3*pw+v=n times
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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: Google Question
hope this works :
#includestdio.h
#define MAX(A,B) AB?A:B
#defineMIN(A,B) AB?A:B
int FindMaxA(int n)
{
int i,k,factor,max = 0,cur,prev;
int* arr = new int[n+1];
int p = MIN(n,4);
for( int j = 1;j = p;j++)
arr[j] = j;
for(i=5;i=n;i++)
{
k = i-4;
factor = 2;
prev = 0;
while(k=1)
{
cur = arr[k]*factor;
if( cur max ) //find max among multiples of Arr[k] for k i
max = cur;
if( cur prev )
break; // once the decreasing pattern starts its safe to
break out of loop.
k--;
factor++;
prev = cur;
}
arr[i] = MAX(i,max);
}
int result = arr[n];
delete[] arr;
return result;
}
int main()
{
int n;
scanf(%d,n);
printf(%d\n,FindMaxA(n));
return 0;
}
--
On Fri, Jan 21, 2011 at 11:28 AM, Preetam Purbia
preetam.pur...@gmail.comwrote:
Hi,
I think this method will work
Possible Number of A's = N/2(1+R)
where R=N-(N/2+3)
assuming 11/2 = 5
Thanks
Preetam
On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote:
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
Try this on a notepad. you will only 15A's
On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote:
According to me Nishaanth's solution is incorrect, as let for n =10, your
output : m=16
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d
abhijith200...@gmail.com wrote:
I think its correct.
On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com
wrote:
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above
four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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
Saikat Kumar Debnath
IIIrd year, Computer Science Deptt.,
Delhi Technological University,
(formerly Delhi College of Engineering)
Delhi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
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 algogeeks@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.
--
Preetam Purbia
http://twitter.com/preetam_purbia
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
[algogeeks] Re: Google Question
I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.comwrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. Try this on a notepad. you will only 15A's On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote: According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.com wrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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: Google Question
Hi, I think this method will work: Possible Number of A's = N/2(1+R) where R=N-(N/2+3) assuming 11/2 = 5 Thanks Preetam On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote: but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. Try this on a notepad. you will only 15A's On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote: According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.com wrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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 algogeeks@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. -- Preetam Purbia http://twitter.com/preetam_purbia -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
Keys 23 may be combined, cause there is no sense to use them separately. It's cost of pressing is 2, however. For all other keys the cost is 1 though. DP[i][n] - maximum number of A's we can produce with cost of pressings = i and we have string of A's with size n in a clipboard. DP[N][any] - result. There are -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question
How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. 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: Google Question: Find kth largest of sum of elements in 2 array
this will not work out
a[0]b[0] doesn't mean that a[0]+b[i] is ith largest sum
try
int a[]={10,8,6,4,1};
int b[]={9,6,3,2,1};
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Oct 6, 2010 at 11:36 PM, ligerdave david.c...@gmail.com wrote:
use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the pointers. therefore, the worst case is either
O(m) when length of m is shorter or O(n) when length of n is
shorter,
make the pointers pointing to the first elements in both arrays.
A)
4,3,2,2,1
^
B)
5,3,2,1
^
compare them to find out which one is larger, here 5 is larger than 4.
by definition, you know 5 would be bigger than any elements in array
A, and sum of 5 with kth element of array A (here, kth = A.length)
will be the one(kth largest sum(a+b) overall) you are looking for.
if kA.length, shift the pointer of B one number to the right and
repeat the same process.
like i said, if the k m*n/2, start from small
On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote:
you are given 2 arrays sorted in decreasing order of size m and n
respectively.
Input: a number k = m*n and = 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
The Brute force approach will take O(n*n). can anyone find a better
logic. thnkx in advance.
--
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: Google Question
http://coders-stop.blogspot.com/2010/12/most-used-data.html On Jan 7, 5:24 pm, bittu shashank7andr...@gmail.com wrote: You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. Thanks 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: Google Question: Find kth largest of sum of elements in 2 array
@sourav I think the best way to explain my logic is to draw a 2D matrix 5 4 2 1 6 5 4 2 then you would find the patten. i have something draw on the paper. if you need, i guess i can scan and send it out On Oct 7, 10:05 am, sourav souravs...@gmail.com wrote: @lingerdave If you get the larget element from the 2 arrays A - 5, 4, 2, 1 B - 6, 5, 4, 2, say 6, do not underestimate the next element in A. The difference between the first two elements in A may be less and 2nd element in A may be string enough to make itself plus an element in B greater than first element in A plus kth element in B. More so if elements in B are very small after first few. for example see example A- 100, 99, B- 50,9,2,1,1 Here A[i] + B[1} is largest but A[2]+B[1] is much larger than A[2]+B[2]. Sourav On Oct 7, 6:22 pm, ligerdave david.c...@gmail.com wrote: @ Ercan, yes, you were right. i forgot about that. anyway, that's the idea. you would need to move pointers on both, depends on which is bigger. for loop w/ i=k, when the loop stops, you have the pointers pointing at the numbers you wanted On Oct 6, 7:16 pm, Gönenç Ercan gon...@gmail.com wrote: A - 5, 4, 2, 1 B - 6, 5, 4, 2, 1 k = 3, ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the algorithm below give 8 (a=2, b=6)? On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote: use pointers and lengths of two arrays. depends on what K is, if K m*n/2, you reverse the pointers. therefore, the worst case is either O(m) when length of m is shorter or O(n) when length of n is shorter, make the pointers pointing to the first elements in both arrays. A) 4,3,2,2,1 ^ B) 5,3,2,1 ^ compare them to find out which one is larger, here 5 is larger than 4. by definition, you know 5 would be bigger than any elements in array A, and sum of 5 with kth element of array A (here, kth = A.length) will be the one(kth largest sum(a+b) overall) you are looking for. if kA.length, shift the pointer of B one number to the right and repeat the same process. like i said, if the k m*n/2, start from small On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote: you are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k = m*n and = 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance. -- 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: Google Question: Find kth largest of sum of elements in 2 array
@ Ercan, yes, you were right. i forgot about that. anyway, that's the idea. you would need to move pointers on both, depends on which is bigger. for loop w/ i=k, when the loop stops, you have the pointers pointing at the numbers you wanted On Oct 6, 7:16 pm, Gönenç Ercan gon...@gmail.com wrote: A - 5, 4, 2, 1 B - 6, 5, 4, 2, 1 k = 3, ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the algorithm below give 8 (a=2, b=6)? On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote: use pointers and lengths of two arrays. depends on what K is, if K m*n/2, you reverse the pointers. therefore, the worst case is either O(m) when length of m is shorter or O(n) when length of n is shorter, make the pointers pointing to the first elements in both arrays. A) 4,3,2,2,1 ^ B) 5,3,2,1 ^ compare them to find out which one is larger, here 5 is larger than 4. by definition, you know 5 would be bigger than any elements in array A, and sum of 5 with kth element of array A (here, kth = A.length) will be the one(kth largest sum(a+b) overall) you are looking for. if kA.length, shift the pointer of B one number to the right and repeat the same process. like i said, if the k m*n/2, start from small On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote: you are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k = m*n and = 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance. -- 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: Google Question: Find kth largest of sum of elements in 2 array
A - 5, 4, 2, 1 B - 6, 5, 4, 2, M - 6,b,5,a,5,b,4,a,4,a,2,a,2,a,1,a x=6b, find the index of B[1]=5 in A, which is 0. so 1 big number. k=1 x=5a, find the index of A[1]=4 in B, which is 3. so there are 2 more, k=3 . . . In the case if k=2 is asked, we know that k=2 can be found when a=5, then simply find the the first largest pair to get the 3rd. if you find the index by binary search then its logn or logm to search, doing it for n numbers i A takes mlogn, and for B it is nlogm. I hope it helps to get the main idea, there are details I am avoiding. (don't want to waste too much time on this) On Oct 7, 5:07 pm, sourav souravs...@gmail.com wrote: @Ercan I am not clear about your approach. It is clear than you are creating a single list of numbers which is a merge of numbers from both array such that final list / array is also decreasing. This can be done in O(m+n). But what after that? Will be great if you can give some more detail. Thanks Sourav On Oct 7, 5:30 am, Gönenç Ercan gon...@gmail.com wrote: merge the A and B in a queue in sorted order. find the following number (next in original array a_i+1) of the largest number (next in queue a_i) execute binary search in the other array (B), the index returned from binary search (even if its not in the array) gives the number of sums greater than the next greatest in A, a_i+1. so; we know the number of pairs; (a_i , b_j) where b_j a_i+1 if you know one of the numbers then the other can be found easily. I think this is O(nlogm + mlogn) On Oct 7, 2:16 am, Gönenç Ercan gon...@gmail.com wrote: A - 5, 4, 2, 1 B - 6, 5, 4, 2, 1 k = 3, ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the algorithm below give 8 (a=2, b=6)? On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote: use pointers and lengths of two arrays. depends on what K is, if K m*n/2, you reverse the pointers. therefore, the worst case is either O(m) when length of m is shorter or O(n) when length of n is shorter, make the pointers pointing to the first elements in both arrays. A) 4,3,2,2,1 ^ B) 5,3,2,1 ^ compare them to find out which one is larger, here 5 is larger than 4. by definition, you know 5 would be bigger than any elements in array A, and sum of 5 with kth element of array A (here, kth = A.length) will be the one(kth largest sum(a+b) overall) you are looking for. if kA.length, shift the pointer of B one number to the right and repeat the same process. like i said, if the k m*n/2, start from small On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote: you are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k = m*n and = 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance. -- 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: Google Question: Find kth largest of sum of elements in 2 array
use pointers and lengths of two arrays. depends on what K is, if K m*n/2, you reverse the pointers. therefore, the worst case is either O(m) when length of m is shorter or O(n) when length of n is shorter, make the pointers pointing to the first elements in both arrays. A) 4,3,2,2,1 ^ B) 5,3,2,1 ^ compare them to find out which one is larger, here 5 is larger than 4. by definition, you know 5 would be bigger than any elements in array A, and sum of 5 with kth element of array A (here, kth = A.length) will be the one(kth largest sum(a+b) overall) you are looking for. if kA.length, shift the pointer of B one number to the right and repeat the same process. like i said, if the k m*n/2, start from small On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote: you are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k = m*n and = 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance. -- 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: Google Question: Find kth largest of sum of elements in 2 array
A - 5, 4, 2, 1 B - 6, 5, 4, 2, 1 k = 3, ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the algorithm below give 8 (a=2, b=6)? On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote: use pointers and lengths of two arrays. depends on what K is, if K m*n/2, you reverse the pointers. therefore, the worst case is either O(m) when length of m is shorter or O(n) when length of n is shorter, make the pointers pointing to the first elements in both arrays. A) 4,3,2,2,1 ^ B) 5,3,2,1 ^ compare them to find out which one is larger, here 5 is larger than 4. by definition, you know 5 would be bigger than any elements in array A, and sum of 5 with kth element of array A (here, kth = A.length) will be the one(kth largest sum(a+b) overall) you are looking for. if kA.length, shift the pointer of B one number to the right and repeat the same process. like i said, if the k m*n/2, start from small On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote: you are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k = m*n and = 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance. -- 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.
