Re: [algogeeks] Facebook Intern F2F Interview
Generate a random number from 1 to 100.
If it is less than or equal to x, return true, else return false.
This will ensure that ur returning true with x/100 probability.
Cheers
Nikhil Jindal
On Thu, Jul 28, 2011 at 4:21 PM, KK kunalkapadi...@gmail.com wrote:
bool foo(int x)
// Implement this function where 0 = x = 100
It should return true x% of times n false otherwise
first i told him to have a static int s then increment it each time
the func is called...
and if s % (100 - x ) == 0 then true else false.
then he told me to have some different approach..
I told him like this:
bool foo(int x)
{
// checking if x is btw 0 100
if(x == 0)
return false;
if(x == 100)
return true;
srand(time(0));
int rno = rand();
if(rno % (100 - x) == 0)
return True;
else
return False;
}
He was like okk but i think he was not completely satisfied
Any other Approach...
--
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] Google Interview Question
Anshu here has given a Perfect soln!
Sunny's code is also correct but is a bit less efficient than anshu's.
Cheers
Nikhil Jindal
http://sites.google.com/site/aboutnikhiljindal/
On Fri, May 27, 2011 at 9:11 PM, anshu mishra anshumishra6...@gmail.comwrote:
@all go through this code
#includeiostream
#includealgorithm
using namespace std;
bool compare(int a, int b)
{
string u, v;
u = v = ;
while (a)
{
u += (a % 10 + '0');
a/=10;
}
while (b)
{
v += (b % 10 + '0');
b/=10;
}
int i = 0, j = 0;
reverse(u.begin(), u.end());
reverse(v.begin(), v.end());
while (i u.size() || j v.size())
{
if (i == u.size()) i = 0;
if (j == v.size()) j = 0;
for (; i u.size() j v.size(); i++, j++)
{
if (u[i] == v[j]) continue;
return (u[i] v[j]);
}
}
if (u.size() == v.size()) return true;
}
int main()
{
int n;
cin n;
int ar[n];
int i;
for (i = 0; i n; i++)
{
cin ar[i];
}
sort (ar, ar +n, compare);
for (i = 0; i n; i++) cout ar[i];
cout endl;
return 0;
}
--
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] Google Interview Question
@Bhavesh:
Counter case for you:
array = {68, 6867}
u change this array to: {6866, 6867}
then u sort them to get 6867, 6866 and then give the ans as: 686768. While
the correct ans is: 686867
The problem in ur algo is in appending the first digit at the end of each
number. For a correct algo, not just the first digit but the complete number
should be appended.
Hence, to get correct result, you should change the array to : {6868, 6867}.
Hope this makes things clear for you.
Cheers
Nikhil Jindal
http://sites.google.com/site/aboutnikhiljindal/
On Mon, May 30, 2011 at 3:28 PM, Bhavesh agrawal agr.bhav...@gmail.comwrote:
solution may be
array ={ 3 ,21 ,9 ,93,17 ,178 ,1,101} (i think i have covered all
exceptions )
then ,change this array like 3 , 21222, 9, 93999, 17111, 17811,
1 , 10111 ( make each number of 5 digit with rest digits same as Ist
digit )
then sort this array
9, 93999,3 21222, 17811,17111, 1, 10111
and make it with actual numbers
9,93,3,21,178,17,1,101= 993321178171101
plz let me know if any case 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.
--
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] Google Interview Question
@Naveen: Here's a counter case: 162, 16 The next digit(2) is not greater than the last equal digit(6), still 162 comes before 16. Here, as is done in ashu's algo, the next digit (2) should be compared with first digit(1) and not the last equal digit(6). Cheers Nikhil Jindal http://sites.google.com/site/aboutnikhiljindal/ On Mon, May 30, 2011 at 12:43 PM, Naveen Agrawal nav.coo...@gmail.comwrote: @ shubham Your solution need some changes at step 2 step 1: sort the given numbers in the decreasing order based on their first digit(left most). step 2: if two numbers come out to be equal in the above case both of their next digit exist then sort on the basis of their next digit, otherwise, the number whose next digit *is greater than last equal digit will come first.(i.e, n=10 m=108 ,as next digit(n-0,m-8) is greater than last equal digit(0), so 108 will come first ) * Naveen -- 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: Facebook Interview Question....Heavy Number
Ok. Here's a possible O(n) solution.
Assuming last digit of a is 0.
for(n=a;n=b;n+=10)
{
Calculate the sum of digits, leaving the last digit.
Find the minimum value of last digit for it to be a heavy number.
Increment count by 10-that number.
}
So here, complexity will be: O(n/10*(d-1))
where, d is the number of digits in the number, which is always less than
10.
So it'll be O(n).
On Tue, Apr 5, 2011 at 3:10 PM, bittu shashank7andr...@gmail.com wrote:
@all , Nikhi Jindal ,.as i already told that O(n^2) Solution is
Obvious ..but .it wont work for 1Biillion as a time
limit exceeds , memory Error occur, so its not a good solution ..I
think There is DP Solution Exist For Thats We Need to Figure it Out to
resolve this problem
@anand what r u trying to do bro...elaborate something more
let me know if still have confusion ??
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.
--
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] Crazy Question, Wants Creative Answer
- Check whether only the screen has gone blank or the sound is gone as well. - Check by changing the channel. - Check if other applianes are working or the electricity is gone. - Check the TV power connection. - I'll wait for some time, if only this channel has gone blank. Nikhil Jindal https://sites.google.com/site/aboutnikhiljindal/ On Tue, Mar 15, 2011 at 4:17 PM, bittu shashank7andr...@gmail.com wrote: U r watching an i cricket match.Suddenly the tv goes blank. Write the steps u ll take to find the fault purpose of this question is not to spamming but to taste how creative , innovative crazy one can think well what i found 1) See if some remote button is pressed by someone 2) Check the cable connectors 3) whats about amplifier if installed by operator in house 4) Check with your neighbors if there connection is also not working 5) Else notify the the operator i wants to see from all algogeeks what they think about this Q.. 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 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. 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] SPoj maximum sum subseuence
Hey Ankur,
Why dont u just modify the findx function itself to return the frequency of
occurence of maxsum as well.
On Sun, Mar 13, 2011 at 12:26 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
https://www.spoj.pl/problems/MAXSUMSQ/
Hi in above problem , i am getting TLE but according to given contraints ,
i think my code is good enough to run. Can any body help me here
#include vector
#include map
#include algorithm
#include cstring
#include iostream
#include cstdio
#include cmath
#include cstdlib
#include climits
#define VI vector int
typedef long long int LL;
using namespace std;
VI v;
LL x,nos;
//finding maximum sum subsequence
LL findx()
{
int sz=v.size();
LL maxsum=INT_MIN;
int maxstart=0,maxend=0;
LL currentsum=0;
int currentstart=0,currentend=0;
int freq=0;
for(currentend=0;currentendsz;currentend++)
{
currentsum=currentsum+v[currentend];
if(currentsum==maxsum) {
freq++;
}
if(currentsummaxsum)
{
maxsum=currentsum;
maxstart=currentstart;
maxend=currentend;
freq=0;
}
if(currentsum0)
{
currentstart=currentend+1;
currentsum=0;
}
}
return maxsum;
}
// main Program
int main()
{
// freopen(input.txt,r,stdin);
int test;
int num;
map LL , LL m;
cintest;
LL sum=0;
int n;
int i;
while(test--)
{
sum=0;
nos=0;
m.clear();
m[0]=1;
scanf(%d,n);
v.resize(n);
for(i=0;in;i++)
{
scanf(%d,v[i]);
}
x=findx();
nos=0;
//Remove this for loop. No need.
for(i=0;in;i++)
{
sum=sum+v[i];
nos=nos+m[sum-x];
m[sum]++;
}
coutx nosendl;
}
return 0;
}
--
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.
This shld help.
Cheers
Nikhil Jindal
https://sites.google.com/site/aboutnikhiljindal/
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] [brain teaser ] 28february
He tells the truth on tuesday. First day is sunday. Nice question. Took me some time to get it right. On Mon, Feb 28, 2011 at 6:47 PM, nidhi jain nidhi.jain311...@gmail.comwrote: Sunday,Saturday -- 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. 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] Puzzle For Puzzled Minds - Robots
Same prog for both the robots: *Label1 : Go left* * Skip next if oil in my path* * Go to Label1* *Label2 : Go left* * Go left* * Go to Label2* Both robots go left with speed one move per 3 second. After one of them finds an oil spot in its way, it doubles its speed to 2 moves per 3 second. Hence, eventually both the robots will clash. Cheers Nikhil Jindal http://www.fundoonick.blogspot.com/ On Thu, Feb 17, 2011 at 12:23 AM, bittu shashank7andr...@gmail.com wrote: Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points. You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions: * Go left one space * Go right one space * Skip the next instruction if there is oil in my current spot * Go to a label [Note that a label is a name that refers to a line of your code. For example, you could label the third line of your program surveying. Then, the instruction goto surveying would jump to line 3 and start executing from there on the next cycle.] A robot will carry out one instruction per second. Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right. 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. 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:
First Question: Nt sure but shldnt t1 be greater than t2? Second: Since, Q is a subset of P. P intersection Q would be Q itself. Would be great if you can share some more questions On Mon, Feb 14, 2011 at 7:52 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: First question mode switch time context switch time . t1t2 Second Question P intersection Q is always regular (proof is beyond the scope of mortals :P) . fourth Question :- D , it is not supported by plain html text . We can do this only by java script or something . Embed objects -- we have embed tag refresh - we have meta tag automatically redirect -- again meta tag Display client time -- javascript or ajax (Alert(some function )) Third :- It uses DP , also in a bottom up fashion . -- 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. h2Brought to you by Team DWD - Visit a href=http://ruhshe.dce.edu; RUHSHE'/a/h2 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] Delightfully Puzzle
The puzzle has recently been discussed in another thread. On Fri, Feb 4, 2011 at 2:20 PM, bittu shashank7andr...@gmail.com wrote: A blind man is handed a deck of 52 cards and told that exactly 10 of these cards are facing up. How can he divide the cards into two piles, not necessarily of equal size, with each pile having the same number of cards facing up? Solution I need Some Discussion on this.. 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.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
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] Modular Arithmetic
(a/b)mod m = (amodm)*(Bmodm) where B is the multiplicative inverse of b i.e (b*B)modM = 1 or B = 1/b Look into the wiki page of Multiplicative inverse for more. Hope this helps Cheers Nikhil Jindal On Wed, Jan 12, 2011 at 7:06 AM, mittal mohitm.1...@gmail.com wrote: Somehelp with (a/b)modm expression. http://en.wikipedia.org/wiki/Modular_arithmetic i visited this link but found only for addition,subtraction and multiplication. -- 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: Modular Arithmetic
On Thu, Jan 13, 2011 at 12:06 AM, Aviral Gupta aviral@gmail.com wrote: we can do it when hcf(b,m)=1 , in that case find inverse of b by extended euclidean mod m and then multiply it by a Yes. And when m is prime, B(mulitplicative inverse of b) = b^(m-2) As b^(m-1)mod m = 1 if m is prime. Regards Aviral http://coders-stop.blogspot.com/ On Jan 12, 6:36 am, mittal mohitm.1...@gmail.com wrote: Somehelp with (a/b)modm expression. http://en.wikipedia.org/wiki/Modular_arithmetic i visited this link but found only for addition,subtraction and multiplication. -- 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: Amazon Analytical Puzzle
Cut each slice into 8 equal pieces. Total 24 pieces. One part consists of 3 pieces. Total 8 parts. On Wed, Jan 12, 2011 at 6:14 PM, bittu shashank7andr...@gmail.com wrote: 2nd puzzle You have a birthday cake and have exactly 3 slices to cut it into 8 equal pieces. How do you do 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 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.
[algogeeks] Number of ways for generating n pairs of valid parenthesis
Try this: Find the number of ways for generating n pairs of valid parenthesis. A set of parenthesis is said to be valid if at any instant while scanning from left to right, the number of opening parenthesis are never less than the number of closing parenthesis. For ex: for n=3, f(n) = 5 ()()(), ((())), (()()), ()(()), (())() Cheers Nikhil Jindal Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] search a 2d sorted array in less than O(n)
On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote: solution 1: use concept of quad-tree and do binary search in that tree solution 2: do binary search on major diagonal. ultimately u will narrow down to search for element in 2 rows. in these two rows again do binary search. How do you narrow down to two rows? Please explain. By searching on the diagonal, you get two elements such that one is lesser than the number being searched for and the next is greater. let them be i,i, and i+1,i+1. So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But the number could be anywhere in the rest of the array any solution will lead you to O(log(n)) time On Tue, Sep 21, 2010 at 5:10 PM, jagadish jagadish1...@gmail.com wrote: Hi all, Given a 2d array which is sorted row wise and column wise as well, find a specific element in it in LESS THAN O(n). PS: an O(n) solution would involve skipping a column or a row each time from the search and moving accordingly. Solution less than O(n) is desirable! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] search a 2d sorted array in less than O(n)
Here's an O(n) soln: Start from the bottom right corner. Move up within the last column until you reach an element such that the element before that is less than the value being searched and this is greater. Now move left and check for the same. Move one more left. The value can only be in the present column after(below) the element we are on. At max, 3n moves = O(n). On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote: solution 1: use concept of quad-tree and do binary search in that tree solution 2: do binary search on major diagonal. ultimately u will narrow down to search for element in 2 rows. in these two rows again do binary search. How do you narrow down to two rows? Please explain. By searching on the diagonal, you get two elements such that one is lesser than the number being searched for and the next is greater. let them be i,i, and i+1,i+1. So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But the number could be anywhere in the rest of the array any solution will lead you to O(log(n)) time On Tue, Sep 21, 2010 at 5:10 PM, jagadish jagadish1...@gmail.com wrote: Hi all, Given a 2d array which is sorted row wise and column wise as well, find a specific element in it in LESS THAN O(n). PS: an O(n) solution would involve skipping a column or a row each time from the search and moving accordingly. Solution less than O(n) is desirable! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] search a 2d sorted array in less than O(n)
Sorry the last solution wont work.
Here's the correct O(n) soln:
Start from top-right element.
If it is greater than the item, go left.
Else go down.
Keep on doing this until you find the element or can not go left or down
(then the element is not in the array).
void 2dsearch(int i, int j, int item)
{
if (i0 || j0 || in-1 || jn-1)
{
printf(Not Found\n);
return;
}
if( a[i][j] == item) printf(Found: %d %d\n, i, j);
elseif( a[i][j] item) 2dsearch(i, j-1, item);
else 2dsearch(i+1, j, item);
}
Call this function as 2dsearch(0, n-1, item);
Cheers
Nikhil Jindal
Delhi College of Engineering
On Sun, Sep 26, 2010 at 8:06 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
Here's an O(n) soln:
Start from the bottom right corner. Move up within the last column until
you reach an element such that the element before that is less than the
value being searched and this is greater.
Now move left and check for the same.
Move one more left. The value can only be in the present column
after(below) the element we are on.
At max, 3n moves = O(n).
On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote:
solution 1:
use concept of quad-tree and do binary search in that tree
solution 2:
do binary search on major diagonal. ultimately u will narrow down to
search for element in 2 rows. in these two rows again do binary search.
How do you narrow down to two rows? Please explain.
By searching on the diagonal, you get two elements such that one is lesser
than the number being searched for and the next is greater. let them be i,i,
and i+1,i+1.
So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But
the number could be anywhere in the rest of the array
any solution will lead you to O(log(n)) time
On Tue, Sep 21, 2010 at 5:10 PM, jagadish jagadish1...@gmail.comwrote:
Hi all,
Given a 2d array which is sorted row wise and column wise as well,
find a specific element in it in LESS THAN O(n).
PS: an O(n) solution would involve skipping a column or a row each
time from the search and moving accordingly.
Solution less than O(n) is desirable!
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
Saurabh
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Adobe Question
The answer would be:
(log1+1) + (log2+1) + (log3+1) + (log4+1) + ... + (log(n-1)+1)
which is equal to:
(log1+log2+log3+...+log(n-1)) + (n-1)
== *log((n-1)!) + (n-1)*
where, log everywhere is assumed to be in base 2
*This according to me will be the final answer!*
*
*
*Cheers*
*Nikhil Jindal
*
On Fri, Sep 24, 2010 at 8:10 PM, SVIX saivivekh.swaminat...@gmail.comwrote:
what's the datatype of j? mathematically speaking, the while loop is
infinite for every j0...
On Sep 23, 6:19 am, Krunal Modi krunalam...@gmail.com wrote:
for(k=1 ; kn ; k++){
j=k;
while(j0){
j=j/2;
}
}
How many times while loop gets executed (for any n) ?
I don't want answer in terms of series (i.e, don't want any sigma, I
have that)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Yahoo Question
@vikas: Total number of elements are not n*k. Total number of elements are n, which are divided into k lists. @Rahul Singal: +1 for ur answer. On Fri, Sep 17, 2010 at 12:58 PM, vikas kumar vikas.kumar...@gmail.comwrote: @Bittu I am confused about one point you need to process atleast n*k elements so how will you do it in nlogk time. It seems really tricky if possible.it's min time should be O(nk). correct me if I am wrong. On Sep 17, 6:34 am, tkcn tkcna...@gmail.com wrote: Use k-way merging +1. 1. Before the merging start, sorting these lists according to the first element of each list. // O(k log k) 2. So the first element in the first list is the smallest element. Put the smallest into the result array. // O(1) 3. Then, using binary search to find the new position of the first list // O(k) 4. These lists are still sorted, so the first element in the first list is still smallest. Just repeat the step 2, 3 n times. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question
Keep an augmented balanced BST. Augmented data: number of elements in the
right and left subtrees .
Insertion: logn
Find Median: logn
Cheers
Nikhil Jindal
Delhi College of Engineering
On Fri, Sep 17, 2010 at 12:09 PM, vikas kumar vikas.kumar...@gmail.comwrote:
struct list
{
median -- median from the start to num
number ---number
list *next
};
during insertion : insert in sorted LL
after that all subseq node's median has to be modified
O(n)
during median_retriev
check the median value and return that
O(1)
I assumed deletion is not happening. if supported , can be done in
O(n)
On Sep 15, 8:24 pm, bittu shashank7andr...@gmail.com wrote:
Propose a data structure that would store numbers, without any
knowledge about them, and allow to perform the operations: insert, get
median, as efficiently as possible same as before, only this time the
numbers are from a group V, which is |V|n
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Subsequence
Very Nice soln Dhritiman.
The solution to the standard LCS problem only needs O(n^2) time and O(n)
space.
And you have very intelligently solved its variation also in the same time
and space complexity.
I fell this is the correct solution.
Nikhil Jindal
On Tue, Aug 31, 2010 at 2:13 AM, Dhritiman Das dedhriti...@gmail.comwrote:
This is, drawing on the idea of LCS using DP. Think, this works.
Given array A[1..n] and k, fill up two more arrays ,
lcs[j] = max_{i=1 to j-1} lcs[i] , where A[i] = A[j]
maxPrevindex[j] = i , where A[i] is max among all A[i], such that A[i]
= A[j] and i ranging over 1 to j-1
This can be done in O(n^2).
Now compute
maxSum[j] = A[j] if lcs[j] == 1
= A[j]+ maxSum[ maxPrevindex[j] ] otherwise
if( lcs[j] = k for all j )
answer = MAX ( maxSum[j] ) , lcs[j] == k
else
for all j, st. lcs[j] k
move down the maxPrevindex[j] chain k times , to say
j'
update maxSum[j] = maxSum[j] - maxSum[j']
end for
answer = MAX ( maxSum[j] ) , lcs[j] = k
end if
O(n^2) time, O(n) space
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Sorting when n-√n numbers are already sorted
@Wan: Storing the elements as link list rather than array requires additional space. If we are taking extra O(n) space, then the usual approach of merging two sorted arrays in O(n) time and memory will suffice. On Fri, Aug 27, 2010 at 5:18 PM, Yan Wang wangyanadam1...@gmail.com wrote: Also, you can choose not to use a tree here. Just sort the remaining √n elements first, then insert these √n elements sequentially into the n-√n elements' array. The essential here is to store all these elements in a linked list rather than an array, because using an array the program always needs to do a lot of element shifting manipulations which is a time-consuming thing. On Fri, Aug 27, 2010 at 4:40 AM, Yan Wang wangyanadam1...@gmail.com wrote: We can turn the sorted array with first (n − √n) elements recursively to a balanced binary sorting tree. This can be done by choosing the median as the pivot in every step and then recursively manipulate the left half array and right half array in this way. For a sorted array, to find its median is an easy action with constant time complexity. Thus this procedure will cost O(n-√n) time. At last, we insert the remaining √n elements into the tree, this will cost O(√n * log(n - √n)) time. So the ultimate time complexity will be O(n). On Thu, Aug 26, 2010 at 9:56 PM, Rahul Singal rahulsinga...@gmail.com wrote: @saurav I dont think in place approach is possible . This will end up taking n^2 time . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sorting when n-√n numbers are alre ady sorted
Hi Sourav, I will first inplace sort the last √n elements in O(n) and then merge the two sorted arrays in O(n). The only problem: O(n) merging will not be inplace. On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote: Let A[1..n] be an array such that the first (n − √n) elements are already sorted (though we know nothing about the remaining elements). Give an algorithm that sorts A in substantially better than (n log n) steps. This question is from chapter 4 : Algorithm Design Manual by S Skiena -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Counting number of rectangles
Here's my try:
The following function returns the rectangle number given the dimensions of
the rectangle.
int FindRectangleNumber(int row, int colm)
{
if (row == colm)
return row;
if (row == 1)
return colm;
if (row%2 == 0 colm%2 == 0)
return 2*FindRectangleNumber(row/2, colm/2);
if (row%2 == 1 colm%2 == 0)
return FindRectangleNumber(row - 1, colm) + 2;
if (row%2 == 0 colm%2 == 1)
return FindRectangleNumber(row, colm - 1) + 2;
if (row%2 == 1 colm%2 == 1)
return FindRectangleNumber(row - 1, colm-1) + 1;
}
This function can be used to solve the given problem.
On Sun, Aug 22, 2010 at 3:29 PM, Saikat Debnath saikat@gmail.comwrote:
Can anyone help in finding number of rectangles having a given
recatngle number. A rectangle number is defined as the number of unit
sided square formed inside the given rectangle having a common point
with a diagonal of rectangle. The sides of rectangle have integer
length. E.g. number of rectangle with rectangle number 4 is 4, i.e.
1X4, 2X4, 2X3 and 4X4.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Palindromic Substring
@Aravind:
Ur soln will be O(n^2)*O(n).
It is similar to nipun's soln.
On Sun, Aug 22, 2010 at 6:15 AM, aravind prasad raja@gmail.com wrote:
1)maintain 2 pointers.. one from left and other from right..
2)run two nested loops to compre each element from right with the element
in left..
3)if they are same pass the subset(the characters in between) to function
that checks if it is a palindrome or not.
complexity== O(n^2)+O(n)
correct me if am wrong
On Sun, Aug 22, 2010 at 5:48 AM, venkatesan B
venkat_b_engin...@yahoo.co.in wrote:
use stack
push one by one element before compare to top 2 element in stack
{
if same then pop element and compare next char of string with top char in
stack
if same continue otherwise clear stack
}
else
{push element to stack}
if wrong correct me
--- On *Sat, 21/8/10, nipun batra nipunredde...@gmail.com* wrote:
From: nipun batra nipunredde...@gmail.com
Subject: Re: [algogeeks] Longest Palindromic Substring
To: algogeeks@googlegroups.com
Date: Saturday, 21 August, 2010, 4:18 PM
An O(n^3) solution.Wanna know if it's possible to optimize without using
trees.
#includeiostream
#includestring.h
using namespace std;
char* substring(char*s,int start,int finish)
{
int ctr=0;
char str[1000];
while(start=finish)
{
str[ctr]=s[start];
start+=1;
ctr+=1;
}
str[ctr]='\0';
return str;
}
bool isPalindrome(char *s)
{
int size=strlen(s);
int j=size-1;
int i=0;
while((s[i]==s[j])(ij))
{
i+=1;
j-=1;
}
if (i=j)
return true;
else
return false;
}
int main()
{
int i,j;
char s[100];
cins;
int size=strlen(s);
int tempMax=size-1;
while(tempMax1)
{
for(i=0;i+tempMaxsize;i++)
{
if(isPalindrome(substring(s,i,i+tempMax)))//O(n)
{
puts(substring(s,i,i+tempMax));
cout of size tempMax\n;
break;
}
}
tempMax-=1;
}
return 0;
}
On Sat, Aug 21, 2010 at 12:12 PM, Chonku
cho...@gmail.comhttp://mc/compose?to=cho...@gmail.com
wrote:
I definitely meant a suffix Tree and not a trie. Apologize for that. :)
On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal
fundoon...@yahoo.co.inhttp://mc/compose?to=fundoon...@yahoo.co.in
wrote:
@chonku
As i understand, a trie is used when we have a lot of strings (such as a
dictionary).
Here we just have a single string. The resultant trie will be:
a
\
b
\
c
\
l
\
e
\
v
\
e
\
l
\
a
\
b
\
c
We get a similar trie for the reverse string.
So why are you using a trie here? I cant see any advantage of it here.
On Fri, Aug 20, 2010 at 8:36 AM, Chonku
cho...@gmail.comhttp://mc/compose?to=cho...@gmail.com
wrote:
Can we use a trie here.
Make first pass from left to right and construct the trie.
Make second pass from right to left and look for the trie branch with
maximum nodes that match the characters.
On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal
fundoon...@yahoo.co.inhttp://mc/compose?to=fundoon...@yahoo.co.in
wrote:
Hi All,
Givan a string, you have to find the longest palindromic substring.
For ex: Longest Palindromic substring for abclevelabc is level.
What is the most optimised solution possible?
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
http://mc/compose?to=algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
http://mc/compose?to=algogeeks%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.comhttp://mc/compose?to=algoge...@googlegroups.com
.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comhttp://mc/compose?to=algogeeks%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
Re: [algogeeks] Longest Palindromic Substring
@Nipun: The soln is correct. It is O(n^3) and no extra memory is required.
One soln I can think of is:
Find longest common substring in the given string and its reverse. It will
be a palindrome.
This will be O(n^2) but uses extra space.
On Sat, Aug 21, 2010 at 4:18 PM, nipun batra nipunredde...@gmail.comwrote:
An O(n^3) solution.Wanna know if it's possible to optimize without using
trees.
#includeiostream
#includestring.h
using namespace std;
char* substring(char*s,int start,int finish)
{
int ctr=0;
char str[1000];
while(start=finish)
{
str[ctr]=s[start];
start+=1;
ctr+=1;
}
str[ctr]='\0';
return str;
}
bool isPalindrome(char *s)
{
int size=strlen(s);
int j=size-1;
int i=0;
while((s[i]==s[j])(ij))
{
i+=1;
j-=1;
}
if (i=j)
return true;
else
return false;
}
int main()
{
int i,j;
char s[100];
cins;
int size=strlen(s);
int tempMax=size-1;
while(tempMax1)
{
for(i=0;i+tempMaxsize;i++)
{
if(isPalindrome(substring(s,i,i+tempMax)))//O(n)
{
puts(substring(s,i,i+tempMax));
cout of size tempMax\n;
break;
}
}
tempMax-=1;
}
return 0;
}
On Sat, Aug 21, 2010 at 12:12 PM, Chonku cho...@gmail.com wrote:
I definitely meant a suffix Tree and not a trie. Apologize for that. :)
On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
@chonku
As i understand, a trie is used when we have a lot of strings (such as a
dictionary).
Here we just have a single string. The resultant trie will be:
a
\
b
\
c
\
l
\
e
\
v
\
e
\
l
\
a
\
b
\
c
We get a similar trie for the reverse string.
So why are you using a trie here? I cant see any advantage of it here.
On Fri, Aug 20, 2010 at 8:36 AM, Chonku cho...@gmail.com wrote:
Can we use a trie here.
Make first pass from left to right and construct the trie.
Make second pass from right to left and look for the trie branch with
maximum nodes that match the characters.
On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal
fundoon...@yahoo.co.in wrote:
Hi All,
Givan a string, you have to find the longest palindromic substring.
For ex: Longest Palindromic substring for abclevelabc is level.
What is the most optimised solution possible?
Please access the attached hyperlink for an important electronic
communications disclaimer:
http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic
communications disclaimer:
http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from
Re: [algogeeks] Re: Longest Common Subsequence
longest common substring in the given string. If i get it right. You need two strings to find a common subsequence. We use DP for it. 2010/8/18 ♪ ѕяiηivαѕαη ♪ 21.sr...@gmail.com Example: If my sequence is ABC..the longest common subsequence is AC,BC,AB. It is a very common problem... On Wed, Aug 18, 2010 at 11:58 AM, vinodh kumar vinodh...@gmail.comwrote: heh could u explain the question with a example..??!! On Aug 18, 8:47 pm, ♪ ѕяiηivαѕαη ♪ 21.sr...@gmail.com wrote: Hi.. Can anyone here explain me /provide me with an algorithm/source code in C which efficiently finds out the *longest common substring in the given string??* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
@Nikhil Agarwal: You cannot take extra memory and neither the range of
numbers is specified.
Counting will not be a viable option.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Check this new algo: plz provide counter eg.(if any)
step 1 : count the no. of elements,0s,1s,2s,3s in arr1 and arry2.if yes
proceed to step 2 else print fail
step2: if(sum of the elements and product of the non zero elements are
same in both arrays ) print arrays are same else print fail.
On Fri, Aug 20, 2010 at 4:26 AM, Dave dave_and_da...@juno.com wrote:
@Saikat: Rather than challenging everyone to keep coming up with
counterexamples, please provide a rationale as to why an algorithm
such as this should work. It looks as if you have two equations in 2N
unknowns and are trying to assert that the only solution is A_1 =
B_1,
A_2 = B_2, etc. (where I have assumed that each array is sorted).
Usually, it takes 2N equations to determine 2N unknowns, although
other information about the solutions can lessen that number in
certain circumstances.
At least if you are going to propose something, do so only after you
have tested it on all of the combinations of up to four numbers
between -5 and 5.
Dave
On Aug 19, 11:52 am, Saikat Debnath saikat@gmail.com wrote:
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote:
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
Dave
On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote:
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
@Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
S1=0;S2=0;
M1=-1 and M2 =-4 (excluding 0 multiplication which i had
corrected)
M1!=M2 there fore it is correct.
Code:
bool check_arrays(vectorint v1,vectorint v2){
if(v1.size()!=v2.size())
return 0;
if(v1.size()==0v2.size()==0)
return 1;
int sum,product1,product2;
sum=0;product1=1;product2=1;
for(int i=0;iv1.size();i++){
sum+=v1[i];
sum-=v2[i];
if(v1[i]!=0)
product1*=v1[i];
if(v2[i]!=0)
product2*=v2[i];
}
if(sum==0(product1==product2))
return 1;
return 0;
}
On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com
wrote:
@Srinivas, Make that: Your algorithm seems to fail on A =
{0,1,-2), B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of
twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com
wrote:
add one more thing to the solution suggested by nikhil
i.e;count the
number
of elements in array 1 and number of elements in array2 if
these two
values
are equal then after follow the algo proposed by nikhil
agarwal..
On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Chonku: Your algo seems to fail with following input.
Arr1[]= {1,6}
Arr2[]={7}
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Nikhil: Your algo seems to fail with following input.
What do you
say?
Arr1[]= {1,2,3}
Arr2[]={6}
On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.com wrote:
Sum all the elements of both the arrays..let it be s1 and
s2
Multiply the elements and call as m1 and m2
if(s1==s2) (m1==m2)
return 1;else
return 0;
O(n)
On Tue, Aug 17, 2010 at 11:33 PM, amit
amitjaspal...@gmail.com
wrote:
Given two arrays of numbers, find if each of the two
arrays have
the
same set of integers ? Suggest an algo which can run
faster than
NlogN
without extra space?
--
You received this message because you are subscribed to
the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group
Re: [algogeeks] Longest Palindromic Substring
@chonku As i understand, a trie is used when we have a lot of strings (such as a dictionary). Here we just have a single string. The resultant trie will be: a \ b \ c \ l \ e \ v \ e \ l \ a \ b \ c We get a similar trie for the reverse string. So why are you using a trie here? I cant see any advantage of it here. On Fri, Aug 20, 2010 at 8:36 AM, Chonku cho...@gmail.com wrote: Can we use a trie here. Make first pass from left to right and construct the trie. Make second pass from right to left and look for the trie branch with maximum nodes that match the characters. On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Longest Palindromic Substring
Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
@Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
S1=0;S2=0;
M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected)
M1!=M2 there fore it is correct.
Code:
bool check_arrays(vectorint v1,vectorint v2){
if(v1.size()!=v2.size())
return 0;
if(v1.size()==0v2.size()==0)
return 1;
int sum,product1,product2;
sum=0;product1=1;product2=1;
for(int i=0;iv1.size();i++){
sum+=v1[i];
sum-=v2[i];
if(v1[i]!=0)
product1*=v1[i];
if(v2[i]!=0)
product2*=v2[i];
}
if(sum==0(product1==product2))
return 1;
return 0;
}
On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote:
@Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote:
add one more thing to the solution suggested by nikhil i.e;count the
number
of elements in array 1 and number of elements in array2 if these two
values
are equal then after follow the algo proposed by nikhil agarwal..
On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com
wrote:
@Chonku: Your algo seems to fail with following input.
Arr1[]= {1,6}
Arr2[]={7}
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com
wrote:
@Nikhil: Your algo seems to fail with following input. What do you
say?
Arr1[]= {1,2,3}
Arr2[]={6}
On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.com wrote:
Sum all the elements of both the arrays..let it be s1 and s2
Multiply the elements and call as m1 and m2
if(s1==s2) (m1==m2)
return 1;else
return 0;
O(n)
On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com
wrote:
Given two arrays of numbers, find if each of the two arrays have
the
same set of integers ? Suggest an algo which can run faster than
NlogN
without extra space?
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
Re: [algogeeks] Permutation of Array.
The critical thing here is how to define your comparator function to be used for sorting. Sorting using the normal comparator function will return the following: 31 33 55 312 Using insertion sort O(n^2) such that the resultant concatenation is smallest, should do it. The steps for [55,31,312,33] would be: 55 31 55 312 31 55 312 31 33 55 which gives the correct result :) Defining the comparator function on these lines should do it in O(nlogn) as well. On Thu, Aug 19, 2010 at 5:02 PM, Shiv ... shivsinha2...@gmail.com wrote: An interesting idea would be treat the inputs as strings and sort them. On Thu, Aug 19, 2010 at 4:01 AM, amit amitjaspal...@gmail.com wrote: Given an array of numbers. Calculate a permutation when the concatenate number is smallest. For instance, [55,31,312,33] is 312313355 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 0's and 1's yet again!!!
@ram:
This doesnt work for:
arr[] = {1,0,0,0}
Here, then number of 1's and 0's are not same. So the array should be left
untouched.
On Thu, Aug 19, 2010 at 7:02 PM, ram das ramnaraya...@gmail.com wrote:
{
int odd=1,even=0;
while(odd = size even =size)
{
if ( arr[even] != 1 )
even+=2;
if ( arr[odd] != 0 )
odd+=2;
if ( arr[even] == 1 arr[odd] == 0 )
{
arr[even]=0;
arr[odd]=1;
}
}
}
On Thu, Aug 19, 2010 at 7:00 PM, ram das ramnaraya...@gmail.com wrote:
shiftZeroOne(int *arr,int size)
{
int odd=1,even=0;
while(odd = size even =size)
{
if ( arr[even] != 1 )
even+=2;
if ( arr[odd] != 0 )
odd+=2;
if ( arr[even] == 1 arr[odd] == 0 )
{
arr[even]=0;
arr[odd]=1;
}
}
}
On Thu, Aug 19, 2010 at 5:53 PM, Rais Khan raiskhan.i...@gmail.comwrote:
void ArrayShifting(int *str, int size)
{
int odd=1, even=0;
while(odd size)
{
int position;
if(str[even]!=0)
{
position = even+1;
while(position size)
{
if(str[position]==0)
{ str[position]=1;str[even]=0;break;}
position = position+2;
}
}
even = even+2;
if(str[odd]!=1)
{
position = odd+1;
while(position size)
{
if(str[k]==0)
{ str[position]=0;str[odd]=1;break;}
position = position+2;
}
}
odd=odd+2;
}
}
This code seems working for me, If you agree then we can work on
measuring the complexity improving the code accordingly.
On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar
asshuto...@gmail.com wrote:
Hi Amit
Am I allowed to keep counters to count the number of 1's and 0s right?
The condition of not using extra memory is for the array!?
Regards
Ashutosh
2010/8/18 amit amitjaspal...@gmail.com
you are given an array of integers containing only 0s and 1s. you have
to place all the 0s in even position and 1s in odd position and if
suppose no if 0s exceed no. of 1s or vice versa then keep them
untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Ram Narayan Das
mob: +91 9177711195
--
Thanks Regards
Ram Narayan Das
mob: +91 9177711195
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Shuffling a deck of cards
Use Knuth Shuffle algo.
On Sun, Aug 15, 2010 at 8:34 PM, Rahul Singhal nitk.ra...@gmail.com wrote:
Let X1, X2…. XN (In this case N=52) be the set of N numbers to be shuffled.
1. Set j to N
2. Generate a random number R. (uniformly distributed between 0 and 1)
3. Set k to (jR+1). k is now a random integer, between 1 and j.
4. Exchange Xk and Xj
5. Decrease j by 1.
6. If j 1, return to step 2.
void Shuffle(int* pArr)
{
int rand;
for(int i=51;i=0;i--)
{
rand=GenRand(0,i);
swap(pArr[i], pArr[rand]);
}
}
GenRand(int min, int max) generates a random number between min and max.
On Sun, Aug 15, 2010 at 9:10 AM, Dave dave_and_da...@juno.com wrote:
@Sharad: Your code does not produce equally probable shuffles. You can
see this by noting that a[0] is swapped with one of 52 cards, same for
a[1], a[2], ..., a[51]. Thus, there are 52^52 possible sets of swaps.
But there are only 52! possible outcomes, and 52^52 / 52! is not an
integer.
You can verify this experimentally by shuffling a small deck, say 3
cards. If you do so, you will find that, starting with the deck ABC,
you get ABC 4/27 of the time, ACB 5/27, BAC 5/27, BCA 5/27, CAB 4/27,
and CBA 4/27. Thus, some outcomes are 25% more likely than others.
The proper code is
for(i=1;i52;++i)
{
int r=rand()%(i+1);
swap(a[i],a[r]);
}
Dave
On Aug 14, 9:34 pm, sharad kumar aryansmit3...@gmail.com wrote:
for(i=0;i52;++i)
{
int r=rand()%52;
swap(a[i],a[r]);
}
On Sat, Aug 14, 2010 at 11:46 PM, amit amitjaspal...@gmail.com wrote:
write a program to shuffle an pack of cards in the most efficient way.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Rahul singhal
RnD Engineer
Tejas Networks
Mobile- 09916969422
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
Use hash maps... On Mon, Aug 16, 2010 at 10:06 PM, ashita dadlani ash@gmail.com wrote: You have a string say foobarfoo in which fo and oo aree repeated twice.You have to find all such repeated pairs in O(n) time,The string can only have alphanumeric elements in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
Let the problem be represented as f(i,j) for i A's and jB's.
Amir represented it correctly as: f(i,j) = f(i,j-1) + f(j,i-1)
Lets try another representation:
Let t(i,j) is the number of strings of length i+j with iA's and jB's in any
order.
Hence, t(i, j) = (i+j)Ci
Now some valid strings for our problem would be:
At(n-2,0)AB...ntimes, where t(n-2,0) is a string counted as valid
by t(n-2,0)
Or At(n-2,1)AB...n-1times, t(n-2,1) is a string counted as valid
by t(n-2,1)
Hence,
*f(n,n) = t(n-2,0) + t(n-2,1) + t(n-2,2)+...+t(n-2,n-1)*
*
*
Adding these terms should give you the answer.
Hope this helps
Cheers
Nikhil Jindal
Delhi College of Engineering
On Thu, Aug 5, 2010 at 9:56 PM, Ashish Goel ashg...@gmail.com wrote:
can u explain how is this number reached at?
(2n)!/((n+1)!(n!))
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Aug 5, 2010 at 12:53 PM, umesh kewat umesh1...@gmail.com wrote:
Calculate the number of string can be formed by this formula in one
statement..
for cross check the result is
2N!/((N+1)! * N!) where is number of A or B in string
On Thu, Aug 5, 2010 at 8:54 AM, Ashish Goel ashg...@gmail.com wrote:
void dyckWords(int index, int open, int close)
{
static int dyck=0;
if (index == 2 *n)
{
printf(%s\n, out);
return ;
}
out[index] = '('; //or A
if ((open + 1) = n open = close)
{
dyckWords(index + 1, open + 1, close);
}
out[index] = ')';//or B
if ((close + 1) = n open = close)
{
dyckWords(index + 1, open, close + 1);
}
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
@ashish: AAA is the prefix of the string and it is valid as a prefix
and it's only used for strings with length = 6 (where it is a valid
prefix)
actually only dp[i][j] where i==j counts the number of such strings and
otherwise there is no string where i!=j and it that case dp[i][j] counts
the
number of valid prefixes for string
dp[0][0]=1 does satisfy both properties because 0=0 so the number of As
Bs are the same
the logic behind n/2 is that if the length of the string is n this
means that it has n/2 As and n/2 Bs (n must be even)
the dp for n=4 doesn't look like that! this is how it looks (i just
compiled the code and checked values of dp):
1 0 0
1 1 0
1 2 2
so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Umesh kewat
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amezan interview.........
Observation:
Following is the sequence of indices which we want to swap:
(2,n+1)
(3,n+1)
(4,n+2)
(5,n+1)
(6,n+3)
(7,n+2)
(8,n+4)
(9,n+3)
Hence, for even indices we swap (k,n + k/2) and for odd indices, we swap(k,
n + k/2-1).
This is O(n). and constant space.
for(k=1;k=2*n;k++) {
if(k%2==0) {
swap(a[k],a[n+k/2]);
} else {
swap(a[k],a[n+k/2-1]);
}
}
*Done!*
Nikhil Jindal
Delhi College of Engineering
On Sat, Aug 7, 2010 at 10:17 AM, Dave dave_and_da...@juno.com wrote:
Here's a solution that I am pretty sure is less than O(n^2). The data
are moved only once, but timing the routine suggests that it is O(n
log n), but I have no proof of that.
The first and last do-while loops move cycles of data, while the
nested do-while loops find the beginning index of a new cycle.
Dave
int Shuffle( int a[], int N)
{
int i, j, m, t, u;
if( N 1 ) return 1;
if( N == 2 ) return 0;
N *= 2;
m = N-2;
i = j = 1;
t = a[j];
do
{
j = (j+j N ? j+j : j+j-N+1);
u = a[j];
a[j] = t;
t = u;
m--;
}
while( j != i );
while( m 0 )
{
do
{
j = ++i;
do
j = (j+j N ? j+j : j+j-N+1);
while( j i );
}
while( j != i );
t = a[j];
do
{
j = (j+j N ? j+j : j+j-N+1);
u = a[j];
a[j] = t;
t = u;
m--;
}
while( j != i );
}
return 0;
}
On Aug 6, 12:37 pm, UMESH KUMAR kumar.umesh...@gmail.com wrote:
how to sort specific order the given array ,Without using extra memory
Input:-a1,a2,a3,a4,a5..an,b1,b2,b3,b4,b5..bn.
output:-a1,b1,a2,b2,a3,b3,an.bn
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Bitstring with equal 0s and 1s
Here's a possible O(n) soln: for all i, I calculate a[i].diff as number of zeroes - number of ones ones from a[0] to a[i]. I do this in O(n). Also, I make a list of all the indexes that have a difference d(for all possible d, which is n). Now, for it to be possible that the number of ones and number zeros between two indices i and j are same, a[i].diff needs to be equal to a[j].diff Thus, for a particular difference d, in the list I take the first value of the list and the last value and their diff gives me the maximum length of string possible through diff d. Now find max by iterating thru all d's which is again O(n). Hence, time complexity: O(n) Space: O(n) On Sun, Aug 1, 2010 at 12:33 PM, Ram Kumar harrypotter@gmail.comwrote: Given an array of 0s and 1s in any order, find the longest sequence that has equal number of 0s and 1s. 0 0 0 0 1 1 1 1 0 0 //array 0 1 2 3 4 5 6 7 8 9 //index ans1 (0,7) ans2 (1,8) ans3 (2,9) all having 4 0's and 4 1's -- Regards, Ramkumar.G -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] minimum window containing charecters
wat abt duplicates? eg THAT TT answer should be 1 or 4 ? On Sun, Aug 1, 2010 at 11:22 PM, srikanth sg srikanthini...@gmail.comwrote: dude they dont need to be in the same order .. how are taking care of that On Sun, Aug 1, 2010 at 10:47 AM, Anand anandut2...@gmail.com wrote: Using Dynamic programing(Longest common subsequence logic) we can solve this problem in O(nm) where n is the length of the first string and m is the length of second string. Last element of matrix which the length of the string that matches. http://codepad.org/cyiKEMSF http://codepad.org/cyiKEMSF On Sun, Aug 1, 2010 at 8:13 AM, srikanth sg srikanthini...@gmail.comwrote: plz .. if any one knows dp solution then tell ... On Sun, Aug 1, 2010 at 7:31 AM, Ashim Kapoor ashimkap...@gmail.comwrote: I am not sure, but can I do this using a suffix trie ? any comments ? On Sun, Aug 1, 2010 at 2:29 PM, Ashish Goel ashg...@gmail.com wrote: solution could be to find the charcter position from both sides for each char of s2 then from the 2*n array, find the smallest index from left and largest from right, within these two indexes all chars would be there one case where one of the chars can be missing can be found if a row in this 2-d array remains unmodified Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Jul 31, 2010 at 10:22 PM, Nikhil Jindal fundoon...@yahoo.co.in wrote: At the moment, I can only think of an O(n^3) algo. Maybe if you can find a hash function which computes the hash value depending on the unique characters the string contains, you can reduce it to O(n^2). On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.com wrote: given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You
Re: [algogeeks] minimum window containing charecters
At the moment, I can only think of an O(n^3) algo. Maybe if you can find a hash function which computes the hash value depending on the unique characters the string contains, you can reduce it to O(n^2). On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.comwrote: given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merging Companies Problem
For merging n companies, F(n) = n*F(n-1) for n 3.
Base case, F(3) = 3.
On Sat, Jul 31, 2010 at 6:59 PM, sourav souravs...@gmail.com wrote:
Suppose we start with n companies that eventually merge into one big
company. How many different ways are there for them to merge?
With three companies {a,b,c}, we need to find the number of ways that
the three companies can become two companies, and for every one of
those possibilities, the two remaining companies can be reduced to one
in only 1 way (because we've already solved the case of two
companies). In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b},
{bc,a}], or 3.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: What is the time complexity of multiplying two n-digit numbers base b
Multiplying two n digit numbers, where multiplication of two 1 digit numbers is O(1), is : O(n^2). On Sat, Jul 31, 2010 at 9:12 PM, Dave dave_and_da...@juno.com wrote: If by repeated addition method, you mean m + m + m + ... + m (where m occurs k times) for forming the product k*m, then the work of forming k*m where k and m are n digit numbers is O((k-1)*n). Using the elementary school algorithm, the work can be reduced to O(n^2). See http://en.wikipedia.org/wiki/Multiplication_algorithm for even faster algorithms. Dave On Jul 31, 7:58 am, sourav souravs...@gmail.com wrote: When you first learned to multiply numbers, you were told that x * y means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is the time complexity of multiplying two n-digit numbers in base b using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes O(1) time. Show how you arrive at your answer. (Hint that was given : how big can y be as a function of n and b?) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
@Ram Kumar: Yes. Simple and affective. Just at each node: node-left-side=node-right node-right-side=node-side-left i.e at each node you are setting the side of each of your child. Go on and just do it for all nodes. Done. On Sat, Jul 31, 2010 at 9:39 AM, Ram Kumar harrypotter@gmail.comwrote: DONT DO A BFS!! NOT WORTH IT! CALL THE NEW POINTER AS 'SIDE' POINTER. for every root connect its left and right, for every root connect root-right and root-SIDE-left that ll do -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: impossible microsoft puzzle
Hello All, Since duplicates are allowed, the fact that I can see the number on others hat is of no significance to me. My guess with this information is as good without it. Hence, I will consider the situation as: I am sitting alone in a dark room and I am given a hat with a number from 1 to N. I have to guess the number on my hat. I am in such a situation N times and I have to develop a strategy for guessing such that I am correct atleast once. Now if I guess a number x (1=x=N), my probability of correctness is 1/N i.e if I guess the same number N times, I will be correct once. Hence I guess the same number every time. For the given puzzle, all men guess the same number and at least one of them will be correct. :) Nikhil Jindal Department of Computer Engineering Delhi College of Engineering http://www.dce.edu, Delhi My Blog: http://fundoonick.blogspot.com My LinkedIn Profile: http://www.linkedin.com/in/nikhiljindal http://www.linkedin.com/in/nikhiljindal On Sun, Jul 4, 2010 at 11:05 PM, Dave dave_and_da...@juno.com wrote: But everyone guesses simultaneously. I take it to mean that no one knows anyone else's guess when making his own. Dave On Jul 4, 2:01 am, agnibha nath agni.fl...@gmail.com wrote: can it be like... one person sees any other person's number and guesses it first. then, everybody else guesses the same number. this way, atleast one guesses it right, since there is no boundation on the no. of wrong guesses. On Jul 3, 11:10 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: N people team up and decide on a strategy for playing this game. Then they walk into a room. On entry to the room, each person is given a hat on which one of the first N natural numbers is written. There may be duplicate hat numbers. For example, for N=3, the 3 team members may get hats labeled 2, 1, 2. Each person can see the numbers written on the others' hats, but does not know the number written on his own hat. Every person then simultaneously guesses the number of his own hat. What strategy can the team follow to make sure that at least one person on the team guesses his hat number correctly? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 0 and 1 again :)
Hello Jalaj, I am not sure whether I have understood your approach corectly, but do you want to say that you will always get a subsequence with number of terms equal to twice the min(count0, count1)? Consider for ex: 00 The longest subsequence is 01 or 10, both of length 2(and none of length 4). PS: I am assuming by maximum subsequence, you meant longest. Nikhil Jindal On Sun, Jul 4, 2010 at 3:21 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space algorithm to find the maximum sub sequence which has equal number of 1s and 0s. Examples 1) 10101010 The longest sub sequence that satisfies the problem is the input itself 2)1101000 The longest sub sequence that satisfies the problem is 110100 My approach: in 1 go count the number of zero's and 1's .. find which is smaller then in the next scan take two count1 and count0 and start fetching o's and 1's upto you get them to the smaller count(calculated earlier) better answers ?? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
