Re: [algogeeks] Divide an array into two equal subsets
What if we sort array and place first n/4 and last n/4 elements in one subarray and other n/2 in the 2nd subarray. On Fri, Dec 31, 2010 at 4:08 AM, Anand wrote: > http://anandtechblog.blogspot.com/2010/07/partition-of-array.html > > > On Thu, Dec 30, 2010 at 12:35 AM, vishal raja wrote: > >> This means , You can make a sum = j , with or without using the item i , >> while calculating P[i][j]. >> >> So you can have another counter Count2 which will have the count for such >> items. So you will calculate P as discussed before >> but You will add 1 in Count2[i][j] whenever you find that case. add one in >> count[i][j] in any of P = 1 case. >> >> in the end you'll search for the max value of j (closest to S/2) for all P >> values which has this property on value of i . >> 1. i = 50 >> 2. for all i> 50 >> i-count2[i][j] <= 50 >> >> I think this will do. Check it out. >> On Thu, Dec 30, 2010 at 12:41 PM, Ankur Khurana > > wrote: >> >>> vishal , what will we do to count when both p[i-1][j] and >>> p[i-1][j-a[i]] is true . >>> >>> On Thu, Dec 30, 2010 at 12:36 PM, Ankur Khurana >>> wrote: >>> > Thanks everybody for wonderful support and special thanks to Vishal >>> > raja. . But i was bit apprehensive about your last solution . . i will >>> > test it :) and let you know as well . Thanks . . . . >>> > >>> > >>> > On Thu, Dec 30, 2010 at 11:52 AM, vishal raja >>> wrote: >>> >> But the same solution I've given above can give you the solution for >>> this >>> >> problem . >>> >> In the formed table of P[i][j] , you can take another variable >>> attached to >>> >> it as count[i][j] for how many items we have selected yet. >>> >> So you gotta find , the max. value of j which has count = 50. >>> >> count[i][j] = count[i-1][j] if P(i-1,j) ==1 >>> >> count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 >>> >> else count[i][j] = 0 >>> >> >>> >> >>> >> >>> >> >>> >> On Thu, Dec 30, 2010 at 11:42 AM, vishal raja >> > >>> >> wrote: >>> >>> >>> >>> yeah, My bad. >>> >>> Missed that. >>> >>> >>> >>> On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares < >>> wladimir...@gmail.com> >>> >>> wrote: >>> >>> Sum up all the number and divide by 2 >>> >>> Using the algorithm subset problem to find a number close to median >>> >>> >>> Wladimir Araujo Tavares >>> Federal University of Ceará >>> >>> >>> >>> >>> >>> >>> On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana < >>> ankur.kkhur...@gmail.com> >>> wrote: >>> > >>> > How will you divide and array of approx 100 elements into two sub >>> sets >>> > of 50 each such that the difference between both the subsets is the >>> > minimum possible one . . >>> > >>> > Thanks in advance . >>> > Ankur >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> > Groups "Algorithm Geeks" group. >>> > To post to this group, send email to algoge...@googlegroups.com. >>> > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com >>> . >>> > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> >> >>> >> -- >>> >> You received this message because you are subscribed to the Google >>> Groups >>> >> "Algorithm Geeks" group. >>> >> To post to this group, send email to algoge...@googlegroups.com. >>> >> To unsubscribe from this group, send email to >>> >> algogeeks+unsubscr...@googlegroups.com >>> . >>> >> For more options, visit this group at >>> >> http://groups.google.com/group/algogeeks?hl=en. >>> >> >>> > >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post t
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@sourav, As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's because each element can be at most popped twice. Thanks Yq On Mon, Jan 3, 2011 at 11:20 AM, sourav wrote: > @yq Zhang, > > To pop if you are going to "pop all from first stack and push into the > second stack", then does your operation remain "constant time"? Please > note that we need constant time implementation for the 3 functions > pop_front, push_rear and get_min(). Goint by your approach, not all of > them are constant time. > > Thanks, > Sourav > > On Jan 3, 9:44 pm, yq Zhang wrote: > > Push into one stack. When pop first pop all from the first stack and push > > into the second stack. Then pop from the second stack > > On Jan 3, 2011 7:42 AM, "MOHIT " wrote: > > > > > if only two stack are used but how pop_front is get? > > > > > suppose if element comes in order > > > > > 12 15 4 3 7 20 > > > then in min queue > > > 1. 12 (12) > > > 2. 12 12 (12,15) > > > 3. 12 12 4 (12,15,4) > > > 4.12 12 4 3 (12,15,4,3) > > > 5.12 12 4 3 3 (12,15,4,3,7) > > > 6.12 12 4 3 3 3 (12,15,4,3,20) > > > > > we can get min in constant by pop of stack but how pop front will work > > using > > > two stack only in constant 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.com > > > > > .> For more options, visit this group at > > > > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@yq Zhang, To pop if you are going to "pop all from first stack and push into the second stack", then does your operation remain "constant time"? Please note that we need constant time implementation for the 3 functions pop_front, push_rear and get_min(). Goint by your approach, not all of them are constant time. Thanks, Sourav On Jan 3, 9:44 pm, yq Zhang wrote: > Push into one stack. When pop first pop all from the first stack and push > into the second stack. Then pop from the second stack > On Jan 3, 2011 7:42 AM, "MOHIT " wrote: > > > if only two stack are used but how pop_front is get? > > > suppose if element comes in order > > > 12 15 4 3 7 20 > > then in min queue > > 1. 12 (12) > > 2. 12 12 (12,15) > > 3. 12 12 4 (12,15,4) > > 4.12 12 4 3 (12,15,4,3) > > 5.12 12 4 3 3 (12,15,4,3,7) > > 6.12 12 4 3 3 3 (12,15,4,3,20) > > > we can get min in constant by pop of stack but how pop front will work > using > > two stack only in constant 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.com > .> For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Longest increasing subsequence
@anand http://anandtechblog.blogspot.com/2010/07/longest-increasing-subsequence.html there is problem with your blog... plz check it . its very nice.. and very informative... but it no opening check it plz... On Fri, Dec 31, 2010 at 10:18 PM, Anand wrote: > @Nikhil, > > I searched through the group for the answer but didn't find one so I stated > again. > > > On Fri, Dec 31, 2010 at 1:39 AM, Nikhil Agarwal > wrote: > >> I guess this has already been discussed here many times.Please check in >> the group archives. >> >> >> On Fri, Dec 31, 2010 at 2:14 PM, Anand wrote: >> >>> Longest increasing subsequence using segment tree with O(nlogn) >>> >>> >>> http://anandtechblog.blogspot.com/2010/12/longest-increasing-subsequence-using.html >>> >>> >>> On Thu, Dec 30, 2010 at 11:27 PM, juver++ wrote: >>> And of course simple binary search. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> 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.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile" -- 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: Interview question amazon
On Tue, Jan 4, 2011 at 8:13 AM, rahul patil wrote: > > > On Mon, Jan 3, 2011 at 6:08 PM, juver++ wrote: > >> Tree structure already have parent node link. Even we reconstruct the tree >> as linked list we are not allowed to achieve > > > Normal tree node does not contain link to its parent. I am not saying > convert tree into linklist directly. I want to say that convert tree into a > branched list(not linear) in which each node can have (at max) 2 nodes as > its next. > > Further u can add some extra fields into ur node struct for optimal > solution. > Just add and set a link to parent of node in node struct it will be a branched list. > > >> the goal. Path can be combined using non-contigious (created from inorder >> traversal) elements. The only solution is using DP with O(MAX_SUM_VALUE) >> extra space for each node. >> >> -- >> 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. >> > > > > > -- > Regards, > Rahul Patil > -- Regards, Rahul Patil -- 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: Interview question amazon
On Mon, Jan 3, 2011 at 6:08 PM, juver++ wrote: > Tree structure already have parent node link. Even we reconstruct the tree > as linked list we are not allowed to achieve Normal tree node does not contain link to its parent. I am not saying convert tree into linklist directly. I want to say that convert tree into a branched list(not linear) in which each node can have (at max) 2 nodes as its next. Further u can add some extra fields into ur node struct for optimal solution. > the goal. Path can be combined using non-contigious (created from inorder > traversal) elements. The only solution is using DP with O(MAX_SUM_VALUE) > extra space for each node. > > -- > 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. > -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Please Explain
"The C++ compiler can only allocate an array with a size known at
compile time. If you want to allocated a variable size piece of
memory, use the new operator."
http://stackoverflow.com/questions/4589463/initialize-array-size-from-another-array-value
On Jan 3, 4:58 pm, Aniket wrote:
> #include
> using namespace std;
> const int a[]={1,2,3,4,5};
> int b[a[2]];
> int main(){return 0;}
>
> If the code is like above it is giving error in line 4;
>
> But if it is something like below it gives no error after compilation:
>
> #include
> using namespace std;
> const int a=3;
> int b[a];
> int main(){return 0;}
>
> Anybody please expalin.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: probability
@Jai: Oops. I switched two numbers: P(when C shoots at B)=5/18 P(when C shoots at A)=13/36 P(when C shoots in air)=5/12 Dave On Jan 3, 10:36 am, Dave wrote: > @Jai: If B doesn't hit A, then A surely will shoot B. Thus, B's only > chance of survival is to shoot A, so your statement that B will prefer > to kill C is incorrect. > > It also looks like you changed 33% to 1/3. When I calculate the > probabilities of C's survival using 1/3 instead of 33%, I get > > P(when C shoots at B)=13/36 > P(when C shoots at A)=5/18 > P(when C shoots in air)=5/12 > > And I see that I had made a mistake on the last calculation when using > 33%. The correct figure is 0.41312 instead of 0.49624 as I had > reported inhttp://groups.google.com/group/algogeeks/msg/30e11e6ff2945573. > > Dave > > On Jan 3, 9:34 am, jai gupta wrote: > > > > > Going case by case and Taking into consideration Daves suggestion that A > > will prefer to kill B if all three are alive and B will prefer to kill C if > > all three are alive, We find the following probabilities of survival of C by > > starting. > > P(when C shoots at B)=2/9 > > P(when C shoots at A)=13/36 > > P(when C shoots in air)=5/12 > > > Hence C must chose to shoot in air.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Please Explain
#include
using namespace std;
const int a[]={1,2,3,4,5};
int b[a[2]];
int main(){return 0;}
If the code is like above it is giving error in line 4;
But if it is something like below it gives no error after compilation:
#include
using namespace std;
const int a=3;
int b[a];
int main(){return 0;}
Anybody please expalin.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: probability
@Jai: C shoots at B and misses. Then B shoots at A and hits. Then C and B have a shootout with C getting the first shot. C kills B with probability 1/3 + 2/3 * 1/2 * 1/3 + (2/3 * 1/2)^2 * 1/3 + ... = (1/3) / (1 - 2/3 * 1/3) = (1/3) / (2/3) = 1/2 because it is an infinite geometric series. So your formula should be (2/3)*( (1/2 * 1/2 + 1/2 * 1/3) ) = 5/18. Dave On Jan 3, 11:04 am, jai gupta wrote: > @Dave: Sorry It was a typo but for the probability figures, > When C shoots B then if he is successful then A will shoot C > Hence he must be unsuccessful and then > if B is unsuccessful then A must will Kill B and then C must kill A > if B is successful then C must kill B now > Hence P(when C shoots at B)=(2/3 )*( (1/2)*(1/3) + (1/2)*(1/3) ) > =2/9 > > When C shoots at A i am similarly getting for the case when A is killed as > 1/12 > and when A is safe as 5/18 > Hence total 13/36 > > where am i wrong? -- 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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Algorithm provides amortized linear time. So some operations can be O(n), but on average it is linear at all. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: probability
@Dave: Sorry It was a typo but for the probability figures, When C shoots B then if he is successful then A will shoot C Hence he must be unsuccessful and then if B is unsuccessful then A must will Kill B and then C must kill A if B is successful then C must kill B now Hence P(when C shoots at B)=(2/3 )*( (1/2)*(1/3) + (1/2)*(1/3) ) =2/9 When C shoots at A i am similarly getting for the case when A is killed as 1/12 and when A is safe as 5/18 Hence total 13/36 where am i wrong? -- 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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Push into one stack. When pop first pop all from the first stack and push into the second stack. Then pop from the second stack On Jan 3, 2011 7:42 AM, "MOHIT " wrote: > if only two stack are used but how pop_front is get? > > suppose if element comes in order > > 12 15 4 3 7 20 > then in min queue > 1. 12 (12) > 2. 12 12 (12,15) > 3. 12 12 4 (12,15,4) > 4.12 12 4 3 (12,15,4,3) > 5.12 12 4 3 3 (12,15,4,3,7) > 6.12 12 4 3 3 3 (12,15,4,3,20) > > we can get min in constant by pop of stack but how pop front will work using > two stack only in constant 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.com . > For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: probability
@Jai: If B doesn't hit A, then A surely will shoot B. Thus, B's only chance of survival is to shoot A, so your statement that B will prefer to kill C is incorrect. It also looks like you changed 33% to 1/3. When I calculate the probabilities of C's survival using 1/3 instead of 33%, I get P(when C shoots at B)=13/36 P(when C shoots at A)=5/18 P(when C shoots in air)=5/12 And I see that I had made a mistake on the last calculation when using 33%. The correct figure is 0.41312 instead of 0.49624 as I had reported in http://groups.google.com/group/algogeeks/msg/30e11e6ff2945573. Dave On Jan 3, 9:34 am, jai gupta wrote: > Going case by case and Taking into consideration Daves suggestion that A > will prefer to kill B if all three are alive and B will prefer to kill C if > all three are alive, We find the following probabilities of survival of C by > starting. > P(when C shoots at B)=2/9 > P(when C shoots at A)=13/36 > P(when C shoots in air)=5/12 > > Hence C must chose to shoot in air. -- 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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
if only two stack are used but how pop_front is get? suppose if element comes in order 12 15 4 3 7 20 then in min queue 1. 12 (12) 2. 12 12 (12,15) 3. 12 12 4 (12,15,4) 4.12 12 4 3(12,15,4,3) 5.12 12 4 3 3 (12,15,4,3,7) 6.12 12 4 3 3 3(12,15,4,3,20) we can get min in constant by pop of stack but how pop front will work using two stack only in constant 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Palindrome
The blogsite referred is unavailable. On Fri, Dec 31, 2010 at 3:49 AM, Anand wrote: > > http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html > > > On Thu, Dec 30, 2010 at 1:10 PM, Aniket wrote: > >> How do you find the longest palindrome in a given string in O(n) 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.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Rishi Agrawal -- 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: probability
Going case by case and Taking into consideration Daves suggestion that A will prefer to kill B if all three are alive and B will prefer to kill C if all three are alive, We find the following probabilities of survival of C by starting. P(when C shoots at B)=2/9 P(when C shoots at A)=13/36 P(when C shoots in air)=5/12 Hence C must chose to shoot in air. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: probability
@Salil: The argument I was making is that A will choose to shoot at B rather than C on his first shot if both are standing, because doing so maximizes A's chances of survival. Perhaps we are using the notation P(A shoots at C) to mean different things. Dave On Jan 3, 12:24 am, Salil Joshi wrote: > @Dave > In point # 1, I had mentioned that P(A survives) + P(B survives) + P(C > survives) = 1 as the dual will be carried out till only 1 man is left. Do > you agree on this?... > > read more » > > By your calculations, P(A survives) = 0.17 * 1 + 0.5 = 0.67 > P(C survives) = 0.4962 > They add to more than 1. Please let me know your views. > > > > On Mon, Jan 3, 2011 at 11:34 AM, Dave wrote: > > @Salil. The point that is incorrect is: > > 2. Now, by shooting in air C increases his probability by your > > argument, > > which is not good for A. > > Thus, P(A shooting at C) should NOT be 0 if A is intelligent. > > > If A shoots C, then B hits A with 50% probability, but if A shoots B, > > then C hits A with only 33% probability. Thus, A's probability of > > survival is higher if he shoots B rather than C. > > Hence, P(A survives) = .67 * P(A shoots B) + .5 * P(A shoots C). > > But since P(A shoots B) + P(A shoots C) = 1, it follows that > > P(A survives) = 0.67 * P(A shoots B) + 0.5 * [1 - P(A shoots B)] > > = 0.17 * P(A shoots B) + 0.5. > > Therefore, P(A survives) is maximized when P(A shoots B) = 1 and P(A > > shoots C) = 0. > > > Dave > > > On Jan 2, 11:07 pm, Salil Joshi wrote: > > > @Dave, > > > Can you please point out which of the 3 points mentioned earlier sounds > > > incorrect? Because I think that this problem is much like the Three Body > > > problem, and we can not just maximize the likelihood for C, ignoring A & > > B. > > > They will also try to maximize their survival likelihood > > > > On Mon, Jan 3, 2011 at 1:34 AM, Dave wrote: > > > > @Salil: If C shoots at A instead of into the air, he increases the > > > > odds that he will be shot by B, because if C hits A then B will shoot > > > > at C instead of A. > > > > > On the other hand, if C shoots at B instead of into the air, he > > > > increases the odds that he will be shot by A. > > > > > Thus, shooting at either A or B decreases his odds of survival. > > > > > Dave > > > > > On Jan 2, 12:25 pm, Salil Joshi wrote: > > > > > @Dave > > > > > 1. In the end only 1 will survive (after max of 2 rounds). > > > > > i.e. P(A survives in end) + P(B survives in end) + P(C survives in > > end) = > > > > 1 > > > > > > 2. Now, by shooting in air C increases his probability by your > > argument, > > > > > which is not good for A. > > > > > Thus, P(A shooting at C) should NOT be 0 if A is intelligent. > > > > > > 3. If it is not 0, P(C's survival) decreases (doesn't remain > > 0.49624). > > > > > > Please let me know if this is clear enough. > > > > > > On Sun, Jan 2, 2011 at 11:15 PM, Dave > > wrote: > > > > > > @Salil: Just to make sure we are on the same page, A hits with 100% > > > > > > probability, B hits with 50% probability, and C hits with 33% > > > > > > probability. C shoots first, then B, then A. Then the shooting > > > > > > continues among the survivors in that order until only one is > > > > > > standing. > > > > > > > If all three are alive and it is A's turn to shoot, he logically > > will > > > > > > choose to shoot at B rather than C since B has a greater > > probability > > > > > > of hitting him. Thus, your P(A shooting at C) = 0 if B is unhit > > when > > > > > > it is A's turn. > > > > > > > Similarly, if it is B's turn to choose between shooting at A or C, > > he > > > > > > rationally will choose A since A will shoot at and hit B if A gets > > a > > > > > > turn. So your P(B shooting at C) = 0 if A is unhit when it is B's > > > > > > turn. > > > > > > > If you dispute either of the above two paragraphs, please clealy > > state > > > > > > your objection. > > > > > > > Dave > > > > > > > On Jan 1, 11:19 pm, Salil Joshi wrote: > > > > > > > @Dave, > > > > > > > Yeah, I had read those numbers on internet as this puzzle is well > > > > known. > > > > > > > However I am not convinced with the calculations because of > > following > > > > 2 > > > > > > > points: > > > > > > > > 1) If C shoots in air, the probability of survival is more for > > the > > > > > > > probabilities considered in the calculations with which A & B > > will > > > > shoot > > > > > > at > > > > > > > him. > > > > > > > Now, if A & B are intelligent, they will know that increasing > > > > survival > > > > > > > probability for C is bad for them (you can calculate survival > > > > probability > > > > > > > for A & B in each case), and therefore they will shoot at C with > > > > higher > > > > > > > probability than what they were planning earlier. > > > > > > > > 2) C's survival probability depends on P(A shooting at C) * 1 and > > P(B > > > > > > > shooting at C) * 1/2. > > > > > > > If C shoots at A, P(A shooting at C) is less by 33% and P(B > > shooting >
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Yes, you are right. Stack contains the following pair of elements - (Min, Element), where Min - minimum element among all elements in the stack below the current, Element - current element. When you add new element onto the stack, then you should push pair(min(stack.top().Min, Element), Element). To retrieve min element from the stack, simply access its top min. -- 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: Interview question amazon
Tree structure already have parent node link. Even we reconstruct the tree as linked list we are not allowed to achieve the goal. Path can be combined using non-contigious (created from inorder traversal) elements. The only solution is using DP with O(MAX_SUM_VALUE) extra space for each node. -- 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: Longest Palindrome
@Anand post correct algorithm. There is no simpler method to find longest palindrome in a linear time. To understand the algorithm you may be should know the Z algorithm cause main idea is the same. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
