[algogeeks] Apply to US
Hi all, I would like to apply for US companies like google, twitter, linkedin, facebook for next year. Any suggestions how/when should i apply ? General suggestions on prep. Thanks in advance. -- regards, chinna. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: find a point closest to other points
On Tue, May 1, 2012 at 8:44 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Find the centroid X= (x1 +x2xn)/N Y=(y1+y2..yn)/N This will precisely be the point no need to calculate and check with distance. @dubey : Consider this case, let there be a cluster of 4 points near the origin and 1 point at (100,0). Then the answer would be near the origin and not close to the centroid. median might make some sense. On Tue, May 1, 2012 at 1:18 PM, mohit mishra mohit7mis...@gmail.comwrote: Let me know if there is any bug /*using centroid of plane */ struct point { int x; int y; }; typedef struct point Point; int main() { int n,i; int d,dis; float sum_x=0,sum_y=0; Point centroid,final; //clrcsr(); printf(how many points? ); scanf(%d,n); Point p[100]; printf(enter X and Y cordinates of %d points\n,n); for(i=0;in;i++) scanf(%d%d,p[i].x,p[i].y); for(i=0;in;i++) { sum_x=sum_x+p[i].x; sum_y=sum_y+p[i].y; } centroid.x=(int)sum_x/n; centroid.y=(int)sum_y/n; for(i=0;in;i++) { dis=distance(centroid,p[i]); if(disd) { d=dis; final.x=p[i].x; final.y=p[i].y; } } printf(\n The point is (%3d ,%3d),final.x,final.y); getch(); return 0; } int distance(Point A,Point B) { int x,y; x=(A.x-B.x)*(A.x-B.x); y=(A.y-B.y)*(A.y-B.y); return sqrt(x+y); } On Mon, Apr 30, 2012 at 4:34 PM, kosgi santosh santoshko...@gmail.comwrote: how can we find centriod of n points in a plane? Regards, Santosh K. -- 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. -- bhupendra dubey -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] how to code a deterministic or Non-Deterministic finite state automata model?
How about using function pointers ? On Fri, Apr 6, 2012 at 11:09 PM, Doom duman...@gmail.com wrote: Any pointers to a code using NFA / DFA computation model? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/UO5Em7j89scJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] c
Is const a compiler level construct ? #include stdio.h int main() { const int i = 0; int * p ; p = (int *) i; *p = 2; printf((i,p): %x %x \n,i,p); printf((i,p): %d %d \n,i,*p); } I ran this program and got this output.Can somebody explain ? (i,p): bfc3de6c bfc3de6c (i,p): 0 2 On Sat, Aug 20, 2011 at 10:08 AM, sukran dhawan sukrandha...@gmail.comwrote: may be it places the variable in read only memory On Thu, Aug 18, 2011 at 2:38 AM, bihari kumarvive...@gmail.com wrote: How to prevent the compiler to alter the value of i in statement: const int i=2; Just give the idea about the implementation of const int i=somevalue; -- 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. -- regards, chinna. -- 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] MICROSOFT RESEARCH INTERN
Its different. There are separate kind of interviews for both looking for different things. On Tue, Aug 16, 2011 at 5:18 PM, arvind kumar arvindk...@gmail.com wrote: Hi friends Can anyone please tell me about microsoft research intern-the selection process?? Is it the same or is it different from microsoft itc?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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]
Whats the take-home salary if you work at TCS or infosys ? also work hours expected ? On Mon, Aug 15, 2011 at 12:01 PM, vikas singh shyguy1...@gmail.com wrote: TCS also have COBOL project... TCS has every language based project u can think of. it's your luck whether you get the latest technology to work with or the RETRO... On Mon, Aug 15, 2011 at 10:59 AM, vaibhav agrawal agrvaib...@gmail.comwrote: Majorly software maintainence On Mon, Aug 15, 2011 at 12:17 AM, siddharth srivastava akssps...@gmail.com wrote: On 15 August 2011 00:15, sukran dhawan sukrandha...@gmail.com wrote: do they recruit software engineers for maintainenance? yes..and major chunk of projects are maintenance only On Mon, Aug 15, 2011 at 12:10 AM, siddharth srivastava akssps...@gmail.com wrote: On 15 August 2011 00:03, sukran dhawan sukrandha...@gmail.com wrote: hmmm k or even purely maintenance jobs where you may not get chance to code at all On Sun, Aug 14, 2011 at 11:47 PM, rashmi i rash...@gmail.com wrote: Infosys and TCS are consultancies. So, the type of job is not fixed. It depends on the type of project a client provides, so it may involve variety of technologies from C to Java , Perl,etc. On Sun, Aug 14, 2011 at 11:31 PM, sukran dhawan sukrandha...@gmail.com wrote: can anyone tell me what is the job provided by infosys and tcs? IF they do so much mass recruitment what kinda job the ppl get der? -- 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. -- R@$!-! DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS. -- 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. -- Regards Siddharth Srivastava -- 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. -- Regards Siddharth Srivastava -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards VIKAS SINGH MCA- final year NIT DURGAPUR email: vikas.singh1...@gmail.com shyguy1...@gmail.com http://smrit.wordpress.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] reason
I believe you are assuming little endian right ? On Mon, Aug 15, 2011 at 2:14 PM, programming love love.for.programm...@gmail.com wrote: The internal representation of array is this: suppose that the address starts from decimal number 10 and integer occupies 2 bytes 10- 0002 ( num 2 in hex) 12- 0003 ( num 3 in hex) 14- 0004 ( num 4 in hex) Now p points to address 10 and is type char. (Even after type casts) p+1 will increment address by 1 byte (since it's char). p will now point to 11 (int *) will say that when de-referenced 2 bytes should be extracted. So the 2 bytes extracted are 11, 12. Numbers in these bytes are 02 and 00 10- 00*02* ( num 2 in hex) 12- *00*03 ( num 3 in hex) 14- 0004 ( num 4 in hex) now (char *) says extract 1 byte for me. The extracted byte is 00. Hence 0 is printed *Correct me if i am wrong.* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] c++ multi dimensional arrays
In memory arrays are stored in row major ordering.If you dont provide the column size then the system cannot make any access to any of the location in the array. when you actually look for the value at a[4][2] what the system does is that it computes the location as (4 * column_size + 2 ) * (int size ) and then makes the reference a[ new_address ].So if you dont provide the column_size it cannot perform the above operation.Try thinking how would you go about doing that with out column_size for a[4][2] ? Not possible. When you do int * * a , you dont need because a + 1 automatically moves to the next row without the need of column size.Here it is because the underlying implementation is pointer to pointer and it increments accordingly to the next row but not next element in the same row when you do a + 1. Let me know if im wrong anywhere in my explanation. On Wed, Aug 17, 2011 at 12:04 AM, priya ramesh love.for.programm...@gmail.com wrote: Why should the column size be mandatorily passed to a function which expects a multi dimensional array int arr (int marray[][5], int rows); int arr (int marray[][], int rows, int cols); 1st is valid whereas second is invalid. why?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: Probability Puzzle
I'm little late but I too got 17/18. On Tue, Aug 16, 2011 at 10:47 PM, Jacob Ridley jridley2...@gmail.comwrote: I think there is some ambiguity in the question. (All this time you don't know you were tossing a fair coin or not). 1) Does the above statement mean that the thower don't know whether he or she threw a fair coin even after throwing? Or is the thrower not informed beforehand that one of them is not a fair coin? 2) Does the coin count reduce after every throw or should it be put back? 3) Depending on 1) and 2), there will be different answers. On Aug 9, 12:13 am, Maddy madhu.mitha...@gmail.com wrote: I think the answer is 17/80, because as you say the 5 trials are independent.. but the fact that a head turns up in all the 5 trials, give some information about our original probability of choosing the coins. in case we had obtained a tail in the first trial, we can be sure its the fair coin, and so the consecutive trials would become independent.. but since that is not the case, every head is going to increase the chance of choosing the biased coin(initially), and hence affect the probability of the next head.. before the first trial probability of landing a head is 3/5, but once u see the first head, the probability of landing a head on the second trial changes to 4/5*1/4+1/5, and so on..that is, there is a higher probability that we chose a biased coin, rather than the fair coin. hope its clear.. On Aug 7, 11:36 pm, sumit gaur sumitgau...@gmail.com wrote: (3/5) On Aug 7, 10:34 pm, Algo Lover algolear...@gmail.com wrote: A bag contains 5 coins. Four of them are fair and one has heads on both sides. You randomly pulled one coin from the bag and tossed it 5 times, heads turned up all five times. What is the probability that you toss next time, heads turns up. (All this time you don't know you were tossing a fair coin or not).- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] MS test
I believe the answer for fifth one is o(n2) , f(1) + f(2) + ... + f(n/2) ( increment the counter alternatively). Im not very sure. On Sat, Aug 6, 2011 at 10:39 PM, siddharam suresh siddharam@gmail.comwrote: what is *Page segmentation?* Thank you, Siddharam On Sat, Aug 6, 2011 at 10:35 PM, ankit sambyal ankitsamb...@gmail.comwrote: @neha: Cud u explain how r u getting d option for ques 4 ?? -- 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. -- regards, chinna. -- 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] interview questions
I couldn't find the solution to this problem please help. Find the *first unique* string from a list of strings in *one pass.* * * *unique : *It occurs only once in the list. *one pass : *you are allowed to traverse the list only once. -- regards, chinna. -- 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] direct i
O(nlogn) 1. precompute the minimum of [ i+1 N] and store in b[i] 2. Now do a binary search for a[i] in b[i+1] in the range of b[i+1. N] On Wed, Jul 27, 2011 at 12:27 PM, salvador_cerinza vishwakarma.ii...@gmail.com wrote: Let say stack S. 1.insert elements in S of A[] from right to left. 2.int val = S.top(); 3.S.pop(); 4.now check val with S.top() until u find any element smaller than val. 5.Note down the element pop it from stack 6.if step 4 is true , the push val in stack S and all elements which were popped in the order they were popped except the last matched candidate element. Yeah..dis algo is not very efficient.. On Wed, Jul 27, 2011 at 12:20 PM, Pankaj jatka.oppimi...@gmail.comwrote: Can you please elaborate a little about your stack based solution. I was thinking of using queue but was unable to make a perfect algo. On Wed, Jul 27, 2011 at 12:18 PM, salvador_cerinza vishwakarma.ii...@gmail.com wrote: i m suggesting stack not just for best case only . On Wed, Jul 27, 2011 at 12:16 PM, Pankaj jatka.oppimi...@gmail.comwrote: Even in array best case can be O(n). Why use stack? On Wed, Jul 27, 2011 at 12:14 PM, salvador_cerinza vishwakarma.ii...@gmail.com wrote: Best case : O(n) Worst case : O(n^2) can be done using stack. Thinking of better solution. . On Wed, Jul 27, 2011 at 11:50 AM, ankit sambyal ankitsamb...@gmail.com wrote: O(n^2) algo is trivial. Can anybody think of a better 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 DIRECT-I !!!!!!
+1 to the idea of a shared document. A spreadsheet with multiple sheets for different companies should be awesome.But the solution to the problem might as well be discussed in gmail threads. I find it difficult to find the best solution to a problem discussed in gmail threads.Having a spreadsheet should help us to fill in the best possible answer next to each question. I personally dont like those websites like careercup etc (though they are good) just for the reason that for each question u need to visit a diffrent link/page ,also hard to find the best answer to a question. What are your opinions ? On Mon, Jul 25, 2011 at 8:04 PM, shady sinv...@gmail.com wrote: i would recommend you people to share questions related to each company on some document like this... it has access to all and anyone can edit it you can append questions to it in future also.. just a little more systematic then sharing it on thread,,, and one week later someone else will be asking the same question... :D https://docs.google.com/document/d/1GhsStHu3WaCpbGd2PzpiyTvg_IY53dxLc6g6LzhlyKo/edit?hl=en_US On Mon, Jul 25, 2011 at 7:52 PM, swetha rahul swetharahu...@gmail.comwrote: Guys pls dont reveal the placements schedule of AU here... Hope u knw dat v r instructed not to do so.. On Mon, Jul 25, 2011 at 7:47 PM, Mani Bharathi manibharat...@gmail.comwrote: ya :) :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/7LnJnObFILcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: MS
heapsort ? On Sat, Jul 23, 2011 at 1:26 PM, Akshata Sharma akshatasharm...@gmail.comwrote: better than O(n^2).. On Sat, Jul 23, 2011 at 1:08 PM, Akshata Sharma akshatasharm...@gmail.com wrote: Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them. For example, if the given string is Potato, then, the output has to be Pota. Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) . Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: MS
By heapsort i meant : After building the min heap(or max heap) ,we extract the top of heap and put it at the end of the array constraint to one condition that if the element already exists at a[heap-size+1] then dont add just discard and continue. O(nlogn) and inplace with no extra memory.But even i believe that 26 bits is not extra memory may be bitmask is better. On Sat, Jul 23, 2011 at 5:15 PM, Akshata Sharma akshatasharm...@gmail.comwrote: @ross, I have posted my question in a new thread, not as a reply to any existing thread!!! On Sat, Jul 23, 2011 at 5:13 PM, ross jagadish1...@gmail.com wrote: check for visited can also be implemented by using an integer variable and setting corresponding bits! On Jul 23, 4:39 pm, ross jagadish1...@gmail.com wrote: @akshata sharma: Kindly post a new question as a separate thread and not as a reply to an existing one so tat it would be noticed by many ppl! As akash suggestd, use a bit vector called 'visited' of 26 size for ASCII or of a larger size in case of Unicode ( still constant space and i dont think declaring 26 variables counts as an additional DS!!), if visited then , ignore the character while processing. a simple algorithm, int last_ptr=0; for ( i = 0 - N ) { if(visited(a[i])) continue; else a[last_ptr++]=a[i]; visited(a[i]) = true;} a[last_ptr]=NULL; print (%s,a) ; On Jul 23, 12:56 pm, Akshata Sharma akshatasharm...@gmail.com wrote: better than O(n^2).. On Sat, Jul 23, 2011 at 1:08 PM, Akshata Sharma akshatasharm...@gmail.comwrote: Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them. For example, if the given string is Potato, then, the output has to be Pota. Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) . Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters. -- 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. -- regards, chinna. -- 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: Negative index of array
This works. code #include iostream #include map using namespace std; int main() { mapint,int a; a[-1] = 0; couta[-1]endl; } /code On Wed, Jul 20, 2011 at 7:50 PM, ankit sambyal ankitsamb...@gmail.comwrote: You can make the following structure : #define MAX 100 typedef struct { int count_positive; int count_negative; }Element; typedef Element Map[MAX]; Now you can just create a map as : Map map; Now for every element read, first check whether it is +ve or -ve. Use the absolute value of the number read as the key. Increment count_positve if key is +ve and increment count -ve if key is -ve -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] interview questoin
Find unique string from a list of strings in one pass. -- regards, chinna. -- 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: interview questoin
sorry. On Tue, Jul 19, 2011 at 9:07 PM, Shubham Maheshwari shubham.veloc...@gmail.com wrote: what is meant by unique string ...!! A string which occurs only once. On Tue, Jul 19, 2011 at 9:04 PM, SAMMM somnath.nit...@gmail.com wrote: There is only one unique string in the list of strings (words) ? There can be many. On Jul 19, 8:31 pm, pacific :-) pacific4...@gmail.com wrote: Find unique string from a list of strings in one pass. -- regards, chinna. -- 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. -- Shubham Maheshwari ShubZz O.o o.O enJoY ...!!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] MS Question
Hi, You may look out for plagirism detectors. My approach would be : 1. Hash all the keywords in one file and keep the count. 2. For each keyword in the other file , check if it exists in the hash table , decrement its count. Also increment a counter which represents the similarity between the two docs. For percentage you might also count the total keywords in the second doc and do found keywords/ total keywords. On Wed, Jul 6, 2011 at 11:41 AM, Navneet Gupta navneetn...@gmail.comwrote: See diff documentation. It's an application of Longest Common Subsequence problem. http://en.wikipedia.org/wiki/Diff On Wed, Jul 6, 2011 at 11:12 AM, priyanshu priyanshuro...@gmail.com wrote: What is the most efficient way to compare two text documents?? Also we need to find the percentage by which they match.. Thanks, priyanshu -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: Complexity QuickSort
Another question reg. quicksort. If we always find the median in o(n) and use it as the pivot ,will the quicksort by o(nlogn) ( i mean worst case also o(nlogn) )? Since partition is anyway o(n) , im making it o(n) + o(n){for finding median}. On Wed, Jul 6, 2011 at 2:50 AM, Ritesh Srivastava riteshkumar...@gmail.comwrote: It will be O (n*log(n)). Recurrence relation will be T(n) = T(n/4) + T(3n/4) + O(n) Lets just say n=4^p so p=log n in base 4 so this will be the number of steps the array will be divided to get trivial constant size array. at every step , processing done will be O(n) because n -- for first step (n/4) +(3n/4) -- for second step == n/4 for the first partition and 3n/4 for the second partition obtained in the first step ( n/4 * 1/4 + n/4 * 3/4) + ( 3n/4*1/4 + 3n/4*3/4) --third step ... ... so on for logn steps. Hence O(n *logn ) Omitting constant factor of base 4. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/THiTmtrNhogJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Design questions in interviews
Hi all , Can someone point to some websites where you can find cs design questions ? Eg. Design a data structure for sparse matrix ? -- regards, chinna. -- 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: Yahoo Question
Oh I got it. If ( interview at google) { Map reduce } else if(interview at yahoo) { Hadoop } else { Your personal preference. } On Thu, Jun 30, 2011 at 4:02 AM, bittu shashank7andr...@gmail.com wrote: 1.Use Haddop Map Reduce Framework .Obviously We Need Distributed Algo we will make one computer as master assign the job to all slave computer to do the crawling the web depending upon the geographic area ( m thinking real time problem).to crawled the maximum pages in least time we need above framework or any other distributed framework like google map reduce or GFS. computers are given for maximizing the crawling function minimizing the the crawling time time.. Algorithmically you ca think of its like a graph which has 100 connected components in it we will bfs to traverse each computer to find out the number of pages it has been crawled till now. i have given some overview hope it will help Thanks Shashank I Don't Do Code to Code But I Do Code to Build Product Computer Science Engineering Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Binary Tree
My approach : int FindPath(Node n , sum s ) { FindPath(n-left , s ) || FindPath(n-right , s) || OneOf { a1 = AllSumsFromLeafToRoot( n-left ) } + n-value + Oneof { a2 = AllSumsFromLeafToRoot( n-right ) == s ) } // Use a1 and a2 to find out the actual path } Here all possible sums from a node to the leaves can be precomputed in O(n) (one inorder traversal) and so lookup can be made in O(1). For each node store child_left , sum1,sum2,sum3 ... , child_right , sum1,sum2,sum3 ... We may need this data to traverse the tree again with the sum values to find the path. Looks complicated to me too, waiting for comments. On Thu, Jun 30, 2011 at 4:17 PM, sagar pareek sagarpar...@gmail.com wrote: Try traversing in LEVEL order and maintain array for each level...(Levels can be found by height of tree) then try by calculating sums starting from root(level zero) to higher level. Its typical to explain here but i found it as a solution and that will definitely found the solution. On Thu, Jun 30, 2011 at 9:08 AM, rajeev bharshetty rajeevr...@gmail.comwrote: By traversing tree either preorder or inorder or postorder and storing the partial sums along the way and comparing the partial sums with the required sum can solve the problem On Wed, Jun 29, 2011 at 7:56 PM, Akshata Sharma akshatasharm...@gmail.com wrote: How to find a path in a given binary tree which sums up to a given target value? for example if the given BT is 5 / \ 3 2 / 7 and if the target is 10, then the path is root(5) + left node(3) + right node (2). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: spoj shlights
Can one of you provide some hints in solving this problem ? On Sat, Jun 25, 2011 at 3:34 PM, kartik sachan kartik.sac...@gmail.comwrote: @jitendra that's what i am asking forwhat algo i should implement to get process in 1 sec? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] (OOPS) Composition VS Inheritance
The problem with inheritence is that it is compile time(i.e a class A inheriting from class B cannot be modified again) whereas composition can be used to change the objects during runtime(by having a base class pointer we can change the objects runtime). Correct me if i'm wrong. On Sun, Jun 26, 2011 at 7:13 AM, HowTechStuffWorks howtechstuffwo...@gmail.com wrote: Why Composition is said to be good ahead of inheritance. I am just learning C++ and it was said inheritance can be handled only by expert programmers, but I dont see anything like that. Can some one give me an example. Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: Sort - Consecutive Array in O(n)
My approach : 1. Find the median. 1.5 Check if the median is min + (max - min ) / 2. 2. Partition the array into two sub arrays using the partition function of quicksort. 3. Check if the subarrays also satisfy the constraint. Complexity : T(n) = 2 T(n/2) + O(1) :: O(nlogn) On Sat, Jun 25, 2011 at 12:15 PM, varun pahwa varunpahwa2...@gmail.comwrote: will this work. n size of array. cal (a[i] - min(arr) + 1). now cal sum of a[i], cal square sum of array as (a[i] * a[i]) , cal cube sum of array as (a[i] * a[i] * a[i]). now if array elements are consecutive then sum must be n * (n + 1) / 2. square sum must be (n * (n + 1) * (2n + 1) )/ 6 and cube sum must be (n * (n + 1) / 2) ^ 2. On Fri, Jun 24, 2011 at 11:00 PM, Adarsh s.adars...@gmail.com wrote: I think I got an work around for this if number of elements are not odd why not make them odd :) I variation to my prev algo int n = A.size(); for (int i=0; in; i++) total += A[i]; findMinMax(A[1...n]); //returns first smallest (fmin), second smallest (smin) and largest (max) element in array int fmean = (max+fmin)/2; int smean = (max+smin)/2; stotal = total - fmin; if ((total - n*fmean) == 0) { if ((stotal - n*smean) == 0) printf(consecutive\n); return; } printf(not consecutive\n); -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: rit2008...@iiita.ac.in Another Email :: varunpahwa.ii...@gmail.com People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] SET IN C
Disjoint set data structure. Refer cormen. On Fri, Jun 24, 2011 at 10:36 PM, hary rathor harry.rat...@gmail.comwrote: Can anyone suggest me how to implement a set in c . It means that it should take O(1) in insertion, deletion , finding element -- Harish Pranami Master Of Computer Application , Deptt of computer Science, north campus , university of delhi, New Delhi pin no - 110007 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Writing good code in interviews
Hey all, I want to know a quick list of things (positive and negative) looked in the code written during interviews. I think these are a couple of things to take care. 1. Writing compilable code is definitely good. 2. Variables and methods should indicate their need. Can you guys add more learnt from your experience ? -- regards, chinna. -- 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] Minimum draws for correct labels
Is it 4 draws if we were to identify them back ? On Tue, Jun 21, 2011 at 9:22 AM, Navneet Gupta navneetn...@gmail.comwrote: Nice..! On Tue, Jun 21, 2011 at 2:36 AM, oppilas . jatka.oppimi...@gmail.com wrote: Yes. One draw only. As all the box are incorrectly labeled so, box BW willl either contain 2Black or 2 white balls. We pick one ball from BW box. If it's white( it contains WW ball), then as the box label WW does not contain while, it can either have BB or BW ball. But it must have BB ball inside it otherwise, we will end up getting BB in correct labeled BB box. On Tue, Jun 21, 2011 at 12:11 AM, Radhika Renganathan radi.coo...@gmail.com wrote: one drawing ?! On 6/21/11, Navneet Gupta navneetn...@gmail.com wrote: IMAGINE THAT YOU have three boxes, one containing two black marbles, one containing two white marbles, and the third, one black marble and one white marble. The boxes were labeled for their contents-BB, WW and BW-but someone has switched the labels so that every box is now incorrectly labeled. You are allowed to take one marble at a time out of any box, without looking inside, and by this process of sampling you are to determine the contents of all three boxes. What is the smallest number of drawings needed to do this? --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- radhika .. :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Sum to K problem
@vaibhav : Please note that more than two numbers can sum upto k. On Mon, Jun 20, 2011 at 12:21 PM, vaibhav shukla vaibhav200...@gmail.comwrote: sort the array using merge sort : order nlogn take the first element,subtract it with 'k' , then search the result using binary search in rest of the array : order nlogn hence u get two elements which sum up to K in order nlogn On Mon, Jun 20, 2011 at 12:14 PM, Navneet Gupta navneetn...@gmail.comwrote: Right, in the worst case, complexity with be O(2^N). So what are the possible optimizations here? Would building pre-computed data structures with intermediate sum values help in finding such pairs in less complexity? I think then we can apply dynamic programming to find such pairs. On Mon, Jun 20, 2011 at 12:09 PM, oppilas . jatka.oppimi...@gmail.comwrote: I think its a NP problem. The solution complexity can go up O(2^N) in worst case. On Mon, Jun 20, 2011 at 11:55 AM, Navneet Gupta navneetn...@gmail.comwrote: Given a set of integers , find a set of numbers such that they sum to a given number k . Notice the set of numbers can have 2 or more than 2 numbers. --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- best wishes!! Vaibhav Shukla DU-MCA -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Minimum Rotations
@kk : Your approach looks like o(n^2) and only o(n) is likely to pass TLE. On Fri, Jun 17, 2011 at 5:38 PM, KK kunalkapadi...@gmail.com wrote: http://www.spoj.pl/problems/MINMOVE/ This code is showing TLE after some 20th test case what else can be optimized??? try: import psyco psyco.full() except ImportError: pass string = input() minlen = string length = len(string) string += string[:] #print(string) index = 0 for i in range(1, length): if string[i : i+length] minlen: minlen = string[i : i+length] index = i print(index) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] spoj problem acode
Link : https://www.spoj.pl/problems/ACODE/ 25114 BEAN’, ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ ‘BEKD’. How many different decodings?” My soln , but i get TLE.Please help. #include iostream #include cstdio #include vector using namespace std; char * head; int result[5001]; int count(char * a ,int size) { if(result[a-head]!=0){ return result[a-head]; } if(size==1) return 1; else if (size==2) { if(a[0]'2') return 1; else return 2; } else { int temp = count(a+1,size-1); if(a[0]'2' || (a[0]=='2' a[1]'6')) { result[a-head] = temp ; return temp; } else { int r = temp+count(a+2,size-2); result[a-head] = r; return r; } } } int main() { char ch; cinch; while(ch!='0') { char input[5001]; int index=0; while(ch!='\n') { //input.push_back(ch-'0'); input[index]=ch; index++; scanf(%c,ch); } cinch; head = input ; for(int i=0;i=5000;i++) result[i]=0; coutcount(input,index)endl; } return 0; } -- regards, chinna. -- 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] Admin of Group
+1 On Wed, May 25, 2011 at 11:48 PM, anuj agarwal coolbuddy...@gmail.comwrote: Hi, Are there any admins on this group? I recently joined this group and i liked the discussions going on here. But there is a problem which hurts is that unlike other groups which are moderated by certain admin guys (also active members of group), this one is not. So we are receiving lots of SPAMS. I guess no body wants to get a job from this group (specially ones which are sent by some Panzer). If the mods are reading this, Please take some action on that mails so that group will remain clean. Sorry for off topic. Anuj Agarwal Engineering is the art of making what you want from things you can get. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 Q
If we were given two strings and asked to check if they have the same characters (anagrams) : @ gene : you are sorting them both ,and trying to match. cost : sort the first string + sort the second string + compare i.e k * k + k * k + k .. k is the length of the string. I presume that bubble sort is nearly optimal for smaller strings if u consider the overall performance ( its O(n^2) but smaller constants than the O(nlogn) with larger constants in say quicksort. Rather i would suggest , take each character and check that in the other string. O( k * k) ..in the average case you might do even less than nearly O(k * k/ 2) if the two strings are not same. On Wed, May 18, 2011 at 10:31 AM, anuj agarwal coolbuddy...@gmail.comwrote: Same method as Gene told. Only enhancement u can made is start from the word nearer to sorted string and compare till the nearest word of the reverse of sorted string. You don't need to check the whole dictionary. Anuj Agarwal Engineering is the art of making what you want from things you can get. On Wed, May 18, 2011 at 6:01 AM, Gene gene.ress...@gmail.com wrote: Sort the characters in the string. Go through the dictionary sorting the characters in each word in turn. Print the words whose sorted versions match the sorted string. You can quickly print all equivalence classes of anagrams in the dictionary by hashing with the sorted strings as keys. It only takes a few seconds to get them all this way with a 2-line perl or ruby script. -- 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. -- regards, chinna. -- 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 Q
perfect. Thanks for the effort in explanation. On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com wrote: @Pacific: A balanced binary tree is commonly defined as a binary tree in which the height of the two subtrees of every node never differ by more than 1. Thus, there could be more nodes in one subtree than in the other. E.g., a balanced binary tree with 11 nodes could have 7 nodes in the left subtree and only 3 nodes in the right subtree. Thus, the root would not be the median. An additional condition is needed: the number of nodes in the left subtree differs by at most one from the number of nodes in the right subtree. In fact, given that the heap structure is a balanced binary tree structure with implicit pointers to the left and right subtrees, the two-heap algorithm I described results in a balanced binary tree satisfying this additional condition, with an implicit root node equal to the median. Dave On May 14, 11:55 am, pacific :-) pacific4...@gmail.com wrote: Will not a balanced binary tree do the job ? if we will pick the root each time for the median. On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote: @Ashish: The idea is to keep two heaps, a max-heap of the smallest half of the elements and a min-heap of the largest elements. You insert incoming elements into the appropriate heap. If the result is that the number of elements in the two heaps differs by more than 1, then you move the top element from the longer heap into the other one, thereby equalzing the number of elements. Thus, inserting an element is an O(log n) operation. To get the median, it is the top element of the longer heap, or, if the heaps are of equal length, it is the average of the two top elements. This is O(1). Dave On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote: not clear, can u elaborate.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com wrote: This problem can be solved using 2 heaps and the median can always be accessed in O(1) time ,the first node. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 Q
Will not a balanced binary tree do the job ? if we will pick the root each time for the median. On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote: @Ashish: The idea is to keep two heaps, a max-heap of the smallest half of the elements and a min-heap of the largest elements. You insert incoming elements into the appropriate heap. If the result is that the number of elements in the two heaps differs by more than 1, then you move the top element from the longer heap into the other one, thereby equalzing the number of elements. Thus, inserting an element is an O(log n) operation. To get the median, it is the top element of the longer heap, or, if the heaps are of equal length, it is the average of the two top elements. This is O(1). Dave On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote: not clear, can u elaborate.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com wrote: This problem can be solved using 2 heaps and the median can always be accessed in O(1) time ,the first node. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] first fit bin packing
i think we can use heaps for this problem..bring to the root which has capacity to hold and pick the root each time. If the root cannot accomodate then no other node will be able to accomodate. On Sat, May 14, 2011 at 1:26 AM, MK stardust...@gmail.com wrote: Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] exon chaining
Can you provide example input and output ? On Thu, May 12, 2011 at 9:32 AM, ganesha suresh.iyenga...@gmail.com wrote: Can some one help in finding out the bug in the below code. Input: (left,right,weight) representing intervals Output: maximum weight of non-overlapping intervals #include iostream #include vector #include math.h #include algorithm struct point { int value; bool isLeft; long int weight; int index; struct point* prev; }; typedef struct point* NODEPTR; bool compare (NODEPTR A,NODEPTR B) { return (A-value B-value); } int main() { int numIntervals; cin numIntervals; // read the intervals and sort the list vectorNODEPTR points; for (int i=0; i numIntervals; i++) { NODEPTR p1 = new point; p1-isLeft = true; p1-weight = 0; p1-prev = NULL; cin p1-value; points.push_back(p1); NODEPTR p2 = new point; p2-isLeft = false; p2-prev = p1; cin p2-value; cin p2-weight; points.push_back(p2); } sort(points.begin(),points.end(),compare); vectorNODEPTR::iterator it; int idx=1; for (it=points.begin(); it!=points.end(); ++it) { (*it)-index = idx++; } /*for (it=points.begin(); it!=points.end(); ++it) { if ((*it)-prev != NULL) cout (*it)-prev-value (*it)-value (*it)- weight (*it)-prev-index endl; }*/ int score[2*numIntervals + 1]; for (int i=0; i = 2*numIntervals; i++) { score[i] = 0; } int i = 1; for (it=points.begin(); it!=points.end(); ++it) { // right end of the interval if (false == (*it)-isLeft) { int j = (*it)-prev-index; int t1 = score[j] + (*it)-weight; int t2 = score[i-1]; if (t1 t2) score[i] = t2; else score[i] = t1; } else { score[i] = score[i-1]; } i++; } cout Max weight is score[2*numIntervals] 2*numIntervals 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. -- regards, chinna. -- 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]
Just a try for : You have a billion urls, where each has a huge page. How to you detect the duplicate documents? 1. Compute a simple hash for each of the document. 2. And for those docs where the hash matches , 3. use a different hash function and go back to step 1.. you might want to stop when u after a certain similarity. On Thu, May 5, 2011 at 7:33 PM, sourabh jakhar sourabhjak...@gmail.comwrote: You have a billion urls, where each has a huge page. How to you detect the duplicate documents? -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Finding subarray
myapproach( set S , sum s ) : Let all elements be set S and we need to find sum , s 1. for each element taken from the set ,e 2. now call the function recursively with myapproach( S - { e } , s - e ) and myapproach( S - {e } , s ) On Mon, Apr 11, 2011 at 3:17 PM, Subhransu subhransu.panigr...@gmail.comwrote: I didnt get the step 3. Could you please elaborate this(dry run be good to understand and bringing it for generic solution). Also how best the complexity will be . *Subhransu Panigrahi * *Mobile:* *+91-9840931538* *Email:* subhransu.panigr...@gmail.com On Mon, Apr 11, 2011 at 12:27 AM, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.com wrote: well i hav deviced a approach : well say we hav sorted array {-1 -3 2 3 3 5 9 13 24} say we hav to seach 6 take sum of all neg no store it -4 means we can atmost reduce any no by 4 units means in any case we cant take no greater than 10-4=6 for finding 6. now locate the upto position just less than we r searching for here 9 now sum up all positive upto 9 3+2+3+3+5 ie 16 now WE hav 3 sets (1) negative no sum (2) postive no less than requred sum (3) greater no set we can easily check here since only of this set less than 10 is useful so we hav 9 check for 9 -1 -3 here we get 6. either way we hav 16 -4 need some thing done here NOT PURE SOLN JUST AN IDEA THOUGH GOOD TO BE SHARE On Thu, Mar 31, 2011 at 1:06 AM, Subhransupanigrahi subhransu.panigr...@gmail.com wrote: could you please point to some similar I just want to validate the approach which I am thinking of. Sent from my iPhone On Mar 31, 2011, at 0:59, hammett hamm...@gmail.com wrote: We did :-) Dynamic programming seems as the best way to approach this kind of problem. On Wed, Mar 30, 2011 at 12:56 AM, Subhransu subhransu.panigr...@gmail.com wrote: For this X = {-1,4,2,3} Nearest will be 4 then remain is 1 but the there is no 1 so again in recursion nearest number is 2 then it search for suitable number where the sum is zero so 3 is not suitable then it will pick the next closest number to 2 which is one and make it (5= 4 + 2 -1 ) I just propose one approach you guys also can think a better one. Subhransu Panigrahi Mobile: +91-9840931538 Email: subhransu.panigr...@gmail.com On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath crazysai...@gmail.com wrote: @ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3} and your sum is 5. You will get nearest element 4, but there is no 1 in the set. A DP solution will be like this : Let a[i][j] be the 1 if using the first i elements we can get sum of j, and 0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1; Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith element of set X. On Wed, Mar 30, 2011 at 12:35 PM, hammett hamm...@gmail.com wrote: I'd try a tabular approach. Check dynamic programming. Samples like LCS may give you a click. On Tue, Mar 29, 2011 at 11:46 PM, Subhransu subhransu.panigr...@gmail.com wrote: set of integers in an array X that the sum equals a given number N Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3} Lets say the number 5 which can be formed in the following manner 5= 2 + 3 (the values from array). If there is no match it has to return invalid numbers. We also have to see the complexity of the solution. I thought of one approach but not sure if there is more approach where the complexity will be minimal. Lets say sort the array and now take number and find the closest number for that. Then in a recursion manner search for another( Lets say number '5', it search the list and found closest match will be 3. Then recursively search for 3 now where closest match is 2) Any algo with better complexity will be appreciated. Subhransu Panigrahi Email: subhransu.panigr...@gmail.com -- 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. -- Cheers, hammett http://hammett.castleproject.org/ -- 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
Re: [algogeeks] Re: Need help on Divide and Conquer Algorithm
a sort and another traversal would also do the same job in o( nlogn + n ) ?? On Fri, Apr 15, 2011 at 12:49 AM, vishwakarma vishwakarma.ii...@gmail.comwrote: complexity : O(n) + O(nlogn) Sweety wrote: Question :Let A[1..n] be an array of integers. Design an efficient divide and conquer algorithm to determine if A contains a majority element, i.e an element appears more than n/2 times in A. What is the time complexity of your algorithm? Answer: a[1..n] is an array int majorityElement(int a[], int first, int last) { If (first = = last) { return a[first]; // Array has one element and its count = 1 and it is major element } mid= (first+last)/2; (majorL,countL)= majorityElement(a,first,mid); (majorR,countR)= majorityElement(a,mid +1,last); n = total elements in an array; If(majorL==majorR) return(countL+countR); else { If(countLcountR) return(majorL,countL); elseif(countL countR) return(majorR,countR); else return(majorL,majorR); } if(countLn/2) temp1=majorL; if(countRn/2) temp2=majorR; If(temp1 = = temp2) return temp1; elseif(countLcountR) return temp1; else (countRcountL) return temp2; else return -1; } int main() { int a[8] = {2,3,2,2,4,2,2,2}; int first =1; int last=8; //change the value of last when the array increases or decreases in size int x = majorityElement(a,first,last); if(x= = -1) printf(“No Majority Element”) else Majority element = x; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 Interview Question
My approach : Have a pointer to the start (smallest of the array) of each of the N arrays. Until all pointers reach end of respective arrays : take the smallest value from all of the pointers and compute the difference between the smallest and the current pointers of each of the arrays let newdiff be the smallest among all the diffs if newdiff olddiff : olddiff = newdiff only advance the smallest number pointer Correctness : I believe that if the smallest difference occurs between a and b ,(a is smallest) you will come across that comparison and find the least. Complexity : 0(kn) , it should be the best because you atleast need to read all of the input. Please correct me if i'm wrong. On Mon, May 9, 2011 at 8:55 PM, bittu shashank7andr...@gmail.com wrote: see here let me know if anything wrong..?? http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-difference-between.html Thanks Regrads Shashank the Best Way to Escape From The problem is to Solve it Computer Science Engg. BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Need the algorithm or idea
You may have to use a trie and also the edit distance for this problem. Firstly , walk down the trie as you can keep matching the alphabets. When you encounter a first mismatch , findout the edit distance for the rest of the substring of the input with all of the strings possible from that node down to the leaves. Now output the one with the least edit distance as the correct spelling. You might want to keep a bound on the max edit distance and say no suggestions if edit distance exceeds that. On Tue, May 3, 2011 at 9:47 AM, Sathaiah Dontula don.sat...@gmail.comwrote: is it not EDIT DISTANCE (DP) problem ? Thanks regards, Sathaiah Dontula On Tue, May 3, 2011 at 9:03 AM, lichenga2404 lichenga2...@gmail.comwrote: The question in an interview. And I got lost with this one. Could you guys give some algorithm or idea on this ? Write a program that reads a large list of English words (e.g. from / usr/share/dict/words on a unix system) into memory, and then reads words from stdin, and prints either the best spelling suggestion, or NO SUGGESTION if no suggestion can be found. The program should print as a prompt before reading each word, and should loop until killed. Your solution should be faster than O(n) For example: shep sheep peepple people sheeple NO SUGGESTION The class of spelling mistakes to be corrected is as follows: Case (upper/lower) errors: inSIDE = inside Repeated letters: jjoobbb = job Incorrect vowels: weke = wake Any combination of the above types of error in a single word should be corrected (e.g. CUNsperrICY = conspiracy). If there are many possible corrections of an input word, your program can choose one in any way you like. It just has to be an English word that is a spelling correction of the input by the above rules. Final step: Write a second program that *generates* words with spelling mistakes of the above form, starting with correctly spelled English words. Pipe its output into the first program and verify that there are no occurrences of NO SUGGESTION in the output -- 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. -- regards, chinna. -- 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] Output of the code
ruby : putsIndia will win the worldcup 2011 On Mon, Mar 28, 2011 at 9:04 PM, shady sinv...@gmail.com wrote: python 2.6 print 'India will win the World Cup 2010' On Mon, Mar 28, 2011 at 8:45 PM, Praveen Kumar praveen97...@gmail.comwrote: Here is the correct program : #includeiostream using namespace std; int main() { while(true) { coutIndia will win the World Cup 2010endl; } return 0; } On Mon, Mar 28, 2011 at 8:42 PM, Praveen Kumar praveen97...@gmail.comwrote: true is a keyword representing 1 and false as 0. The program will print the line a single time. On Mon, Mar 28, 2011 at 11:13 AM, balaji a peshwa.bal...@gmail.comwrote: the code will give error as there is nothing called true defined. On Sun, Mar 27, 2011 at 10:38 PM, Umer Farooq the.um...@gmail.comwrote: Hi, Can anyone tell me the output of the following code? #include iostream.h int main() { .. if (true) .. cout Pakistan will win the WorldCup 2011\n; return 0; } -- Umer -- 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. -- A.Balaji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] RR Scheduling
You can solve this problem using Binary Indexed Trees. (copied from spoj forum) On Mon, Mar 21, 2011 at 3:09 PM, Terence technic@gmail.com wrote: In this problem, sum can be as large as 5*10^9. Try breaking the whole interval into several stages (no more than 2*N), each with a fixed amount of tasks. Then in each stage, the schedule is a simple loop: A B C D E A B C D E A B ... Process each stage in O(1) time, then the total time complexity is O(N). On 2011-3-21 17:32, saurabh singh wrote: using scanf and printf and still tle,I am not pretty sure how malloc or new arrays can speed up execution? On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal sm14it...@gmail.comwrote: use scanf n printf instead of cin n cout, malloc array of structures after reading value of n if working in c else use new in cpp rest i guess...is ok On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal ankitsamb...@gmail.com wrote: I worked on this problem but cud not get a more efficient algo than yours. Plz get back 2 me if u find a better algo. On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma akshatasharm...@gmail.com wrote: I tried to solve this problem https://www.spoj.pl/problems/RRSCHED/ I am getting TLE!! How can I improve my code?? #includeiostream #includestdio.h using namespace std; struct process { long time; int finished; long elapsed_time; }; int main() { long n,sum=0; cinn; struct process prss[5]; for(long i=0;in;i++) { scanf(%ld,prss[i].time); prss[i].finished=0; sum+=prss[i].time; } long index=0; for(long k=1;k=sum;k++) { while(prss[index].finished==1) index++; prss[index].time--; if(prss[index].time==0) { prss[index].finished=1; prss[index].elapsed_time=k; } index++; if(index==n) index=0; } for(long i=0;in;i++) printf(%ld\n,prss[i].elapsed_time); 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. -- Sanchit Mittal Second Year Undergraduate Computer Engineering Delhi College of Engineering ph- +919582414494 -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Reg. file I/O in unix
I have two questions : 1. How many files can a unix process open ( the same file and different files )? 2. How many processes can open the same file (in unix) ? -- regards, chinna. -- 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] Binary Tree to BST
I dont see any property of binary tree which u can take advantage of to convert the binary tree to a BST. On Tue, Mar 22, 2011 at 9:31 PM, Decipher ankurseth...@gmail.com wrote: Convert Binary tree to BST in 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: Print Hello
Does C struct have constructor ? On Fri, Mar 18, 2011 at 12:55 AM, Don dondod...@gmail.com wrote: int n = printf(Hello\n); int main() { } On Mar 17, 8:08 am, himanshu kansal himanshukansal...@gmail.com wrote: is there any way to print hello in c also wdout writing anythng in main() On Thu, Mar 17, 2011 at 6:34 PM, kunal srivastav kunal.shrivas...@gmail.com wrote: n...c does not support classes On Thu, Mar 17, 2011 at 6:10 PM, himanshu kansal himanshukansal...@gmail.com wrote: is this possible in c also On Wed, Mar 16, 2011 at 11:57 PM, Manikanta manikantabab...@gmail.comwrote: Thats right in C++. How about in C. On Mar 16, 9:44 pm, kumar anurag anurag.it.jo...@gmail.com wrote: @anurag good. On Wed, Mar 16, 2011 at 9:28 PM, Anurag atri anu.anurag@gmail.com wrote: #includeiostream using namespace std ; class a { public : a() { couthello;} }a1; int main() { } On Wed, Mar 16, 2011 at 8:25 PM, himanshu kansal himanshukansal...@gmail.com wrote: How can u print hello in a c/c++ program without writing a single word in main() function -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com . To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Anurag Atri -- 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. -- Kumar Anurag- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- thezeitgeistmovement.com -- 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. -- regards, chinna. -- 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] what to learn python or perl
I vote for python. On Wed, Mar 16, 2011 at 10:03 AM, kracekumar ramaraju kracethekingma...@gmail.com wrote: Hello Python vs Perl been battle for more than 20 years.Perl is been around 23+ years(not sure,people say 25 years pls check) and python for 21 years. Python would be my choice 1.Python achieves code readability. 2.Python can do what perl can do. more on this fight you can find here http://infohost.nmt.edu/~tcc/help/lang/python/vsperl.html http://www.linuxjournal.com/article/3882 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
My approach : partition(n) = 1 + partition(n-1) 2+partition(n-2) 3+partition(n-3) .. .. n-1+partition(1) n Assuming 1+2 and 2+1 as different. On Mon, Mar 14, 2011 at 11:53 PM, Aviral Gupta aviral@gmail.com wrote: you can use coin change problem as one of the solutions. Regards Aviral Gupta http://coders-stop.blogspot.com/ On Mar 14, 8:43 pm, Ralph Boland rpbol...@gmail.com wrote: On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers I suggest you 1) generate the numeric partitions of n. That's the lists of numbers in sorted order whose sum is n. e.g. The numeric partitions of 3 are: {(1,1,1), (1,2), 3} 2) For each partition generate its multiset permutations. Note: there is a formula for how many of sums of positive integers to n there are but I don't what it is. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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: An interesting question
1. do operation on all the values in each column and store it in the first row of each column 2. do operation on all the values in each row and store it in the first column of each row. (when writing at a[0][0] do operation with the value computed at 1.) 3. Now to find out the value at a[i][j] ,you need to do a[i][0] a[0][j] On Sun, Feb 27, 2011 at 12:03 PM, Rajnish rajnish.i...@gmail.com wrote: 1.) Traverse the whole matrix and replace each 0 value with -1. 2.) Traverse the matrix again,all the 1 values are replaced with 0 in the row and column of the index where a -1 value is found. 3.) Set all -1 values to zero and we have the output array. time complexity: O(n^2) space complexity: O(1) On Feb 27, 2:29 am, gaurav gupta 1989.gau...@googlemail.com wrote: A NxN binary matrix is given. If a row contains a 0 all element in the row will be set to 0 and if a column contains a 0 all element of the column will be set to 0. You have to do it in O(1) space. example : input array : 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 result array : 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Thanks Regards, Gaurav Gupta -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] GOOG: Design a circular buffer and write the code for the reader and writer routines
here is my approach. shared variables : in, out shared memory : buf[N] writer while(1) { while(in+1 % N ==out) { // waiting } buf[in+1]= input; in = in+1 % N } reader while(1) { while(out == in) { // waiting } output = buf[out] out = out+1 % N } On Tue, Feb 15, 2011 at 10:35 PM, Ashish Goel ashg...@gmail.com wrote: as i see this would need synchronization... anyone tried it so far? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 paper/...plz help..its urgent
thanks very much. On Sun, Jan 16, 2011 at 5:04 PM, Lakhan Arya lakhan.a...@gmail.com wrote: @pacific Sets of size 2 can have 2 elements common with set of size greater than 2. for example if set is (1,2) than it is adjacent to sets like (1,2,3) (1,2,4), (1,2,3,4...n) etc. So (1,2) is adjacent to (1,2,3), (1,2,4) etc. On Jan 16, 1:04 pm, pacific pacific pacific4...@gmail.com wrote: @Lakhan Why are you not considering sets of size 2 ? Because two sets of size two cannot have both of the elements as same. On Sat, Jan 15, 2011 at 9:39 PM, Lakhan Arya lakhan.a...@gmail.com wrote: @bittu I don't think answer of 6th question to be a) No. of vertices of degree 0 will be those who didnot intersect with any set i exactly 2 points. All sets of size greater than equal 2 must intersect with any other set having exactly 2 common elements between them in exactly 2 points. e.g if a set is (1,2) then it will be adjacent to (1,2,3) , (1,2,3,4) etc.. The sets of size 0 and 1 cannot intersect in 2 points so they all will be of degree 0. Number of Sets of size 0 --- 1 Number of Sets of size 1 --- n so Total number of vertices n+1. In the similar way number of connected components will be n+2. On Jan 15, 8:44 pm, bittu shashank7andr...@gmail.com wrote: 1.c U Can verify by putting n =I where I is positive integer value say n=5 try it out its so easy 2 a...what i have understood. as we know that formal grammar is defined as (N, Σ, P, S) so For instance, the grammar G with N = {S, A}, Σ = {a, b}, P with start symbol S and rules S → aA A → Sb S → ε generates { a^ib^i : =0} so answer is A. 3 expected value doe discrete distributional is defined as E(i)=sum(pi * xi); so from my points of view ans is 1/n ...Really Gud Question one has think..still thinking 4.b -Explaination Informally the NP-complete problems are the toughest problems in NP in the sense that they are the ones most likely not to be in P. NP- complete problems are a set of problems that any other NP-problem can be reduced to in polynomial time, but retain the ability to have their solution verified in polynomial time. In comparison, NP-hard problems are those at least as hard as NP-complete problems, meaning all NP- problems can be reduced to them, but not all NP-hard problems are in NP, meaning not all of them have solutions verifiable in polynomial time. (A) is incorrect because set NP includes both P(Polynomial time solvable) and NP-Complete . (B) is incorrect because X may belong to P (same reason as (A)) (C) is correct because NP-Complete set is intersection of NP and NP- Hard sets. (D) is incorrect because all NP problems are decidable in finite set of operations. 5. The Most Typical..Still Need Time 6 a zero degree means vertex is not connected from any other vertex in graph 7.a 8.No Answer Answer Comes to Be 252 15c10,14c9,10c5,10*9*8*7*6 all are greater then from output so say No Answer Correct Me if I am Wrong Next Time I will Try to provide the solution of 2nd, 5th problem ..explanations from-others are appreciated Thanks Regards Shashank Mani Don't B Evil U Can Earn while U Learn Computer Science Engg. BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 paper/...plz help..its urgent
@Lakhan Why are you not considering sets of size 2 ? Because two sets of size two cannot have both of the elements as same. On Sat, Jan 15, 2011 at 9:39 PM, Lakhan Arya lakhan.a...@gmail.com wrote: @bittu I don't think answer of 6th question to be a) No. of vertices of degree 0 will be those who didnot intersect with any set i exactly 2 points. All sets of size greater than equal 2 must intersect with any other set having exactly 2 common elements between them in exactly 2 points. e.g if a set is (1,2) then it will be adjacent to (1,2,3) , (1,2,3,4) etc.. The sets of size 0 and 1 cannot intersect in 2 points so they all will be of degree 0. Number of Sets of size 0 --- 1 Number of Sets of size 1 --- n so Total number of vertices n+1. In the similar way number of connected components will be n+2. On Jan 15, 8:44 pm, bittu shashank7andr...@gmail.com wrote: 1.c U Can verify by putting n =I where I is positive integer value say n=5 try it out its so easy 2 a...what i have understood. as we know that formal grammar is defined as (N, Σ, P, S) so For instance, the grammar G with N = {S, A}, Σ = {a, b}, P with start symbol S and rules S → aA A → Sb S → ε generates { a^ib^i : =0} so answer is A. 3 expected value doe discrete distributional is defined as E(i)=sum(pi * xi); so from my points of view ans is 1/n ...Really Gud Question one has think..still thinking 4.b -Explaination Informally the NP-complete problems are the toughest problems in NP in the sense that they are the ones most likely not to be in P. NP- complete problems are a set of problems that any other NP-problem can be reduced to in polynomial time, but retain the ability to have their solution verified in polynomial time. In comparison, NP-hard problems are those at least as hard as NP-complete problems, meaning all NP- problems can be reduced to them, but not all NP-hard problems are in NP, meaning not all of them have solutions verifiable in polynomial time. (A) is incorrect because set NP includes both P(Polynomial time solvable) and NP-Complete . (B) is incorrect because X may belong to P (same reason as (A)) (C) is correct because NP-Complete set is intersection of NP and NP- Hard sets. (D) is incorrect because all NP problems are decidable in finite set of operations. 5. The Most Typical..Still Need Time 6 a zero degree means vertex is not connected from any other vertex in graph 7.a 8.No Answer Answer Comes to Be 252 15c10,14c9,10c5,10*9*8*7*6 all are greater then from output so say No Answer Correct Me if I am Wrong Next Time I will Try to provide the solution of 2nd, 5th problem ..explanations from-others are appreciated Thanks Regards Shashank Mani Don't B Evil U Can Earn while U Learn Computer Science Engg. BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Explain anybody solution of Soduo Game is unique or Not......
On Sat, Jan 15, 2011 at 6:58 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: Hello.. Explain and write Algorithm for* Soduo Game* and also describe Solution is unique or Not. I think using a search algorithm like A* would work. if Anybody do you have C/C++ code please send to me. I dont have. Thanks and Regards Umesh kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Recursive Function For insertion in BST
#include stdio.h #include stdlib.h struct node { int a ; }; int insert(struct node * head ) { struct node * temp; temp= (struct node *) malloc(sizeof(struct node )); printf(temp in function %d \n,temp); head = temp; } int main() { struct node * temp; temp= (struct node *) malloc(sizeof(struct node )); printf( temp before function %d\n ,temp); insert(temp); printf( temp after function %d\n ,temp); } Output : temp before function 167862280 temp in function 167862296 temp after function 167862280 The assignment in the function insert to the head doesn't affect in the caller.I hope this example clears the doubt. I suggest an implementation like this , struct node * insert(struct node * head , int data ) which returns the head of the tree to the caller. Let me know if i'm wrong anywhere. On Sun, Jan 16, 2011 at 12:34 AM, juver++ avpostni...@gmail.com wrote: @above Of course, NO. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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] Adobe Question
Integers larger than which fit in 32/64 bits. On Thu, Jan 13, 2011 at 8:58 PM, bittu shashank7andr...@gmail.com wrote: 1. 10 test cases for entering 3 values representing sides of a triangle and the program giving output as scalene, isosceles or equilateral--Means At Least 10 2 .Question on a program that calculates P=R/I where R, I are integer inputs and P a floating point output. Write 10 test cases for thisAt Least 10 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. -- 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 paper/...plz help..its urgent
On Wed, Jan 12, 2011 at 2:44 PM, snehal jain learner@gmail.com wrote: 1. Quick-sort is run on two inputs shown below to sort in ascending order (i) 1,2,3, ….,n (ii) n, n - 1, n - 2, …., 2, 1 Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then, a) C1 C2 b) C1 C2 c) C1 = C2 d) We cannot say anything for arbitrary n 2. Which of the following languages over {0, 1} is regular? a) 0i1j such that i ≤ j b) 0iw1j such that w ∈ {0, 1}∗ and i ≥ 0 c) All strings of 0s and 1s such that every pth character is 0 where p is prime d) None of the above 3. We are given a set X = {x1, x2, ..., xn} where xi = 2i. A sample S (which is a subset of X) is drawn by selecting each xi independently with probability pi = 1 / 2. The expected value of the smallest number in sample S is: a) 1 / n b) 2 c) sqrt(n) d) n 4. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? a) R is NP-complete b) R is NP-hard c) Q is NP-complete d) Q is NP-hard 5. For any string s ∈ (0 + 1)*, let d(s) denote the decimal value of s (eg: d(101) = 5, d(011) = 3). Let L = {s ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 = 4}. Which of the following statements is true? a) L is recursively enumerable, but not recursive b) L is is recursive, but not context-free c) L is context-free, but not regular d) L is regular Common data for questions 6 and 7 The 2n vertices of a graph G corresponds to all subsets of a set of size n. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly 2 elements 6. The number of vertices of degree zero in G is: a) 1 b) n c) 2n - 1 d) None Nodes which dont have any edges are : subset of the given set of size 0 --- 1 subsets of the given set of size 1 --- n subsets of the given set of size 2 --- nc2 so answer is 1 + n + nc2. Since all subsets of size greater than 2 share atleast two elements with some other node. 7. The number of connected components in G is: a) 2n b) n + 2 c) n C 2 d) None I doubt if it is number of nodes of degree 0 + 1. 8. There are 5 nested loops written as follows, int counter = 0; for (int loop_1=0; loop_1 10; loop_1++) { for (int loop_2=loop_1 + 1; loop_2 10; loop_2++) { for (int loop_3=loop_2 + 1; loop_3 10; loop_3++) { for (int loop_4=loop_3 + 1; loop_4 10; loop_4++) { for (int loop_5=loop_4 + 1; loop_5 10; loop_5++) { counter++; } } } } } What will be the value of counter in the end (after all the loops finished running)? a) 15C5 b) 14C5 c) 10C5 d) 10 * 9 * 8 * 7 * 6 * 5 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Interview - Algorithms
At each location if the value is k , find the largest value in the next k elements and jump there. This greedy approach works in 0(n^2) and i believe it works. If not can someone give me a counter example ? On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu avi.du...@gmail.com wrote: @jammy Even I felt the same, but the greedy 'algo' u suggest is actually IMHO not a greedy approach. You just take each arr[i] and jump *without deciding a locally optimal policy* . SO, if u were to *see* arr[i] and *decide* on the optimal policy I feel one would follow d same steps as in a DP solution. Its only just that the implementation would be O(n^2). Just to add, this is the greedy approach I feel: greedy_min_steps[n] for i = 0; i n; i++: for (j = 0; j input[i]; j++) greedy_min_steps[ i + j ] = min(greedy_min_step[ i + j ], greedy_min_steps[ i ] + 1) this is the greedy approach I build and I see this being exactly similar to my DP approach. There are instances of greedy approach based algorithms which have *optimized* DP counter parts. I feel this problem is one of them. More ideas ? Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the scripture of this age. On Sat, Jan 15, 2011 at 2:14 AM, Jammy xujiayiy...@gmail.com wrote: @Avi Greedy approach doesn't work since you can't ensure the choice is locally optimum. Consider 3,9,2,1,8,3. Using greedy alg. would give you 3,1,8,3 while otherwise DP would give you 3,9,3. On Jan 14, 6:11 am, Avi Dullu avi.du...@gmail.com wrote: I guess u got confused with the comment I wrote, I have added 2 print statements and now I guess it should be clear to you as to why the code is O(n). The comment means that each element of the min_steps_dp will be ACCESSED only ONCE over the execution of the entire program. Hence the outer loop still remains O(n). The next_vacat variable if u notice is always incremental, never reset to a previous value. #includestdio.h #includestdlib.h #define MAX 0x7fff inline int min(int a, int b) { return a = b ? b : a; } int find_min_steps(int const * const input, const int n) { int min_steps_dp[n], i, temp, next_vacant; for (i = 0; i n; min_steps_dp[i++] = MAX); min_steps_dp[0] = 0; next_vacant = 1; // Is the index in the array whose min_steps needs to be updated // in the next iteration. for (i = 0; i n min_steps_dp[n - 1] == MAX; i++) { temp = i + input[i]; if (temp = n) { min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1); temp = n - 1; } else { printf(Updating min[%d] to %d \n, i + input[i], min_steps_dp[i] + 1); min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1); } if (temp next_vacant) { printf(i: %d \n, i); for (; next_vacant temp; next_vacant++) { printf(next_vacant: %d \n, next_vacant); min_steps_dp[next_vacant] = min(min_steps_dp[temp], min_steps_dp[next_vacant]); } } } for (i=0;in;printf(%d ,min_steps_dp[i++]));printf(\n); return min_steps_dp[n-1]; } int main() { int n, *input, i; scanf(%d,n); if ((input = (int *)malloc(n * sizeof(int))) == NULL) { return -1; } for (i = 0;i n; scanf(%d,input[i++])); printf(Minimum steps: %d\n,find_min_steps(input, n)); return 0; } Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the scripture of this age. On Fri, Jan 14, 2011 at 1:49 PM, Decipher ankurseth...@gmail.com wrote: I don't think the inner loop is executing only once . Kindly check it for this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner loop you will find that for same values of i(Outer index) inner loop is called. Its an O(n2) solution . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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
Re: [algogeeks] Re: Tejas Networks - Written Test
2. can this be done in the following manner ? print the preorder and inorder traversal of the tree and then you can build it back but for binary trees On Tue, Jan 11, 2011 at 1:12 PM, juver++ avpostni...@gmail.com wrote: 1. Any shortest path algorithms on graphs (Dijkstra, Bellman-Ford, Floyd). 2. Store it's edges while doing DFS. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Interview - Algorithms
doesn't greedy approach work here ? On Sun, Jan 9, 2011 at 8:00 PM, juver++ avpostni...@gmail.com wrote: It doesn't matter how to make transitions: from current position make all necessary moves, or determine all positions from which we can achieve i-th position. So your method is only the one of possible. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BT
Here is my pseudo code : check( node t1 , node t2 ) { if ( t1-data == t2-data) { return check( t1-left , t2-left ) check(t1-right, t2-right) ; } else { return check(t1-left , t2) || check(t1-right , t2); } } time complexity : o(n) because each node in t1 needs to be visited once.let me know if this works. On Sun, Jan 9, 2011 at 1:30 PM, Harshal hc4...@gmail.com wrote: @Nishaanth T1 has millions of nodes. Suppose all the nodes of T1 are equal to root of T2. Then u will have to check every where in T1. Putting height as constraint, u will have to check only those nodes whose height is equal to T2. It will reduce time complexity. Well m not able to think of better time complexity, another way would be: Find Height of T2 ... O(k) //k is no. of nodes in T2 Find Height of each node in T1... O(N) //N is no. of nodes in T1 now if p nodes in T1 have height same as T2, then we can find if a subtree rooted at any of those p nodes are identical to T2 in O(pk) time. Thus total time complexity: O(N) + O(k) + O(pk). correct me if I am 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Interview Question
here is my approach : Starting from the root node , if root node need to have a 1 ... if root is an and gate : flips = minflips for left child to have value 1 + minflips for the right child to have value 1 else flips = minimum of ( minflips for left child to have value 1 , minflips for right child to have value 1) For a leaf node , return 0 if the leaf has the value needed else return INFINITY.Also if at any internal node if it is not possible return INFINITY. On Tue, Dec 28, 2010 at 10:06 AM, Anand anandut2...@gmail.com wrote: @Terence. Could please elaborate your answer. Bottom up level order traversal helps to get the final root value but how to use it to find minimum flips needed to Obtain the desired root value. On Fri, Dec 24, 2010 at 1:56 AM, Terence technic@gmail.com wrote: Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. Regards Shashank Mani Narayan BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] palindrome
On Wed, Dec 22, 2010 at 12:11 PM, mo...@ismu mohan...@gmail.com wrote: if x is a 32 bit number if((x0x)==((x16)0x))) x's bit pattern is a polyndrome @snehal :Do you want to consider binary representation of 5 as 101 or ..0101 ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.