[algogeeks] COMPRO TECH INTERVIEW
HIII CAN ANY BODY TELL ME WHAT KIND OF PUZZLE ASKED IN COMPRO TECH INTERIVEW AUR WHAT R THE SUBJECT AND KIND OF QUEST. THEY ASKED IN COMPRO CAMPUS INTERVIEW IN DELHI PLZ ANSWER asap THANKS -- 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] Puzzle
3, 39, 41, 43, 45, 49, 51, 53, 55, 64, ?, ?, ... (These are successive numbers sharing a common property. No math or outside knowledge is needed.) -- 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.
[algogeeks] Re: difference b/w static global variables and global variables
In addition to the difference in scope, the standard requires that static variables be initialized to zero by default. Global variables are not required to be initialized by default. Don On Feb 25, 10:51 am, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi , Is there any difference b/w static global variables and global variables ??? (apart from that static variables will be limited to that file only and global variables will be visible for other files also.) Regards, Aman. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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: Pbm with rand() function
For instance, if RANDMAX= 32768, then
x = rand() % 2;
is twice as likely to result in the value 10,000 as the value 15,000.
This is because there are two output values from rand() which result
in x=1 (1 and 3), but only one output value from rand()
resulting in x=15000 (15000).
For any case where the statistical quality of the pseudo-random stream
is important, such as simulation, using the built-in rand() function
is not a good idea. Use a pseudo-random algorithm with much longer
period and better properties, such as Mersenne Twister.
But if you are using rand, it is usually recommended to use the high
order bits rather than the low order bits. Many implementations of
rand() have cycles in the low bits which are much shorter than the
period of the generator. He is one way to generate unbiased values of
quality as good as the generator can provide:
// Return pseudo-random integer in the range 0..n-1
int randRange(int n)
{
int result, div = RANDMAX / n;
do {
result = rand() / div;
} while(result = n);
return result;
}
Don
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
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.
Re: [algogeeks] Re: difference b/w static global variables and global variables
As we all know about data organisation structure in c like stack area,heap area and un intialized data segment so wen uninitialized global variable will be allocated memory in unitialized data segment but static variable ll be local to entire file,initialized to 0 and kept in heap area mostly but if any recursive calls associated with dat particular variable den stack segment is used.. hope it xplains Regards, MOZHI. On Mon, Feb 27, 2012 at 8:46 PM, Don dondod...@gmail.com wrote: In addition to the difference in scope, the standard requires that static variables be initialized to zero by default. Global variables are not required to be initialized by default. Don On Feb 25, 10:51 am, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi , Is there any difference b/w static global variables and global variables ??? (apart from that static variables will be limited to that file only and global variables will be visible for other files also.) Regards, Aman. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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
@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] optimisation
Hi all, We have this challenge to make the fastest executing serial matrix multiplication code. I have tried using matrix transpose( in C for row major ) and loop unrolling.I was able to obtain little speedup. Does anyone have any hints/papers that I could read upon and try to speed up further?I had tried a bit of block tiling but was not successful. Thanks Arun -- 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: difference b/w static global variables and global variables
then how static can be an extern? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Feb 27, 2012 at 10:50 PM, teja bala pawanjalsa.t...@gmail.comwrote: As we all know about data organisation structure in c like stack area,heap area and un intialized data segment so wen uninitialized global variable will be allocated memory in unitialized data segment but static variable ll be local to entire file,initialized to 0 and kept in heap area mostly but if any recursive calls associated with dat particular variable den stack segment is used.. hope it xplains Regards, MOZHI. On Mon, Feb 27, 2012 at 8:46 PM, Don dondod...@gmail.com wrote: In addition to the difference in scope, the standard requires that static variables be initialized to zero by default. Global variables are not required to be initialized by default. Don On Feb 25, 10:51 am, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi , Is there any difference b/w static global variables and global variables ??? (apart from that static variables will be limited to that file only and global variables will be visible for other files also.) Regards, Aman. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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
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.
Re: [algogeeks] optimisation
strassen multiplication , but it may cause overflow On Tue, Feb 28, 2012 at 5:27 AM, Arun Vishwanathan aaron.nar...@gmail.comwrote: Hi all, We have this challenge to make the fastest executing serial matrix multiplication code. I have tried using matrix transpose( in C for row major ) and loop unrolling.I was able to obtain little speedup. Does anyone have any hints/papers that I could read upon and try to speed up further?I had tried a bit of block tiling but was not successful. Thanks Arun -- 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
@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: optimisation
@Arun: I'm assuming that you are optimizing for large matrices. Try making your basic operation a 4x4 matrix multiplication, written out (i.e., without loops), where the 4x4 matrices are subarrays of the operand arrays. This should give you good cache utilization and data reuse, as each element of the two 4x4 operand matrices will be used 4 times. You will have to clean up around the edges if the matrix dimensions are not multiples of 4. Dave On Feb 27, 5:57 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote: Hi all, We have this challenge to make the fastest executing serial matrix multiplication code. I have tried using matrix transpose( in C for row major ) and loop unrolling.I was able to obtain little speedup. Does anyone have any hints/papers that I could read upon and try to speed up further?I had tried a bit of block tiling but was not successful. Thanks Arun -- 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: optimisation
@Arun: The problem with Strassen usually isn't overflow, but instability. The error bounds will be based on the largest element, rather than on each individual element. You won't want to recurse all the way to 1x1 blocks, as the bookkeeping becomes more expensive as recursion depth increases. Dave On Feb 27, 10:12 pm, atul anand atul.87fri...@gmail.com wrote: strassen multiplication , but it may cause overflow On Tue, Feb 28, 2012 at 5:27 AM, Arun Vishwanathan aaron.nar...@gmail.comwrote: Hi all, We have this challenge to make the fastest executing serial matrix multiplication code. I have tried using matrix transpose( in C for row major ) and loop unrolling.I was able to obtain little speedup. Does anyone have any hints/papers that I could read upon and try to speed up further?I had tried a bit of block tiling but was not successful. Thanks Arun -- 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
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.
Re: [algogeeks] Puzzle
66,68,70 On Mon, Feb 27, 2012 at 6:54 PM, karthikeya s karthikeya.a...@gmail.com wrote: 3, 39, 41, 43, 45, 49, 51, 53, 55, 64, ?, ?, ... (These are successive numbers sharing a common property. No math or outside knowledge is needed.) -- 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. -- Srikanth Reddy M (M.Sc Tech.) Information Systems BITS-PILANI -- 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: Pbm with rand() function
i've another doubt. what to do when I need to generate a random long long?
On Mon, Feb 27, 2012 at 9:07 PM, Don dondod...@gmail.com wrote:
For instance, if RANDMAX= 32768, then
x = rand() % 2;
is twice as likely to result in the value 10,000 as the value 15,000.
This is because there are two output values from rand() which result
in x=1 (1 and 3), but only one output value from rand()
resulting in x=15000 (15000).
For any case where the statistical quality of the pseudo-random stream
is important, such as simulation, using the built-in rand() function
is not a good idea. Use a pseudo-random algorithm with much longer
period and better properties, such as Mersenne Twister.
But if you are using rand, it is usually recommended to use the high
order bits rather than the low order bits. Many implementations of
rand() have cycles in the low bits which are much shorter than the
period of the generator. He is one way to generate unbiased values of
quality as good as the generator can provide:
// Return pseudo-random integer in the range 0..n-1
int randRange(int n)
{
int result, div = RANDMAX / n;
do {
result = rand() / div;
} while(result = n);
return result;
}
Don
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
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: Pbm with rand() function
with equal probability
On Tue, Feb 28, 2012 at 5:28 AM, Prakash D cegprak...@gmail.com wrote:
i've another doubt. what to do when I need to generate a random long long?
On Mon, Feb 27, 2012 at 9:07 PM, Don dondod...@gmail.com wrote:
For instance, if RANDMAX= 32768, then
x = rand() % 2;
is twice as likely to result in the value 10,000 as the value 15,000.
This is because there are two output values from rand() which result
in x=1 (1 and 3), but only one output value from rand()
resulting in x=15000 (15000).
For any case where the statistical quality of the pseudo-random stream
is important, such as simulation, using the built-in rand() function
is not a good idea. Use a pseudo-random algorithm with much longer
period and better properties, such as Mersenne Twister.
But if you are using rand, it is usually recommended to use the high
order bits rather than the low order bits. Many implementations of
rand() have cycles in the low bits which are much shorter than the
period of the generator. He is one way to generate unbiased values of
quality as good as the generator can provide:
// Return pseudo-random integer in the range 0..n-1
int randRange(int n)
{
int result, div = RANDMAX / n;
do {
result = rand() / div;
} while(result = n);
return result;
}
Don
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
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] Puzzle
logic ? On Tue, Feb 28, 2012 at 11:16 AM, srikanth reddy malipatel srikk...@gmail.com wrote: 66,68,70 On Mon, Feb 27, 2012 at 6:54 PM, karthikeya s karthikeya.a...@gmail.com wrote: 3, 39, 41, 43, 45, 49, 51, 53, 55, 64, ?, ?, ... (These are successive numbers sharing a common property. No math or outside knowledge is needed.) -- 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. -- Srikanth Reddy M (M.Sc Tech.) Information Systems BITS-PILANI -- 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] Puzzle
I think logic is the difference is 2 2 4 2 2 2 8 so next will be 2 2 2 2 2 16 so ans will be 66 68 70 but first number 3 making some problem -- 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] puzzle
Given a sequance of natural numbers. Find N'th term of this sequence. a1=2, a2=4, a3=11, a4=36, a5=147, a6=778 ... ... ... ... aN. this is a coding quesn and O(n) soln is also welcome... -- 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.
