[algogeeks] Amazon Interview Q
We all knw hw to find a loop in a singly linked list (Using hare and tortoise method)..what if the linked list is a doubly linked list?can we do it smthn better than hare n tortoise method using the advantage of the doubly linked list? -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview question at NIT Warangal
@amitno it wont work..check it.. On Wed, Jul 27, 2011 at 10:07 PM, amit amit.codenam...@gmail.com wrote: This should be O(2^n) #include cstdio #include cstring using namespace std; int n; int sol[1000]; void solve(int pos, int k) { for(int i = 0; i k; i++) printf(%d, , sol[i]); putchar('\n'); for(int i = pos; i n; i++) { sol[k] = i+1; solve(i+1, k+1); } } int main() { scanf(%d, n); solve(0, 0); } On Jul 27, 8:33 pm, Ankur Garg ankurga...@gmail.com wrote: Hi The solution in the link is of complexity (n*2^n)) Does anyone know any better solution ? Regards Ankur On Tue, Jul 26, 2011 at 11:10 PM, rajeev bharshetty rajeevr...@gmail.comwrote: @Ankur The link does has a very good explanation. Nice solution :) On Tue, Jul 26, 2011 at 10:47 PM, Kunal Patil kp101...@gmail.com wrote: @Ankur Garg: Nice explanation at the link given by u... On Tue, Jul 26, 2011 at 10:35 PM, Ankur Garg ankurga...@gmail.com wrote: Check this http://codesam.blogspot.com/2011/03/find-all-subsets-of-given-set.html On Tue, Jul 26, 2011 at 9:41 PM, Vishal Thanki vishaltha...@gmail.comwrote: Here is the working code.. #include stdio.h #include stdlib.h int a[] = {1,2,3,4,5}; #define ARRLEN(a) (sizeof(a)/sizeof(a[0])) void print_comb(int len) { int tlen = len; int i, j, k; int al = ARRLEN(a); for (i = 0; i al; i++) { for (j=i+len-1; jal;j++) { for (k = i; k i+len-1; k++) { printf(%d , a[k]); } printf(%d\n, a[j]); } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); print_comb(len); return 0; } On Tue, Jul 26, 2011 at 5:18 PM, praneethn praneeth...@gmail.com wrote: check this link: *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/* On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Rajeev N B http://www.opensourcemania.co.cc -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https
Re: [algogeeks] Array question
Use stack On Tue, Jul 26, 2011 at 5:22 PM, Shikhar shikharko...@gmail.com wrote: Given an array of integers, for each element of the array, print the first number on the right side of the element which is smaller than it. print -1 is there is no such element. eg: 3,4,2,18,19,1,10 Ans: 2,2,1,10,10,-1,-1 O(n^2) solution is trivial. One solution could be: Insert the elements of the array in a binary search tree. The moment a node in the binary tree gets a left child, it is the element we are looking for. All the nodes in the right subtree of a node which has just received a left child can be assigned the value of the parents' left child as the first smaller element to the right. Thus, this solution is O(nlogn). Does this solution work for all possible cases of input? Is an O(n) solution possible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Array question
Sorry for the above mistakeits not O(n) On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Use stack On Tue, Jul 26, 2011 at 5:22 PM, Shikhar shikharko...@gmail.com wrote: Given an array of integers, for each element of the array, print the first number on the right side of the element which is smaller than it. print -1 is there is no such element. eg: 3,4,2,18,19,1,10 Ans: 2,2,1,10,10,-1,-1 O(n^2) solution is trivial. One solution could be: Insert the elements of the array in a binary search tree. The moment a node in the binary tree gets a left child, it is the element we are looking for. All the nodes in the right subtree of a node which has just received a left child can be assigned the value of the parents' left child as the first smaller element to the right. Thus, this solution is O(nlogn). Does this solution work for all possible cases of input? Is an O(n) solution possible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array question
@Shikhar 1) Push the first element to stack. 2) for i = 1 to n-1 a) temp =a[i] b) while(stack not empty) int x = pop(stack) if(xtemp) print(temp); else push(x,stack) break; c) push(temp,stack) 3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] AMAZON Q
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create another array ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1]. So the output of above should be {0,2,1,2,2,1,0} Time complexity : O(nlogn) use of extra space allowed. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] plzz explain
http://www.cprogramming.com/tutorial/size_of_class_object.html On 7/27/11, TUSHAR tusharkanta.r...@gmail.com wrote: 1. #includeiostream using namespace std; class abc { int x; static int y; }; main() { abc a; coutsizeof(a); coutsizeof(abc); } why o/p is 4 4 ??? 2. class abc { }; main() { abc ob; coutsizeof(ob); } why o/p is 1 ? some say o/p may vary from os to os .why ?? and what may be other o/p s ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Adove Question.........
initial call subset(a,n,r,0,0); printf(%d,count);//to know the value of nPr (no of subsets) * void subset(int a[],int n,int r,int j,int ind) { int i; if(ind==r) { printf({); for(i=0;iind;i++) printf(%d ,a[i]); printf(}\n); count++; } else if (indr) { for(i=j;in;i++) { swap(a[i],a[j]); subset(a,n,r,j+1,ind+1); swap(a[i],a[j]); } } }* -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 ques
http://www.ideone.com/4Rq51 -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] TREES
*A preorder of a complete binary tree is given in an array , prints its level order * -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Solve it
ya nitish above condition will do On 7/20/11, Nitish Garg nitishgarg1...@gmail.com wrote: I think: s[i] = max(s[i-2], s[i-2]+a[i], s[i-1], a[i]) should satisfy all the cases, even when all the numbers are negative. Pleas check. On Wed, Jul 20, 2011 at 12:44 AM, pnandy sayantan.nand...@gmail.com wrote: On Jul 19, 8:00 pm, ankit sambyal ankitsamb...@gmail.com wrote: @Nitish and Shubam : Since we trying to find sub sequence and not a sub string, so if there are negative nos. in the array, just neglect them. Piyush's algo will work perfectly.. Piyush's algo won't work for -ve nos. Consider an array -12 -10 5.answer should be 5 while the algo gives -7 as the answer. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Circle Circle more Circles .........
I would like to redefine my algo with cases clarified... Create a queue that is made to contain the points... say points queue [1000]; for i:1 to n for j:i+1 to n Calculate d (distance between the two centers) if (d = r0 + r1) keep them in two separate queues //the circles don't intersect if(d==0 || d= abs(r0-r1)) ignore the circle with smaller radius // one circle wholly contains another such that the borders do not overlap, or overlap exactly (e.g. two identical circles) else keep both of them in one single queue Now calculate the area of the circles in those queues which have single element... those with more than one element..calculate the area using simple geometry...You can take help of this.. http://mathworld.wolfram.com/Circle-CircleIntersection.html Hope its clear now... On 7/20/11, SAMMM somnath.nit...@gmail.com wrote: I doubth . For (d r0 + r1) ignore the point with smaller radius as it will overshadowed the bigger circle completely There may be a case where the circle is partially overlapped by the other circles. Then this algo will fail . The area will be of like these :- Suppose 3 circles are there X,YZ . Then the area will be :- Case1:- X+Y+Z Case2:- X+(YUZ) == Y + Z - (YnZ) --- intersection case3:- There circle can overlap ... like these . Then Will your algo work .. I guess 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Circle Circle more Circles .........
@Dumanshu..i am not partitioning them into just two queues... Moreover I just gave a raw idea...and yeah the complexity is in the order of n^2 only. There are many chances of improvement in it.. On Wed, Jul 20, 2011 at 5:30 PM, Dumanshu duman...@gmail.com wrote: @Piyush: Initially for partitioning the given circles into the 2 queues u r having an O(n^2) loop, so u are comparing each circle with every other. Now, it is possible that u have 3 or more circles A,B,C intersecting if i got ur algo correct, ur intersection queue will have AB, BC, CA. So, according to the geometry, u will find the areas. But this area would be different than the actual area for intersection of A,B,C. On Jul 20, 3:48 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: I would like to redefine my algo with cases clarified... Create a queue that is made to contain the points... say points queue [1000]; for i:1 to n for j:i+1 to n Calculate d (distance between the two centers) if (d = r0 + r1) keep them in two separate queues //the circles don't intersect if(d==0 || d= abs(r0-r1)) ignore the circle with smaller radius // one circle wholly contains another such that the borders do not overlap, or overlap exactly (e.g. two identical circles) else keep both of them in one single queue Now calculate the area of the circles in those queues which have single element... those with more than one element..calculate the area using simple geometry...You can take help of this.. http://mathworld.wolfram.com/Circle-CircleIntersection.html Hope its clear now... On 7/20/11, SAMMM somnath.nit...@gmail.com wrote: I doubth . For (d r0 + r1) ignore the point with smaller radius as it will overshadowed the bigger circle completely There may be a case where the circle is partially overlapped by the other circles. Then this algo will fail . The area will be of like these :- Suppose 3 circles are there X,YZ . Then the area will be :- Case1:- X+Y+Z Case2:- X+(YUZ) == Y + Z - (YnZ) --- intersection case3:- There circle can overlap ... like these . Then Will your algo work .. I guess 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 ques
@Anika..can u give one example?? On 7/21/11, Anika Jain anika.jai...@gmail.com wrote: write a c code that takes a 32 bit ip address n prints it in dotted notation as a.b.c.d. The code shall work for big endian as well as for little endian.. In this how can i make it common for big endian and little endian?? if in little endian my lower order 8 bits shall be d but for big endian they shall be a.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Question!
unsigned int reverse_bits (unsigned int n) { if(n==1) return n; int j,p; for(j = 31;j0;j--) if(n(1j)) break; //to find the first set bit from left p =0; while(jp) { int x1 = (n (1j))j; int x2 = (n(1p))p; if(x1!=x2) { if(x1) { n = ~(1j);//unset the jth bit n |= (1p); //set the pth bit } else { n = ~(1p); //unset the pth bit n |= (1j); //set the jth bit } } j--;p++; } return n; } On 7/21/11, archita kool.arc...@gmail.com wrote: How to reverse the order of bits of a number in minimum space complexity? if the no is 11-1011 the output should b 1101. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Memory Allocation
char a[] or any array refers to a block of memory (not a single memory location or variable). Analogy to this can be seen in the following fact :- The memory addresses of an array can't be changed, whereas the content of the pointer variables, such as the base memory address of the array it refers to or simply any variable can be changed. Hence an undefined result persists..if we really want to return an array from a function we use the following syntax.. *char a[] = Hello; char *b = (char *)malloc(strlen(a)+1); strcpy(b,a); return b;* here we are returning the base address of the character array, unlike as wat you were doing previously(previously you were trying to return a block of memory) Hope it is clear now... :) -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] INFINITY
*printf(%c\n,236);* On Tue, Jul 19, 2011 at 2:45 PM, SAMMM somnath.nit...@gmail.com wrote: Print the symbol ∞ (INFINITY) through code . Unicode .. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: INFINITY
In Dev C it does On Tue, Jul 19, 2011 at 3:08 PM, SAMMM somnath.nit...@gmail.com wrote: It doesn't display the infinity symbol. On Jul 19, 2:24 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: *printf(%c\n,236);* On Tue, Jul 19, 2011 at 2:45 PM, SAMMM somnath.nit...@gmail.com wrote: Print the symbol ∞ (INFINITY) through code . Unicode .. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
*node *middle(node *head) { node *mid; mid = head; for(int i = 2;head!=NULL;head=head-next,i++) { (i%2==1) mid = mid-next; } return mid; }* To find 1/3rd of a list, change (i%2==1) to (i%3==1)i.e. nth node can be found (i%n==1) (make sure n=no. of nodes) Now to find 3/4th of a node, we can do following initial call *threefourth(head,3,4);* *node *threefourth(node *head,int m,int n) { node *mid,*p; p = head-next; mid = head; while(m) { for(int i = 2;p!=NULL;p=p-next,i++) { (i%n==1) mid = mid-next; } m--; if(m==0) return mid; else mid = mid-next; p = head-next; } }* -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Ignore my previous post for find the 3/4th...its actually traversing the list thriceso it better you traverse the list once and find the number of nodes in it...then then traverse 3/4th times the number of nodes... But the algo given by me is efficient if we are required to compute 1/nth of a node... -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Solve it
I hope it can be solved using DP...check my algo below and give any counter case if you get it... 1. Make an array S equal to the length of the given array where S[0] = a[0] and S[1] = max(a[0],a[1]) 2. for i:2 to n-1 S[i] = max(S[i-2]+a[i], S[i-1]) 3. return S[n-1] Hope the above algo works... On Tue, Jul 19, 2011 at 2:59 PM, sagar pareek sagarpar...@gmail.com wrote: Given an array all of whose elements are positive numbesr, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjecent in the array. eg:- 3 2 7 10 should return (sum of 3 and 10) 3 2 5 10 7 should returnn 15 (sum of 3,5,7) -- **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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Solve it
I think 6+4+3 6+4+2 On Tue, Jul 19, 2011 at 4:30 PM, sagar pareek sagarpar...@gmail.com wrote: Piyush sorry dude but this will not work say original array be 6 8 4 1 2 3 then ur new array be 6 8 10 10 12 13 //but original answer is 12 On Tue, Jul 19, 2011 at 3:49 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: I hope it can be solved using DP...check my algo below and give any counter case if you get it... 1. Make an array S equal to the length of the given array where S[0] = a[0] and S[1] = max(a[0],a[1]) 2. for i:2 to n-1 S[i] = max(S[i-2]+a[i], S[i-1]) 3. return S[n-1] Hope the above algo works... On Tue, Jul 19, 2011 at 2:59 PM, sagar pareek sagarpar...@gmail.comwrote: Given an array all of whose elements are positive numbesr, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjecent in the array. eg:- 3 2 7 10 should return (sum of 3 and 10) 3 2 5 10 7 should returnn 15 (sum of 3,5,7) -- **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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
are the sizes of the two arrays same?? On 7/19/11, swetha rahul swetharahu...@gmail.com wrote: Hi, Find the kth smallest element in O(logk) given 2 sorted arrays. Merging the arrays is not allowed. I can do it in O(k).. How to do in O(logk).. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 ques
Divisibility of 3 of numbers in base 2 can be seen same as divisibility of numbers by 11 in base 10... maintain two variable even_sum odd_sum, both initialized to 0 when an odd location in the number is set increment odd_sum when an even location in the number is set increment even_sum if(abs(even_sum-odd_sum)%3==0) number is divisible by 3... Hence keep the track of even_sum and odd_sum as the bits are getting appended.. Hope I am clear... :) On 7/19/11, sudhanshu pandey sud.nit...@gmail.com wrote: use automata theory. draw dfa for divisibility by 3.. On Tue, Jul 19, 2011 at 11:23 PM, siva viknesh sivavikne...@gmail.comwrote: Given an infinite stream of bits with bits being appended at the highest significant position. Give an algorithm to say whether the number formed by sequence of bits that had been processed till then , is divisible by 3 or not ? My sol: have a variable sum...find the sum of bitswhenever u add a bit do sum+=bit value ... check whether sum%3==0. Is my solution ok?? anyother good solutions ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SUDHANSHU PANDEY --only fair thing in this world is a chance-- -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Circle Circle more Circles .........
Just a simple thoughtI am assuming all points are unique Create a queue that is made to contain the points... say points queue [1000]; for i:1 to n for j:i+1 to n Calculate d (distance between the two centers) if (d = r0 + r1) keep them in two separate queues if(d r0 + r1) ignore the point with smaller radius //as it will overshadowed the bigger circle completely keep both of them in one single queue Now calculate the area of the circles in those queues which have single element... those with more than one element..calculate the area using simple geometry... Hope the above algo is clear... On 7/19/11, SAMMM somnath.nit...@gmail.com wrote: See the input will be :- 6 No of circles x1 y1 R1 x2 y2 R2 x3 y3 R3 x4 y4 R4 x5 y5 R5 x6 y6 R6 Output:- Area occupied by the above circles (one line) 4 decimal points . On Jul 19, 9:01 pm, priyanka goel priya888g...@gmail.com wrote: can u pl tell wat is dis x y coordinate? are dey centre coordinates or any point on circumference of circle.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
It can be done using one extra array only that is the output array out[] *int out = (int *)malloc(sizeof(n)); //n is the number of elements in a int i,temp = 1; for(i=0;in;i++) { out[i] = temp; temp*=a[i]; } temp =1; for(i=n-1;i=0;i--) { out[i] *= temp; temp*=a[i]; }* On Sun, Jul 17, 2011 at 4:43 PM, manish patel manispatel...@gmail.comwrote: thanx the question was asked by MS today in MNNIT. On Sun, Jul 17, 2011 at 4:35 PM, Anurag Aggarwal anurag19aggar...@gmail.com wrote: take two extra arrays b[] and c[] in b[] store the following thing b[0]=1; b[i]=b[i-1]*a[i-1]; in c[] store following things c[n-1]=1; c[i]=c[i+1]*a[i+1] (in-1) fill the c[] array in reverse order i.e. start from n-1 then go to 0; now output[] would be output[i]=b[i]*c[i]; On Sun, Jul 17, 2011 at 4:28 PM, geek forgeek geekhori...@gmail.comwrote: given an array a[0..n-1] .required to find the output array out [0.n-1] such that out [i] is the product of all the numbers a[0] to a[n-1] excluding a[i] for ex out[2]=a[0]*a[1]*a[3]*a[4]a[n-1] constraint is not using division operator how to do this in O(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. Anurag Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Manish Patel BTech 2nd Year Computer Science And Engineering National Institute of Technology -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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Use linked list for designing big int class On Sun, Jul 17, 2011 at 5:17 PM, sourabh jakhar sourabhjak...@gmail.comwrote: 10 c output question . questions were moderate type but negative marking +3 and -2.(30 min) coding round.(45 min) 1.array simple question d.p 2.test cases of notepad 3.Design Big Int class in C or c++ On Sun, Jul 17, 2011 at 5:14 PM, Harshal hc4...@gmail.com wrote: @manish, can you please tell other questions asked by ms today? On Sun, Jul 17, 2011 at 4:53 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: It can be done using one extra array only that is the output array out[] *int out = (int *)malloc(sizeof(n)); //n is the number of elements in a int i,temp = 1; for(i=0;in;i++) { out[i] = temp; temp*=a[i]; } temp =1; for(i=n-1;i=0;i--) { out[i] *= temp; temp*=a[i]; }* On Sun, Jul 17, 2011 at 4:43 PM, manish patel manispatel...@gmail.comwrote: thanx the question was asked by MS today in MNNIT. On Sun, Jul 17, 2011 at 4:35 PM, Anurag Aggarwal anurag19aggar...@gmail.com wrote: take two extra arrays b[] and c[] in b[] store the following thing b[0]=1; b[i]=b[i-1]*a[i-1]; in c[] store following things c[n-1]=1; c[i]=c[i+1]*a[i+1] (in-1) fill the c[] array in reverse order i.e. start from n-1 then go to 0; now output[] would be output[i]=b[i]*c[i]; On Sun, Jul 17, 2011 at 4:28 PM, geek forgeek geekhori...@gmail.comwrote: given an array a[0..n-1] .required to find the output array out [0.n-1] such that out [i] is the product of all the numbers a[0] to a[n-1] excluding a[i] for ex out[2]=a[0]*a[1]*a[3]*a[4]a[n-1] constraint is not using division operator how to do this in O(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. Anurag Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Manish Patel BTech 2nd Year Computer Science And Engineering National Institute of Technology -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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Regards, Harshal Choudhary 7th Semester, CSE Dept. NIT Surathkal, India. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
@Saurabh...ya true buddy...using malloc and realloc functions...gr88 On Sun, Jul 17, 2011 at 5:24 PM, sourabh jakhar sourabhjak...@gmail.comwrote: we can also use dynamically allocated array where they contain the digits of number and than apply the operation it is a better option i think as we can go to any index in 0(1) time. On Sun, Jul 17, 2011 at 5:19 PM, Harshal hc4...@gmail.com wrote: thanks sourabh :) On Sun, Jul 17, 2011 at 5:17 PM, sourabh jakhar sourabhjak...@gmail.comwrote: 10 c output question . questions were moderate type but negative marking +3 and -2.(30 min) coding round.(45 min) 1.array simple question d.p 2.test cases of notepad 3.Design Big Int class in C or c++ On Sun, Jul 17, 2011 at 5:14 PM, Harshal hc4...@gmail.com wrote: @manish, can you please tell other questions asked by ms today? On Sun, Jul 17, 2011 at 4:53 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: It can be done using one extra array only that is the output array out[] *int out = (int *)malloc(sizeof(n)); //n is the number of elements in a int i,temp = 1; for(i=0;in;i++) { out[i] = temp; temp*=a[i]; } temp =1; for(i=n-1;i=0;i--) { out[i] *= temp; temp*=a[i]; }* On Sun, Jul 17, 2011 at 4:43 PM, manish patel manispatel...@gmail.com wrote: thanx the question was asked by MS today in MNNIT. On Sun, Jul 17, 2011 at 4:35 PM, Anurag Aggarwal anurag19aggar...@gmail.com wrote: take two extra arrays b[] and c[] in b[] store the following thing b[0]=1; b[i]=b[i-1]*a[i-1]; in c[] store following things c[n-1]=1; c[i]=c[i+1]*a[i+1] (in-1) fill the c[] array in reverse order i.e. start from n-1 then go to 0; now output[] would be output[i]=b[i]*c[i]; On Sun, Jul 17, 2011 at 4:28 PM, geek forgeek geekhori...@gmail.com wrote: given an array a[0..n-1] .required to find the output array out [0.n-1] such that out [i] is the product of all the numbers a[0] to a[n-1] excluding a[i] for ex out[2]=a[0]*a[1]*a[3]*a[4]a[n-1] constraint is not using division operator how to do this in O(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. Anurag Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Manish Patel BTech 2nd Year Computer Science And Engineering National Institute of Technology -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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Regards, Harshal Choudhary 7th Semester, CSE Dept. NIT Surathkal, India. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- Best Regards, Harshal Choudhary 7th Semester, CSE Dept. NIT Surathkal, India. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group
Re: [algogeeks] MS Ques
check my code below...it works for all cases * **node *MUL(node *h1,node *h2) { node *h3,*p,*r; h1 = reverse(h1); h2 = reverse(h2); h3 = multiply(h1,h2-data); h2 = h2-next; p = h3; while(h2) { r = multiply(h1,h2-data); p-next = add(p-next,r); p = p-next; h2 = h2-next; } h3 = reverse(h3); return h3; } **node *multiply(node *h,int x) { node *head = NULL; node *p; int mul,carry=0; while(h) { if(!head) { head = (node *)malloc(sizeof(node)); mul = (x*(h-data)); carry = mul/10; mul=mul%10; head-data=mul; head-next = NULL; p = head; } else { p-next = (node *)malloc(sizeof(node)); p = p-next; p-next = NULL; mul = (x*(h-data)); p-data = (mul%10)+carry; carry = mul/10; } h = h-next; } if(carry) { p-next = (node *)malloc(sizeof(node)); p = p-next; p-next = NULL; p-data = carry; } return head; } node * add(node *h1,node *h2) { node *h3 = NULL; node *p; int sum,carry = 0; while(h1) { sum = h1-data+h2-data+carry; carry = sum/10; sum = sum%10; if(h3==NULL) { h3 = (node *)malloc(sizeof(node)); h3-data = sum; h3-next = NULL; p =h3; } else { p-next = (node *)malloc(sizeof(node)); p = p-next; p-next = NULL; p-data = sum; } h1 = h1-next; h2 = h2-next; } while(h2) { p-next= (node *)malloc(sizeof(node)); p = p-next; p-next = NULL; sum = h2-data + carry; carry = sum/10; sum = sum%10; p-data = sum; h2 = h2-next; } if(carry) { p-next = (node *)malloc(sizeof(node)); p = p-next; p-next = NULL; p-data = carry; } return h3; } * On Mon, Jul 18, 2011 at 2:34 AM, aditi garg aditi.garg.6...@gmail.comwrote: and 6 is carry forwarded??? next node wud be 6*7=42+6=48 8 and 4 carry? On Mon, Jul 18, 2011 at 2:28 AM, hary rathor harry.rat...@gmail.comwrote: sorry 7*9=63 put 3 in list 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi 9718388816 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 output problem
the output will be (b) before looking for the reason, you should know the syntax of printf *int printf(const char *format,)* the function at the string after the comma operator only if the format string aks for any format specifier like %d or %f etc...u can try it like this also in normal main function *printf(piyush,sinha); *It wil compile and run successfully...and u can guess the output too :) * * On Mon, Jul 18, 2011 at 2:19 AM, aditi garg aditi.garg.6...@gmail.comwrote: #includestdio.h #define FUN(arg) do\ {\ if(arg)\ printf(have fun...,\n);\ } while(i--) void main() {int i=2; FUN(i3); } A.have fun.. have fun.. have fun.. B.have fun..have fun..have fun.. C.Error : cannot use instructions in macro D.No 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Adding w/o +
we are basically assigning address value a to a char pointer p..(the reason y char pointer is used u will get to know it at the end) we know p[b] means *(p+b)then p[b] means *(p+b) i.e. p+b i.e a+b we used char pointer to increment it one by one..had we used int pointer.. it wud have incremented it +4*b. there is another way of doing it *printf(%d\n,printf(%*c%*c,a,,b,)); * On Wed, Jul 13, 2011 at 1:52 PM, nicks crazy.logic.k...@gmail.com wrote: if someone has better idea...then please suggest that. plz explain how this is calculating sum -- sum= (int)p[b]; On Wed, Jul 13, 2011 at 1:50 PM, nicks crazy.logic.k...@gmail.com wrote: I am looking for a code which can add without using + sign i searched the net and found the following code..can anyone explain me whats happening in this ?? #includestdio.h #includeconio.h int main() { int a=3000,b=20,sum; char *p; p=(char *)a; sum= (int)p[b]; //adding a b printf(Answer is :); printf(%d,sum); 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 code bst mirror prob
Its working I guess in both the cases... On 7/14/11, Anika Jain anika.jai...@gmail.com wrote: can some body tell me that: void swap(node *p,node *q) { node *t; t=p; p=q; q=t; } void mirror(node *p) { if (p==NULL) return; else {mirror(p-r); mirror(p-l); swap(p-r,p-l); } } in this the swapping is occuring but if i do : void mirror(node *p) { if (p==NULL) return; else {mirror(p-r); mirror(p-l); node *t; t=p-r; p-r=p-l; p-l=t; } } here it is not getting done .. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: BST
If we dont want the tree back, we can convert the BST to DLL and do the job.. On Mon, Jul 11, 2011 at 3:01 PM, aanchal goyal goyal.aanch...@gmail.comwrote: Given a BST and integer value K. Find all pairs of nodes (x,y), such that x-data + y-data = K Time O(n) Can someone provide a pseudocode/code to solve this using the concept of inorder and reverse inorder traversal of BST? PS: please don't post other solutions for this, I know this can be solved in other ways too. I am not able to code this using the above concept.. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
@Dk..i dint frame the question buddy...:P I found it over here http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-75 On Mon, Jul 11, 2011 at 3:14 PM, DK divyekap...@gmail.com wrote: @Sunny: Thanks for this counterexample. The O(N) algorithm currently seems unfeasible to me. @Piyush: Are you sure an O(N) algo exists? Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's algo as it doesn't generate duplicates) For arrays A = a1 a2 ... an B = b1 b2 bn Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this). Insert (an, bn). Repeat N Times { Pop off and output the max value from the priority queue. Let that be (ai, bj) // O(log N) if(i == j) { Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. // O(log n) } else if(i j) { Insert (ai-1, bj) in the priority queue. // O(log n) } else { Insert (ai, bj-1) in the priority queue. // O(log n) } } Time complexity: O(N log N) Space complexity: O(N) ?? -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/XCjyFaTFD-UJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: BST
@AanchalI think my following algo will work..its a modification of Morris traversal...check if you can find any bug in it...I have tried my best to make it error free..For further details regarding Morris traversal, check out http://geeksforgeeks.org/?p=6358 *void findsum(node *T,int key) { int n = countnodes(T);//returns the number of nodes in the BST int i=0; int j=n-1; node *cur1,*cur2,*p1,*p2; cur1=cur2=T; int flag1,flag2,sum; flag1=flag2=1; while(ij) { if(cur1-left == NULL cur2-right == NULL) { sum = checksum(cur1,cur2,key); if(sum==0) //if cur1-data + cur2-data ==key { i++;j--; flag1=flag2=1; cur1 = cur1-right; cur2 = cur2left; } if(sum0) //if cur1-data + cur2-data key { cur2 = cur2-left; flag1 = 0; //do not do anything with the left traversal j--; } if(sum0) //if cur1-data + cur2-data key { cur1 = cur1-right; flag2 = 0;//do not do anything with the right traversal i++; } } else { if(flag1 cur1-left!=NULL) { p1 = cur1-left; while(p1-right!=NULL p1-right!=cur1) p1 = p1-right; if(p1-right == NULL) { p1-right = cur1; cur1 = cur1-left; } } if(flag2 cur2-right!=NULL) { p2 = cur2-right; while(p2-left!=NULL p2-left!=cur2) p2 = p2-left; if(p2-left == NULL) { p2-left = cur2; cur2 = cur2-right; } } if(p1-right == cur1 || p2-left == cur2) { sum = checksum(cur1,cur2,key); if(sum==0) //if cur1-data + cur2-data ==key { if(cur1-left == NULL) { cur1 = cur1-right; flag1 = 0; } else if(p1-right == cur1) { p1-right = NULL; cur1 = cur1-right; flag1 = 1; } if(cur2-right == NULL) { cur2 = cur2-left; flag2 = 0; } else if(p2-left == cur2) { p2-left = NULL; cur2 = cur2-left; flag2 = 1; } i++;j--; } if (sum0) //if cur1-data + cur2-data key { if(cur1-left == NULL) { cur1 = cur1-right; flag1 = 0; } else if(p1-right == cur1) { p1-right = NULL; cur1 = cur1-right; flag1 = 1; } i++; } if(sum0)//if cur1-data + cur2-data key { if(cur2-right == NULL) { cur2 = cur2-left; flag2 = 0; } else if(p2-left == cur2) { p2-left = NULL; cur2 = cur2-left; flag2 = 1; } j--; } } } } //final correction of the links can be done again } int checksum ( node *c1,node *c2,int key) { if(c1-data+c2-data == key) return 0; else if(c1-data+c2-data key) return 1; else return -1; }* -- *Piyush Sinha* *IIIT, Allahabad* ** *+91-7483122727* *Never say NEVER https://www.facebook.com
Re: [algogeeks] MS: BST
@Anchalthanks for pointing out the error...i found where the error is...it is the else loop in this line in this checking... if(p1-right == cur1 || p2-left == cur2) actually before i have already assigned p1-right == cur1 (or p2-left=cur2)..it shud have been in else loop..soryy for the mistake..i will submit the modification asap.. On 7/11/11, aanchal goyal goyal.aanch...@gmail.com wrote: @Piyush.. I tried your algo on BST {5,4,6,3,2,1,8,7,10,12,9,11}. Its only returning 1+7. Other pairs are 5+3, 6+2. On Mon, Jul 11, 2011 at 6:56 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @AanchalI think my following algo will work..its a modification of Morris traversal...check if you can find any bug in it...I have tried my best to make it error free..For further details regarding Morris traversal, check out http://geeksforgeeks.org/?p=6358 *void findsum(node *T,int key) { int n = countnodes(T);//returns the number of nodes in the BST int i=0; int j=n-1; node *cur1,*cur2,*p1,*p2; cur1=cur2=T; int flag1,flag2,sum; flag1=flag2=1; while(ij) { if(cur1-left == NULL cur2-right == NULL) { sum = checksum(cur1,cur2,key); if(sum==0) //if cur1-data + cur2-data ==key { i++;j--; flag1=flag2=1; cur1 = cur1-right; cur2 = cur2left; } if(sum0) //if cur1-data + cur2-data key { cur2 = cur2-left; flag1 = 0; //do not do anything with the left traversal j--; } if(sum0) //if cur1-data + cur2-data key { cur1 = cur1-right; flag2 = 0;//do not do anything with the right traversal i++; } } else { if(flag1 cur1-left!=NULL) { p1 = cur1-left; while(p1-right!=NULL p1-right!=cur1) p1 = p1-right; if(p1-right == NULL) { p1-right = cur1; cur1 = cur1-left; } } if(flag2 cur2-right!=NULL) { p2 = cur2-right; while(p2-left!=NULL p2-left!=cur2) p2 = p2-left; if(p2-left == NULL) { p2-left = cur2; cur2 = cur2-right; } } if(p1-right == cur1 || p2-left == cur2) { sum = checksum(cur1,cur2,key); if(sum==0) //if cur1-data + cur2-data ==key { if(cur1-left == NULL) { cur1 = cur1-right; flag1 = 0; } else if(p1-right == cur1) { p1-right = NULL; cur1 = cur1-right; flag1 = 1; } if(cur2-right == NULL) { cur2 = cur2-left; flag2 = 0; } else if(p2-left == cur2) { p2-left = NULL; cur2 = cur2-left; flag2 = 1; } i++;j--; } if (sum0) //if cur1-data + cur2-data key { if(cur1-left == NULL) { cur1 = cur1-right; flag1 = 0; } else if(p1-right == cur1) { p1-right = NULL; cur1 = cur1-right; flag1 = 1; } i++; } if(sum0)//if cur1-data + cur2-data key { if(cur2-right == NULL) { cur2 = cur2-left; flag2
Re: [algogeeks] MS: BST
; else if(c1-data+c2-data key) return 1; else return -1; }* -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
using a temp variable is considered to be the best option.. On 7/11/11, Dave dave_and_da...@juno.com wrote: @Vaibhav: Your method b doesn't work for floating point numbers because they have finite precision. E.g.,as an extreme example, try it on a = 1 and b = 1d-25. When you form a+b, the result is 1, not 1 + 1d-25. Then 1 - 1d-25 gives 1 (which is correct), and 1 - 1 = 0. The latter should be 1d-25, so you have a total loss of precision in that number. More common would be just a partial loss of precision. Dave On Jul 10, 3:55 pm, vaibhav shukla vaibhav200...@gmail.com wrote: On Mon, Jul 11, 2011 at 1:51 AM, aanchal goyal goyal.aanch...@gmail.comwrote: These are the various ways to swap 2 variables a) Using temporary Variable always inefficient. using extra memory. b) Usnig some Arithmentic operation works for all numbers even floating points a and b are two no. to swap : a=a+b; b=a-b; a=a-b; always works c) Using bitwise XOR operation since bitwise results an error in floating point numbers so this method also fails. hence (b) is better among the three.what say ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] BIT MANIPULATION
I found a good question to try for bit manipulation.Try it... :) Given an integer x, find out the smallest integer which has same number of set bits as x and is greater than x. For example if the input integer is 12 (1100) then your function should return 17(10001). If the input integer is 3(11) then your function should return 5(101) -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: BIT MANIPULATION
@Dave..canu u explain ur algo to approach this formula?? On 7/10/11, Dave dave_and_da...@juno.com wrote: @Piyush: See http://groups.google.com/group/algogeeks/msg/2b64c4f96fa3598e for a one-line algorithm. Dave On Jul 9, 4:23 am, Piyush Sinha ecstasy.piy...@gmail.com wrote: I found a good question to try for bit manipulation.Try it... :) Given an integer x, find out the smallest integer which has same number of set bits as x and is greater than x. For example if the input integer is 12 (1100) then your function should return 17(10001). If the input integer is 3(11) then your function should return 5(101) -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] find the integer
is there anyting special about the array??? or it is aribitary array?? On 7/8/11, Dumanshu duman...@gmail.com wrote: given an array of intergers. find the any integer that occurs only once. Others might occur any no. of times. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: find the integer
try sorting then if hashing On 7/8/11, Dumanshu duman...@gmail.com wrote: no constraints but try to give the optimized solution and plz no hashing. On Jul 8, 7:02 pm, Dumanshu duman...@gmail.com wrote: given an array of intergers. find the any integer that occurs only once. Others might occur any no. of times. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] GOOGLE Q
Given two sorted positive integer arrays A(n) and B(n). We define a set S = {(a,b) | a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Reversing the order of words in String
@Navneettake a look at the solution below and tell if there is any bug in it... *#include string.h typedef struct revll { char s[100]; struct revll *next; }revll; revll *rev_str(char *a) { char temp[100]; int i,len=strlen(a),j=0; revll *head,*p; head=NULL; for(i=0;ilen;i++) { if(a[i]!=' ') { temp[j++] = a[i]; } else { temp[j] = '\0'; p = (revll *)malloc(sizeof(revll)); p-next = head; strcpy(p-s,temp); head = p; j=0; } } /*for last word*/ temp[j] = '\0'; p = (revll *)malloc(sizeof(revll)); p-next = head; strcpy(p-s,temp); head = p; return head; } main() { char a[100]; revll *head; gets(a); head = rev_str(a); while(head) { printf(%s-,head-s); head=head-next; } system(pause); }* On Thu, Jul 7, 2011 at 9:10 AM, Navneet Gupta navneetn...@gmail.com wrote: @Piyush, could you elaborate your approach with Linked List? From what i am getting, even with Linked List, you would need two traversals at least. On Thu, Jul 7, 2011 at 2:07 AM, Piyush Sinha ecstasy.piy...@gmail.com wrote: Can we do it using linked list if ONE TIME TRAVERSAL is a constraint?? On 7/6/11, Tushar Bindal tushicom...@gmail.com wrote: I read that solution. But the same doubt as Navneet which I think you also raised i one of your posts on that thread On Wed, Jul 6, 2011 at 10:34 PM, Navneet Gupta navneetn...@gmail.com wrote: Saurabh, I understood your solution but wonder if it is purely single traversal In affect, you have a second traversal when you are popping the strings from stack to form the reverse order string. Though the second activity is less than O(n) i.e. O(#words in string) Nice solution, this way we can also get rid of extra spaces easily in the actual string if that is also to be done. On Wed, Jul 6, 2011 at 10:16 PM, saurabh singh saurab...@gmail.com wrote: I have proposed my solution in one of the previous posts.Check the solution there On Wed, Jul 6, 2011 at 10:10 PM, Tushar Bindal tushicom...@gmail.com wrote: good job but how can this be done in one traversal as asked on the Adobe Interview Questions thread. On Wed, Jul 6, 2011 at 9:49 PM, Navneet Gupta navneetn...@gmail.com wrote: I think somebody on this thread has asked this question but i am not able to find that. Question was if a string is like my name is ram, then output should be ram is name my. Wrote the code for same, so sharing. #includeiostream #includestring using namespace std; void SwapStringChars(string str, int pos1, int pos2) { char ch = str[pos1]; str[pos1] = str[pos2]; str[pos2] = ch; } void reverseString(string str, int left, int right) { for(int i = left ; i = left + (right-left)/2 ; i++) SwapStringChars(str, i, right + left -i)); } void reverseWordsInString(string str) { char space = ' '; int len = str.length(); int startIndex = 0, endIndex = 0; while(endIndex len - 1) { while(str[endIndex] != space endIndex len)endIndex++; reverseString(str, startIndex, endIndex-1); startIndex = endIndex; while(str[startIndex] == space)startIndex++; endIndex = startIndex; } } int main() { string str; cout\nEnter enter the string :; getline(cin,str); //Reverse whole string at once reverseString(str, 0, str.length() - 1); //Reverse Individual words in string reverseWordsInString(str); coutstr; cin.get(); return 0; } -- Regards, 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. -- Tushar Bindal Computer Engineering Delhi College of Engineering Mob: +919818442705 E-Mail : tushicom...@gmail.com Website: www.jugadengg.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
Re: [algogeeks] Amazon
I think for initial start it should be the minimum n values for n milestones On Thu, Jul 7, 2011 at 1:53 PM, Akshata Sharma akshatasharm...@gmail.comwrote: There is a straight roads with 'n' number of milestones. You are given an array with the distance between all the pairs of milestones in some random order. Find the position of milestones. Example: Consider a road with 4 milestones(a,b,c,d) : a --- 3Km ---b--- 5Km ---c--- 2Km ---d Distance between a and b = 3 Distance between a and c = 8 Distance between a and d = 10 Distance between b and c = 5 Distance between b and d = 7 Distance between c and d = 2 All the above values are given in a random order say 7, 10, 5, 2, 8, 3. The output must be 3,5,2 or 2,5,3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon
But the problem arises in setting the order On Thu, Jul 7, 2011 at 2:06 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: I think for initial start it should be the minimum n values for n milestones On Thu, Jul 7, 2011 at 1:53 PM, Akshata Sharma akshatasharm...@gmail.comwrote: There is a straight roads with 'n' number of milestones. You are given an array with the distance between all the pairs of milestones in some random order. Find the position of milestones. Example: Consider a road with 4 milestones(a,b,c,d) : a --- 3Km ---b--- 5Km ---c--- 2Km ---d Distance between a and b = 3 Distance between a and c = 8 Distance between a and d = 10 Distance between b and c = 5 Distance between b and d = 7 Distance between c and d = 2 All the above values are given in a random order say 7, 10, 5, 2, 8, 3. The output must be 3,5,2 or 2,5,3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] GOOGLE Q1
Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] GOOGLE Q2
Design a data structure that can be used instead of an array and avoids the high-cost (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merging Sorted Arrays
@radha...i have an algo but its complexity is O(n^2)...check the following and see if there is any bug as I havent tested for all cases...also suggestions are welcomed:) main() { int a[]= {1,3,77,78,88}; int b[]= {2,5,79,80,81,99}; int i=sizeof(a)/sizeof(a[0]) - 1; int j=sizeof(b)/sizeof(b[0]) - 1; int temp,k,m; while(j=0) { if(a[i]b[j]) { temp = a[i]; k=m=i; while(b[j]a[k-1]) k--; while(i-k) { a[i] = a[i-1]; i--; } a[i] = b[j]; b[j] = temp; i = m; } j--; } for(k=0;ksizeof(a)/sizeof(a[0]);k++) printf(%d ,a[k]); puts(\n); for(k=0;ksizeof(b)/sizeof(b[0]);k++) printf(%d ,b[k]); puts(\n); system(pause); } On 7/8/11, radha krishnan radhakrishnance...@gmail.com wrote: :Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge these two arrays, no extra spaces are allowed. Output has to be a[]={1,2,3,5,77} and b[]={78,79,81,90}. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Q3
@Rajeev...check ur logic for 4 On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: So, I think first check for excellent groups then good and then usual to increase the quality. So to get excellent groups scan the string and keep a count of the contagious repeating elements ,if count==3 or count==2,then put in one group The same procedure for good and usual accord to constraints . On Thu, Jul 7, 2011 at 11:46 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: You are given a String number containing the digits of a phone number (the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups: • Excellent: A group that contains only the same digits. For example, 000 or 77. • Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166. • Usual: A group in which all the digits are distinct. For example, 123 or 90. The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups) Divide the number into groups such that the quality is maximized. Design an efficient algorithm to return the solution that maximizes the quality. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Q1
Nopesits about finding subsequence On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: Should the sequence beContinuos ??? On Fri, Jul 8, 2011 at 1:18 AM, sunny agrawal sunny816.i...@gmail.comwrote: @rajiv if Count = 2 means 3 elements isn't it a,a+d,a+2d else according to you for case 10 12 14 24 26 28 diff 2 2 10 2 2 diff 2 has count 4 so will you say ap of 4 elements with diff 2 On Fri, Jul 8, 2011 at 1:06 AM, rajeev bharshetty rajeevr...@gmail.comwrote: @sunny Keep count of longest repeated element in diff i.e 2 so count =2 so ap of 2 elem with diff 2 . On Fri, Jul 8, 2011 at 1:03 AM, sunny agrawal sunny816.i...@gmail.comwrote: @rajiv Fails i think think for 10 12 24 26 diff is 2 12 2 so do you want to say there is an AP pf 3 elements with d = 2, i can't see any :P your solution fails because there can be many APs in the array with the same value of d and you will finish up by combining all those APs On Fri, Jul 8, 2011 at 12:55 AM, rajeev bharshetty rajeevr...@gmail.com wrote: Check the differences between the adjacent elements and store the differenecs in diff[i] array then scan through the array . then keep a count for all the repeated diff elements ,the sequence of indexes with max count is the solution . On Thu, Jul 7, 2011 at 11:43 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merging Sorted Arrays
@RADHA..ya true...my bad i cudnt think dat way...but as pointed out by Sunny the sorted output cant be brought in O(n)...In order to get the sorted output only my algo took O(n^2)...tell me if I am missing anything... On 7/8/11, sunny agrawal sunny816.i...@gmail.com wrote: yes upto the step of swapping the elements it is O(m+n) but if you need final arrays also sorted (Seems like that from your first post)it will go nlgn On Fri, Jul 8, 2011 at 1:25 AM, radha krishnan radhakrishnance...@gmail.com wrote: ok ! i got a O(n lgn) finally i don know exact complexity Let N = size of first array Find the first N smallest elements using one pointer in each array now swap the list of elements from index 0 to second-pointer in second array to first array with first_poiner+1 to N in first Array I think this is O(n) On Thu, Jul 7, 2011 at 12:53 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: @radha...i have an algo but its complexity is O(n^2)...check the following and see if there is any bug as I havent tested for all cases...also suggestions are welcomed:) main() { int a[]= {1,3,77,78,88}; int b[]= {2,5,79,80,81,99}; int i=sizeof(a)/sizeof(a[0]) - 1; int j=sizeof(b)/sizeof(b[0]) - 1; int temp,k,m; while(j=0) { if(a[i]b[j]) { temp = a[i]; k=m=i; while(b[j]a[k-1]) k--; while(i-k) { a[i] = a[i-1]; i--; } a[i] = b[j]; b[j] = temp; i = m; } j--; } for(k=0;ksizeof(a)/sizeof(a[0]);k++) printf(%d ,a[k]); puts(\n); for(k=0;ksizeof(b)/sizeof(b[0]);k++) printf(%d ,b[k]); puts(\n); system(pause); } On 7/8/11, radha krishnan radhakrishnance...@gmail.com wrote: :Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge these two arrays, no extra spaces are allowed. Output has to be a[]={1,2,3,5,77} and b[]={78,79,81,90}. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Q3
@Rajeev..there is the fault.for 4, there can be 2 excellent groups.. 55 55 54 therefore, quality = 2*2 = 4 which is highest... On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: It scans 555 count=3(excellent group) it will put in one group than 54 since the count is one puts that in usual group quality =2*1 =2 , On Fri, Jul 8, 2011 at 1:28 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @Rajeev...check ur logic for 4 On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: So, I think first check for excellent groups then good and then usual to increase the quality. So to get excellent groups scan the string and keep a count of the contagious repeating elements ,if count==3 or count==2,then put in one group The same procedure for good and usual accord to constraints . On Thu, Jul 7, 2011 at 11:46 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: You are given a String number containing the digits of a phone number (the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups: • Excellent: A group that contains only the same digits. For example, 000 or 77. • Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166. • Usual: A group in which all the digits are distinct. For example, 123 or 90. The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups) Divide the number into groups such that the quality is maximized. Design an efficient algorithm to return the solution that maximizes the quality. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Q3
sorry a typing mistake...lst line contains only 4 On 7/8/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: @Rajeev..there is the fault.for 4, there can be 2 excellent groups.. 55 55 54 therefore, quality = 2*2 = 4 which is highest... On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: It scans 555 count=3(excellent group) it will put in one group than 54 since the count is one puts that in usual group quality =2*1 =2 , On Fri, Jul 8, 2011 at 1:28 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @Rajeev...check ur logic for 4 On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: So, I think first check for excellent groups then good and then usual to increase the quality. So to get excellent groups scan the string and keep a count of the contagious repeating elements ,if count==3 or count==2,then put in one group The same procedure for good and usual accord to constraints . On Thu, Jul 7, 2011 at 11:46 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: You are given a String number containing the digits of a phone number (the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups: • Excellent: A group that contains only the same digits. For example, 000 or 77. • Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166. • Usual: A group in which all the digits are distinct. For example, 123 or 90. The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups) Divide the number into groups such that the quality is maximized. Design an efficient algorithm to return the solution that maximizes the quality. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Q3
@Rajeev...ignore my previous two posts. the grouping can be done as 55 554 quality is 2*1+1 = 3 which is the highest On 7/8/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: sorry a typing mistake...lst line contains only 4 On 7/8/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: @Rajeev..there is the fault.for 4, there can be 2 excellent groups.. 55 55 54 therefore, quality = 2*2 = 4 which is highest... On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: It scans 555 count=3(excellent group) it will put in one group than 54 since the count is one puts that in usual group quality =2*1 =2 , On Fri, Jul 8, 2011 at 1:28 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @Rajeev...check ur logic for 4 On 7/8/11, rajeev bharshetty rajeevr...@gmail.com wrote: So, I think first check for excellent groups then good and then usual to increase the quality. So to get excellent groups scan the string and keep a count of the contagious repeating elements ,if count==3 or count==2,then put in one group The same procedure for good and usual accord to constraints . On Thu, Jul 7, 2011 at 11:46 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: You are given a String number containing the digits of a phone number (the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups: • Excellent: A group that contains only the same digits. For example, 000 or 77. • Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166. • Usual: A group in which all the digits are distinct. For example, 123 or 90. The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups) Divide the number into groups such that the quality is maximized. Design an efficient algorithm to return the solution that maximizes the quality. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Q3
@Sunny...can u post a definite algo for it?? On 7/8/11, Ravi Shukla shuklaravi...@gmail.com wrote: @sunny , yep it looks DP. more of MCM. solve for substrings of length 1,2,3. and then apply DP[i][j]=max score for a substring from i to j. =max(DP[i][k]+DP[k][j]) where ki kj . The complexity this approach renders would be O(n^3). with O(n^2) space complexity. anyone anything better ? Thanks. Ravi Shukla CSE Final Year. BIT Mesra, Ranchi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Q3
Can u explain ur algo too?? On 7/8/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: @Sunny...nice solution but ur solution works if there can 1 to 3 groups of digits..but in the question its mentioned the group should contain exactly 2 or 3 digits... but anyways nice solution...:) On 7/8/11, sunny agrawal sunny816.i...@gmail.com wrote: http://ideone.com/xv73J On Fri, Jul 8, 2011 at 2:16 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @Sunny...can u post a definite algo for it?? On 7/8/11, Ravi Shukla shuklaravi...@gmail.com wrote: @sunny , yep it looks DP. more of MCM. solve for substrings of length 1,2,3. and then apply DP[i][j]=max score for a substring from i to j. =max(DP[i][k]+DP[k][j]) where ki kj . The complexity this approach renders would be O(n^3). with O(n^2) space complexity. anyone anything better ? Thanks. Ravi Shukla CSE Final Year. BIT Mesra, Ranchi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] NVIDIA Q
What is the size of an object of a class with no members in it?? -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] NVIDIA Q
thanks buddy..:) On 7/6/11, durgaprasad k durga...@gmail.com wrote: The size will be 1 byte as there is nothing to look into the object. And it is 1 instead of zero because two objects of the class will have different addresses by assigning each object size 1. Regards, Durga On Wed, Jul 6, 2011 at 2:11 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: What is the size of an object of a class with no members in it?? -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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]
Why is it suggested not to use malloc() or calloc() in C++ for memory allocation? -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Reversing the order of words in String
Can we do it using linked list if ONE TIME TRAVERSAL is a constraint?? On 7/6/11, Tushar Bindal tushicom...@gmail.com wrote: I read that solution. But the same doubt as Navneet which I think you also raised i one of your posts on that thread On Wed, Jul 6, 2011 at 10:34 PM, Navneet Gupta navneetn...@gmail.comwrote: Saurabh, I understood your solution but wonder if it is purely single traversal In affect, you have a second traversal when you are popping the strings from stack to form the reverse order string. Though the second activity is less than O(n) i.e. O(#words in string) Nice solution, this way we can also get rid of extra spaces easily in the actual string if that is also to be done. On Wed, Jul 6, 2011 at 10:16 PM, saurabh singh saurab...@gmail.com wrote: I have proposed my solution in one of the previous posts.Check the solution there On Wed, Jul 6, 2011 at 10:10 PM, Tushar Bindal tushicom...@gmail.com wrote: good job but how can this be done in one traversal as asked on the Adobe Interview Questions thread. On Wed, Jul 6, 2011 at 9:49 PM, Navneet Gupta navneetn...@gmail.com wrote: I think somebody on this thread has asked this question but i am not able to find that. Question was if a string is like my name is ram, then output should be ram is name my. Wrote the code for same, so sharing. #includeiostream #includestring using namespace std; void SwapStringChars(string str, int pos1, int pos2) { char ch = str[pos1]; str[pos1] = str[pos2]; str[pos2] = ch; } void reverseString(string str, int left, int right) { for(int i = left ; i = left + (right-left)/2 ; i++) SwapStringChars(str, i, right + left -i)); } void reverseWordsInString(string str) { char space = ' '; int len = str.length(); int startIndex = 0, endIndex = 0; while(endIndex len - 1) { while(str[endIndex] != space endIndex len)endIndex++; reverseString(str, startIndex, endIndex-1); startIndex = endIndex; while(str[startIndex] == space)startIndex++; endIndex = startIndex; } } int main() { string str; cout\nEnter enter the string :; getline(cin,str); //Reverse whole string at once reverseString(str, 0, str.length() - 1); //Reverse Individual words in string reverseWordsInString(str); coutstr; cin.get(); return 0; } -- Regards, 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. -- Tushar Bindal Computer Engineering Delhi College of Engineering Mob: +919818442705 E-Mail : tushicom...@gmail.com Website: www.jugadengg.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. -- 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. -- Regards, 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. -- Tushar Bindal Computer Engineering Delhi College of Engineering Mob: +919818442705 E-Mail : tushicom...@gmail.com Website: www.jugadengg.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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message
Re: [algogeeks] MS Ques
Can we do it using suffix trees and apply DFS on it?? On Tue, Jul 5, 2011 at 11:45 PM, swetha rahul swetharahu...@gmail.comwrote: Hi, Write a function which takes two char * s as inputs, one is a regular expression pattern and the other is a test string and check whether the test string is of the given regular expression pattern. The regular expression pattern can contain all lower-case letter, asterisk and question mark. As usual asterisk stands for 0 or more number of chars and ? for any one char. E.g. Regular Expression: a*b?c Test String: aaavcxbmbcxmbkc Result: TRUE Test String: abc Result: FALSE Test String: abzx Result: TRUE What is d best way 2 do this... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Flatten a BST to produce inorder traversal
Use the concept used in Morris traversal (same as TBT concept)... On 7/4/11, sunny agrawal sunny816.i...@gmail.com wrote: I think Threaded Binary Tree solves your Problem see this http://en.wikipedia.org/wiki/Threaded_binary_tree On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta navneetn...@gmail.comwrote: Tree has an extra pointer next apart from left and right. Objective is to set next pointer to point to node successor in the tree. Following the next pointer, we would be able to produce sorted list. Looking for both a recursive and non-recursive approach. --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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Flatten a BST to produce inorder traversal
http://geeksforgeeks.org/?p=6358 On 7/4/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Use the concept used in Morris traversal (same as TBT concept)... On 7/4/11, sunny agrawal sunny816.i...@gmail.com wrote: I think Threaded Binary Tree solves your Problem see this http://en.wikipedia.org/wiki/Threaded_binary_tree On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta navneetn...@gmail.comwrote: Tree has an extra pointer next apart from left and right. Objective is to set next pointer to point to node successor in the tree. Following the next pointer, we would be able to produce sorted list. Looking for both a recursive and non-recursive approach. --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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Flatten a BST to produce inorder traversal
I know its not about the traversali just suggested that one can use the trick used by Morris traversal to locate the next node of the inorder traversal... On 7/4/11, Navneet Gupta navneetn...@gmail.com wrote: @Piyush, it is not about the traversal, you actually have to establish those links such that once they are established, inorder traversal would be just like traversing a list. @Sunny - thanks, exactly what i was looking for On Mon, Jul 4, 2011 at 11:45 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: http://geeksforgeeks.org/?p=6358 On 7/4/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Use the concept used in Morris traversal (same as TBT concept)... On 7/4/11, sunny agrawal sunny816.i...@gmail.com wrote: I think Threaded Binary Tree solves your Problem see this http://en.wikipedia.org/wiki/Threaded_binary_tree On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta navneetn...@gmail.comwrote: Tree has an extra pointer next apart from left and right. Objective is to set next pointer to point to node successor in the tree. Following the next pointer, we would be able to produce sorted list. Looking for both a recursive and non-recursive approach. --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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Flatten a BST to produce inorder traversal
U only mentioned in ur question that we have to use next pointer to connect the nodes...while TBT used the left and right pointers On 7/5/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: I know its not about the traversali just suggested that one can use the trick used by Morris traversal to locate the next node of the inorder traversal... On 7/4/11, Navneet Gupta navneetn...@gmail.com wrote: @Piyush, it is not about the traversal, you actually have to establish those links such that once they are established, inorder traversal would be just like traversing a list. @Sunny - thanks, exactly what i was looking for On Mon, Jul 4, 2011 at 11:45 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: http://geeksforgeeks.org/?p=6358 On 7/4/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Use the concept used in Morris traversal (same as TBT concept)... On 7/4/11, sunny agrawal sunny816.i...@gmail.com wrote: I think Threaded Binary Tree solves your Problem see this http://en.wikipedia.org/wiki/Threaded_binary_tree On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta navneetn...@gmail.comwrote: Tree has an extra pointer next apart from left and right. Objective is to set next pointer to point to node successor in the tree. Following the next pointer, we would be able to produce sorted list. Looking for both a recursive and non-recursive approach. --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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 plzzzz
i) [Linker error] undefined reference to `a' ii) 4 On 7/3/11, HARSH PAHUJA hpahuja.mn...@gmail.com wrote: 1) #includestdio.h int main() { extern int a; a=20; printf(%d,sizeof(a)); return 0; } 2) #includestdio.h int main() { extern int a; printf(%d,sizeof(a)); return 0; } -- HARSHIT PAHUJA M.N.N.I.T. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] query
Its working fine.. On Wed, Jun 29, 2011 at 5:26 PM, sunny agrawal sunny816.i...@gmail.comwrote: the error is in quotes, just rewrite them On Wed, Jun 29, 2011 at 5:24 PM, Anika Jain anika.jai...@gmail.comwrote: hey, printf(%d ya %u in both same error cming.. On Wed, Jun 29, 2011 at 5:10 PM, sunny agrawal sunny816.i...@gmail.comwrote: Because u copied the code i think :P try writing printf statement yourself again :) On Wed, Jun 29, 2011 at 5:05 PM, Anika Jain anika.jai...@gmail.comwrote: int main() { int I =10, j=2; int *ip = I ,*jp =j; int k = *ip/ *jp; printf(“%u”,k); return 0; } in this code error is coming 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] query
ya noticed just now when sunny agrawal pointed it out... On Wed, Jun 29, 2011 at 5:38 PM, oppilas . jatka.oppimi...@gmail.comwrote: Piyush the original code has double apostrophe( ' ) instead of inverted comma's. http://ideone.com/zPpGA On Wed, Jun 29, 2011 at 5:30 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Its working fine.. On Wed, Jun 29, 2011 at 5:26 PM, sunny agrawal sunny816.i...@gmail.comwrote: the error is in quotes, just rewrite them On Wed, Jun 29, 2011 at 5:24 PM, Anika Jain anika.jai...@gmail.comwrote: hey, printf(%d ya %u in both same error cming.. On Wed, Jun 29, 2011 at 5:10 PM, sunny agrawal sunny816.i...@gmail.com wrote: Because u copied the code i think :P try writing printf statement yourself again :) On Wed, Jun 29, 2011 at 5:05 PM, Anika Jain anika.jai...@gmail.comwrote: int main() { int I =10, j=2; int *ip = I ,*jp =j; int k = *ip/ *jp; printf(“%u”,k); return 0; } in this code error is coming 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] linked list
node *segregate(node *head) { node *even,*odd,*even1,*odd1; even=odd=NULL; while(head) { if((head-data)%2) { if(!odd) { odd = head; odd1 = odd; } else { odd1-next = head; odd1 = odd1-next; } } else { if(!even) { even = head; even1 = even; } else { even1-next = head; even1 = even1-next; } } head=head-next; } odd1-next=NULL; even1-next = odd; return (even); } On 6/29/11, Nishant Mittal mittal.nishan...@gmail.com wrote: segregate even and odd nodes in a singly linked list.Order of even and odd numbers must be same... e.g:- i/p list is 4-1-3-6-12-8-7-NULL o/p list 4-6-12-8-1-3-7-NULL -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
7+3 also give the sum to be 10??? On 6/29/11, 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon - max substring
i think suffix tres will do the job if i have not misunderstood the question... On 6/29/11, Swathi chukka.swa...@gmail.com wrote: Given a string (assume there no spaces or punctuations), write a code that returns the max. length of the string that has repeated more than once. Thanks, Swathi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon - max substring
I dnt think any company is gonna ask u to code suffix tree..:P :P On 6/29/11, Swathi chukka.swa...@gmail.com wrote: It does but i am asked to code.. if you know the code for suffix tree then please provide.. On Wed, Jun 29, 2011 at 10:30 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: i think suffix tres will do the job if i have not misunderstood the question... On 6/29/11, Swathi chukka.swa...@gmail.com wrote: Given a string (assume there no spaces or punctuations), write a code that returns the max. length of the string that has repeated more than once. Thanks, Swathi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon - max substring
jokes apart...then i think it can be done using dynamic programming using the similar approach of LCS but the time and space complexity both will be N^2.i am working on the pseudocode and post it within a few moments if it works.. On 6/29/11, Swathi chukka.swa...@gmail.com wrote: I dont know why people reply in plain words.. I personally had this experience and i was asked to code but i couldn't On Wed, Jun 29, 2011 at 10:53 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: I dnt think any company is gonna ask u to code suffix tree..:P :P On 6/29/11, Swathi chukka.swa...@gmail.com wrote: It does but i am asked to code.. if you know the code for suffix tree then please provide.. On Wed, Jun 29, 2011 at 10:30 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: i think suffix tres will do the job if i have not misunderstood the question... On 6/29/11, Swathi chukka.swa...@gmail.com wrote: Given a string (assume there no spaces or punctuations), write a code that returns the max. length of the string that has repeated more than once. Thanks, Swathi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] 2 D array(dynamic allocation)
int **p; p = (int **)malloc(sizeof(int *)*row); for(i = 0;irow;i++) p[i] = (int *)malloc(sizeof(int)*column); On 6/30/11, Apoorve Mohan apoorvemo...@gmail.com wrote: though thankx :) On Thu, Jun 30, 2011 at 12:44 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: @above: man i need a 2d array not a 1d array... On Thu, Jun 30, 2011 at 12:38 AM, hary rathor harry.rat...@gmail.comwrote: #includestdlib.h int main () { int *mat; int i,j; int ROW=4; int COL=3; int k=0; mat=(int *)malloc(ROW*COL*sizeof(int)); for(i=0;iROW;i++) for(j=0;jCOL;j++) mat[i*COL+j]=++k; for(i=0;iROW;i++) for(j=0;jCOL;j++) printf(%d,,mat[i*COL+j]); 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 Apoorve Mohan -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] 2 D array(dynamic allocation)
ohh sorrymy bad...i didnt read the whole question..i just read the subject...:P i think its not possible if u want other than hary's solution... On 6/30/11, Apoorve Mohan apoorvemo...@gmail.com wrote: @piyush: only one call to malloc...ur sol has 2 On Thu, Jun 30, 2011 at 12:58 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: int **p; p = (int **)malloc(sizeof(int *)*row); for(i = 0;irow;i++) p[i] = (int *)malloc(sizeof(int)*column); On 6/30/11, Apoorve Mohan apoorvemo...@gmail.com wrote: though thankx :) On Thu, Jun 30, 2011 at 12:44 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: @above: man i need a 2d array not a 1d array... On Thu, Jun 30, 2011 at 12:38 AM, hary rathor harry.rat...@gmail.comwrote: #includestdlib.h int main () { int *mat; int i,j; int ROW=4; int COL=3; int k=0; mat=(int *)malloc(ROW*COL*sizeof(int)); for(i=0;iROW;i++) for(j=0;jCOL;j++) mat[i*COL+j]=++k; for(i=0;iROW;i++) for(j=0;jCOL;j++) printf(%d,,mat[i*COL+j]); 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 Apoorve Mohan -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Printing unique rows.
In any case, I don't think the complexity can be improved from O(n^2) because even in creating hash function every column element of every row which itself is N^2 only.. On Tue, Jun 28, 2011 at 11:38 AM, Ankit Agrawal ankitmnnit.agra...@gmail.com wrote: u can use hashing ... hash fun can b base2 to base10 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] given a bst and a value x.find pair of nodes in the tree that sum upto x
Instead of using an array...we can do this by converting the BST into a doubly linked list...but this will definitely modify the BST.. On Mon, Jun 27, 2011 at 3:01 PM, varun pahwa varunpahwa2...@gmail.comwrote: @ankit: no need to use hash table for that. simply run two pointers one from 0 and second from n - 1. On Mon, Jun 27, 2011 at 2:51 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Bharath : Cud u plz explain how r u searching the elements in O(n) time? Because if we use binary search, it will have O(n*log n ) worst case time complexity. One way in which I think it cud be made O(n) is that we can use a hash table, with a good hash function apart frm the array. And then for each element 'm' in the array, we cud search if there is an element (sum - m) in O(1) time by using hash table. Still we can't assure O(n) time complexity. Because coming up with a good hash function is not easy. Again, hash table takes more space On Mon, Jun 27, 2011 at 1:40 AM, Nishant Mittal mittal.nishan...@gmail.com wrote: do inorder traversal of tree and store values in an array. Now find pairs by applying binary search on array.. On 6/27/11, manish kapur manishkapur.n...@gmail.com wrote: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 a bst and a value x.find pair of nodes in the tree that sum upto x
how about converting the BST into a doubly linked list...but this will definitely modify the BST.. On Mon, Jun 27, 2011 at 11:32 PM, Swathi chukka.swa...@gmail.com wrote: Dave, I am unable to write code for this so i am asking your help. Thanks, Swathi On Mon, Jun 27, 2011 at 11:28 PM, Dave dave_and_da...@juno.com wrote: @Swathi: No. I think the high level description should be adequate for you to write your own code or pseudocode, albeit recognizing that you may have to look up how to do an inorder traversal using a stack instead of recursion. Dave On Jun 27, 9:34 am, Swathi chukka.swa...@gmail.com wrote: Dave, Can you provide the psuedo code for this.. Thanks, Swathi On Mon, Jun 27, 2011 at 7:30 PM, Dave dave_and_da...@juno.com wrote: @Sunny. Mea culpa. You are correct. Revised (and correct) algorithm. Do two inorder traversals, one in the usual (descend to the left before descendung to the right) direction and the other in the reversed(descend to the right before descending to the left) direction. Let u and r be the current nodee of the two traversals, respectively. If u + r x, then advance the usual traversal and repeat the comparison. If u + r x, advance the reverse traversal and repeat the comparison. If u + r = x, and if u != r, then terminate with success. If u = r, then terminate with failure. Dave On Jun 27, 7:53 am, sunny agrawal sunny816.i...@gmail.com wrote: @Dave i think your solution won't work consider inorder traversal of a BST is 1 6 7 8 15 and x = 14 initially both u,v (1,1) according to u your algorithm will proceed like (1,1) - (1,6) - (1,7) - (1,8) - (1,15) - (6,15) - (15,15) and clearly in second step of your solution if (u+v) x after advancing u still u+v will be greater than x so something is wrong I think your solution will work in case we need to find 2 nodes with difference x. correct me if i am wrong.!! On Mon, Jun 27, 2011 at 6:13 PM, Dave dave_and_da...@juno.com wrote: @Nishant: No need to store the data in an array. Do two inorder traversals simultaneously. Let u and v be the current nodes of the two traversals, respectively. If u + v x, then advance the v traversal. If u + v x, advance the u traversal. Dave On Jun 27, 3:40 am, Nishant Mittal mittal.nishan...@gmail.com wrote: do inorder traversal of tree and store values in an array. Now find pairs by applying binary search on array.. On 6/27/11, manish kapur manishkapur.n...@gmail.com wrote: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hidequotedtext - - 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee- 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.- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks
Re: [algogeeks] novel written test
1,6,6 On Tue, Jun 28, 2011 at 2:07 AM, amit the cool amitthecoo...@gmail.comwrote: Conversation between two mathematicians: first : I have three children. The product of their ages is 36 . If you sum their ages . it is exactly same as my neighbor's door number on my left. The second mathematician verifies the door number and says that the not sufficient . Then the first says o.k one more clue is that my youngest is the youngest Immediately the second mathematician answers . Can you answer the question asked by the first mathematician? What are the children ages? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] novel written test
We just need to look the 3 set of number that multiply to 36... the set can be as (1,1,36),(1,2,18),(1,4,9)..(1,6,6),(1,3,12)..(2,2,9) The catch here is we need not find the whole set...the second mathematician can't guess their ages through their sum that means there are at least two possible combination that sum to the same value.. we have 1,6,6 and 2,2,9 second clue says my youngest is youngest... if we look into the combination, we find the first set have unique age for the youngest son..hence the ages.. and 2 sons can have same age without being twins...one born in the month of jan and the other born in the month of december...:P :P moreover its no where mentioned there can't be any twins On Tue, Jun 28, 2011 at 2:24 AM, amit kumar amitthecoo...@gmail.com wrote: @piyush..will u xplain plz. by d way 2 sons cant hav d same age(hope they r nt twins) On Tue, Jun 28, 2011 at 2:14 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: 1,6,6 On Tue, Jun 28, 2011 at 2:07 AM, amit the cool amitthecoo...@gmail.comwrote: Conversation between two mathematicians: first : I have three children. The product of their ages is 36 . If you sum their ages . it is exactly same as my neighbor's door number on my left. The second mathematician verifies the door number and says that the not sufficient . Then the first says o.k one more clue is that my youngest is the youngest Immediately the second mathematician answers . Can you answer the question asked by the first mathematician? What are the children ages? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Queue to support insert , delete, find max in o(1)
Can we use circular linked list with each new inserted node keeping track of the minimum before it?? On Fri, Jun 24, 2011 at 3:20 PM, ross jagadish1...@gmail.com wrote: Hi, I know that a stack can be modified with another stack to support push pop min in const time. Design a FIFO data structure to support ins, del, and find min in O(1). Extra space allowed. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Queue to support insert , delete, find max in o(1)
ohh sorry, my bad..I missed that issue...then we can use the same logic of using one more stack that we use for implementing modified stack keeping track of the min()..I hope this will solve the issue On Fri, Jun 24, 2011 at 3:57 PM, ross jagadish1...@gmail.com wrote: @piyush, Dude, how will that make findmin() to be O(1) because, once the minimum element is deleted, u would require changes in the others .. Correct me if i am wrong.. Eg: consider inserting, 1 5 6 7 9 in order into the circular LL. When u make each node keep track of the minm before it, all will retain 1 as minm.. Now consider deleting 1. how will that affect the rest of the list? On Jun 24, 3:07 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: Can we use circular linked list with each new inserted node keeping track of the minimum before it?? On Fri, Jun 24, 2011 at 3:20 PM, ross jagadish1...@gmail.com wrote: Hi, I know that a stack can be modified with another stack to support push pop min in const time. Design a FIFO data structure to support ins, del, and find min in O(1). Extra space allowed. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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)
I have a solution that will do the job in O(n) time but will require three variablesbut this solution won't work if the array contains -ve numbers. * int findrepeat(int a[],int n) { int i,xor = 0; int min = findmin(a,n); int max = findmax(a,n); if((max-min+1)!=n) return 0; for(i = 0 ;in;i++) xor^=a[i]; for(i=min;i=max;i++) xor^=i; if(xor) return 0; else return 1; }* Please let me know if there is any counter example.. On Sat, Jun 25, 2011 at 1:17 AM, ross jagadish1...@gmail.com wrote: One solution would be to : check if max-min = N and that all elements are unique in the array. However, this may require space complexity.. Looking for a better solution. On Jun 25, 12:44 am, ross jagadish1...@gmail.com wrote: Given an array, A, find if all elements in the sorted version of A are consecutive in less than O(nlogn). eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive -- true A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive - false -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Question on Combination
sorry a lil bit modification in the above answer.. *int ref[] = {1,2,3};* *void printcombination(int n,int index,int i)* *{* *static int a[100];* *int j;* *if (n == 0)* * {* * for(j=0;jindex;j++)* * printf(%d ,a[j]);* * printf(\n);* *}* * else if(n0)* * {* * for(j=i;j3;j++)* * {* *a[index]=ref[j];* * printcombination(n-ref[j],index+1,j);* * }* * }* *} * *main()* *{* * int n;* * printf(enter value of n :);* * scanf(%d,n);* * printcombination(n,0,0);* *}* On Thu, Jun 23, 2011 at 11:17 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: pass one more argument to the function *int index* and instead of starting the loop from *i = 0 to N, *make it start from *i = index to N *and then call *printcombinations(a,sum-a[i],level+1,index+1); *I think it will work then... On Thu, Jun 23, 2011 at 10:48 AM, ross jagadish1...@gmail.com wrote: Given an array and a sum S output all combinations of elements that sum to S. eg: 1 2 3 sum = 3 1+1+1, 2+1 3 I came up with the foll algorithm, but it outputs 2+1 and 1+2 again. (does not handle repetitions) printcombinations(int a[],int sum,int level) { if(sum==0) { print array} else if (sum0) { for ( i = 0 to N ) { array[level]=a[i]; printcombinations(a,sum-a[i],level+1); } } } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Please explain the output
printf(%d,*power(432)) will expand as *printf(%d, *432)* 432 represents here a string and *432 is pointing to the first string literal i.e 4 whose ascii value is 52..hence the output is 52 On Thu, Jun 23, 2011 at 4:02 PM, Shachindra A C sachindr...@gmail.comwrote: #includestdio.h #define power(a) #a int main() { printf(%d,*power(432)); return 0; } the printf statement, after preprocessing, will look like printf(%d,*432); so, when u print the value at the first position of the string, 52, which is the ascii value of 4, will be printed. On Thu, Jun 23, 2011 at 3:40 PM, vaibhav shukla vaibhav200...@gmail.comwrote: #includestdio.h #define power(a) #a int main() { printf(%d,*power(432)); return 0; } ans is 52 on gcc. Explain plss -- 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, Shachindra A C -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 query
the comma operator evaluates its first operand and discards the result, and then evaluates the second operand and returns this value. instead of 3, whatever u write. the result will depend on the second operand i.e x1 i.e 2 (5/2 = 2) On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: #includestdio.h typedef struct { char *name; double salary; }job; main() { static job a={tcs,15000.0}; static job a={ibm,25000.0}; static job a={google,35000.0}; int x=5; job *arr[3]={a,b,c}; printf(%s %f\t,(3,x1)[*arr]); } output: google 35000.00 what this printf statement means plz explain... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 query
for further details. http://en.wikipedia.org/wiki/Comma_operator On 6/23/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: the comma operator evaluates its first operand and discards the result, and then evaluates the second operand and returns this value. instead of 3, whatever u write. the result will depend on the second operand i.e x1 i.e 2 (5/2 = 2) On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: #includestdio.h typedef struct { char *name; double salary; }job; main() { static job a={tcs,15000.0}; static job a={ibm,25000.0}; static job a={google,35000.0}; int x=5; job *arr[3]={a,b,c}; printf(%s %f\t,(3,x1)[*arr]); } output: google 35000.00 what this printf statement means plz explain... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 doubt again
An asterisk indicates that the data is to be retrieved from the use but ignored, i.e. it is not stored in the corresponding argument...hence the third value entered gets stored for b and for c the output comes to garbage value One beautiful application of such type of implementation is in finding the sum of 2 variables without using + operator..:) On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: int main() { int a,b, c; scanf(%d%*d%d,a,b,c); printf(%d %d %d,a,b,c); } output: 25 35 garbage how is it happening?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 query
I had a doubt which I wanted to ask...for me output is coming as follows google 0.00 r u sure ur output is coming to be google 35000.00 On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: ya *arr[2] is fine but in printing a struct element do we need to give all necessary format specifiers for printing?? On Thu, Jun 23, 2011 at 7:15 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: for further details. http://en.wikipedia.org/wiki/Comma_operator On 6/23/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: the comma operator evaluates its first operand and discards the result, and then evaluates the second operand and returns this value. instead of 3, whatever u write. the result will depend on the second operand i.e x1 i.e 2 (5/2 = 2) On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: #includestdio.h typedef struct { char *name; double salary; }job; main() { static job a={tcs,15000.0}; static job a={ibm,25000.0}; static job a={google,35000.0}; int x=5; job *arr[3]={a,b,c}; printf(%s %f\t,(3,x1)[*arr]); } output: google 35000.00 what this printf statement means plz explain... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 doubt again
sorry by mistake i added it in scanf situation.. actually this type of specifier can be used with printf statement for finding the sum... look at the code below main() { int a=9; int b=3; printf(%d\n,printf(%*s%*s,a,,b,)); system(pause); } On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: thanx .. can u explain me how this is used in finding sum of 2 vars without using + ?? On Thu, Jun 23, 2011 at 7:20 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: An asterisk indicates that the data is to be retrieved from the use but ignored, i.e. it is not stored in the corresponding argument...hence the third value entered gets stored for b and for c the output comes to garbage value One beautiful application of such type of implementation is in finding the sum of 2 variables without using + operator..:) On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: int main() { int a,b, c; scanf(%d%*d%d,a,b,c); printf(%d %d %d,a,b,c); } output: 25 35 garbage how is it happening?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 doubt again
there is no as such logic behind it..its just the format specifier... u must be knowing printf returns the number of values it has printed(u can check that) now, in printf if u write like *printf(%7s,a), *it will create 7 columns for the output and print a in the last column and the returned value of this printf will be 7..(u can check it) now if u write *printf(%*s,7,a)* then u r giving additional information of format specifier i.e 7..returned value of this printf is also 7. Hence the above logic..hope I am able to clarify it...:) On Thu, Jun 23, 2011 at 8:06 PM, Anika Jain anika.jai...@gmail.com wrote: i mean how it working actually? On Thu, Jun 23, 2011 at 8:06 PM, Anika Jain anika.jai...@gmail.comwrote: hey ya its working :) but whats the logic behind it?? On Thu, Jun 23, 2011 at 7:52 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: sorry by mistake i added it in scanf situation.. actually this type of specifier can be used with printf statement for finding the sum... look at the code below main() { int a=9; int b=3; printf(%d\n,printf(%*s%*s,a,,b,)); system(pause); } On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: thanx .. can u explain me how this is used in finding sum of 2 vars without using + ?? On Thu, Jun 23, 2011 at 7:20 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: An asterisk indicates that the data is to be retrieved from the use but ignored, i.e. it is not stored in the corresponding argument...hence the third value entered gets stored for b and for c the output comes to garbage value One beautiful application of such type of implementation is in finding the sum of 2 variables without using + operator..:) On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: int main() { int a,b, c; scanf(%d%*d%d,a,b,c); printf(%d %d %d,a,b,c); } output: 25 35 garbage how is it happening?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 query
even I am getting output as google 0.0 On 6/23/11, Bhavesh agrawal agr.bhav...@gmail.com wrote: i got (null) 0.0 on my gcc compiler , is there any syntax error -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 doubt again
or u cud consult ANSI C by Balaguruswamy in chapter of Console I/Ps and O/Ps On 6/23/11, harshit pahuja hpahuja.mn...@gmail.com wrote: @rajeev http://www.cplusplus.com/reference/clibrary/cstdio/scanf/ http://www.cplusplus.com/reference/clibrary/cstdio/printf/ On Thu, Jun 23, 2011 at 9:39 PM, rajeev bharshetty rajeevr...@gmail.comwrote: @ Piyush Could u provide the link to some source , because i am still unclear about the above concept . Regards Rajeev N B On Thu, Jun 23, 2011 at 8:32 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: there is no as such logic behind it..its just the format specifier... u must be knowing printf returns the number of values it has printed(u can check that) now, in printf if u write like *printf(%7s,a), *it will create 7 columns for the output and print a in the last column and the returned value of this printf will be 7..(u can check it) now if u write *printf(%*s,7,a)* then u r giving additional information of format specifier i.e 7..returned value of this printf is also 7. Hence the above logic..hope I am able to clarify it...:) On Thu, Jun 23, 2011 at 8:06 PM, Anika Jain anika.jai...@gmail.comwrote: i mean how it working actually? On Thu, Jun 23, 2011 at 8:06 PM, Anika Jain anika.jai...@gmail.comwrote: hey ya its working :) but whats the logic behind it?? On Thu, Jun 23, 2011 at 7:52 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: sorry by mistake i added it in scanf situation.. actually this type of specifier can be used with printf statement for finding the sum... look at the code below main() { int a=9; int b=3; printf(%d\n,printf(%*s%*s,a,,b,)); system(pause); } On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: thanx .. can u explain me how this is used in finding sum of 2 vars without using + ?? On Thu, Jun 23, 2011 at 7:20 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: An asterisk indicates that the data is to be retrieved from the use but ignored, i.e. it is not stored in the corresponding argument...hence the third value entered gets stored for b and for c the output comes to garbage value One beautiful application of such type of implementation is in finding the sum of 2 variables without using + operator..:) On 6/23/11, Anika Jain anika.jai...@gmail.com wrote: int main() { int a,b, c; scanf(%d%*d%d,a,b,c); printf(%d %d %d,a,b,c); } output: 25 35 garbage how is it happening?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email
Re: [algogeeks] Time Complexity of Merge Sort(Linked list)
Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case On 6/23/11, Anantha Krishnan ananthakrishnan@gmail.com wrote: Hi All, Can someone explain about the time complexity of Merge sort(Linked list with billions of node)? There is no way to find the middle of sub-list without traversing completely. Please clear my doubts. Thanks Regards, Anantha Krishnan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Time Complexity of Merge Sort(Linked list)
I googled a better explaination for this and found this... hope this will be useful... Sorting a LinkedList is different from sorting an Array as you can not make index based references to any arbitrary item in the List. Instead you need to remember the items during each recursive step and then pass them on to the merge function. For each recursion step you only need to remember the first item of each list half. If you do not remember these items you will quickly end up with indexes, but this leads you to the problem that in your merge-function you need to traverse the whole list with for-loops to find the items to merge. That in turn means you get a complexity of O(n^2). Another important point is the step of recursing into the list and dividing the list in two halves. You can do this step in the recursive part by using for-loops. Contrary to the merge-part at this step the for-loops will only yield a complexity of O(log(n) * n/2) and this is still below the overall O(n*log(n)) complexity. Here is why: 1. You always need to find the first item of each half of list part. 2. In the first recursion step you need to pass the first item and the item at position n/2. This takes n/2 steps to find. 3. In each following step you need to find the middle item for each of the two halves of the list which gives us n/4 to find the item in the first halve and n/4 in the other halve. In total thats n/2. 4. In each following recursive step the amount of list parts double and the lengths is divided by two: * 4 * n/8 in the 3rd recursion depth * 8 * n/16 in the 4th recursion depth, and so on... 5. The recursion depth is log(n) and in each step we perform n/2 steps. This equals O(log(n)*n/2) On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case On 6/23/11, Anantha Krishnan ananthakrishnan@gmail.com wrote: Hi All, Can someone explain about the time complexity of Merge sort(Linked list with billions of node)? There is no way to find the middle of sub-list without traversing completely. Please clear my doubts. Thanks Regards, Anantha Krishnan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Time Complexity of Merge Sort(Linked list)
Also u can refer http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: I googled a better explaination for this and found this... hope this will be useful... Sorting a LinkedList is different from sorting an Array as you can not make index based references to any arbitrary item in the List. Instead you need to remember the items during each recursive step and then pass them on to the merge function. For each recursion step you only need to remember the first item of each list half. If you do not remember these items you will quickly end up with indexes, but this leads you to the problem that in your merge-function you need to traverse the whole list with for-loops to find the items to merge. That in turn means you get a complexity of O(n^2). Another important point is the step of recursing into the list and dividing the list in two halves. You can do this step in the recursive part by using for-loops. Contrary to the merge-part at this step the for-loops will only yield a complexity of O(log(n) * n/2) and this is still below the overall O(n*log(n)) complexity. Here is why: 1. You always need to find the first item of each half of list part. 2. In the first recursion step you need to pass the first item and the item at position n/2. This takes n/2 steps to find. 3. In each following step you need to find the middle item for each of the two halves of the list which gives us n/4 to find the item in the first halve and n/4 in the other halve. In total thats n/2. 4. In each following recursive step the amount of list parts double and the lengths is divided by two: * 4 * n/8 in the 3rd recursion depth * 8 * n/16 in the 4th recursion depth, and so on... 5. The recursion depth is log(n) and in each step we perform n/2 steps. This equals O(log(n)*n/2) On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case On 6/23/11, Anantha Krishnan ananthakrishnan@gmail.com wrote: Hi All, Can someone explain about the time complexity of Merge sort(Linked list with billions of node)? There is no way to find the middle of sub-list without traversing completely. Please clear my doubts. Thanks Regards, Anantha Krishnan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Question
This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 this.....
r u sure the last output is also 100..for me its coming 99 On 6/22/11, udit sharma sharmaudit...@gmail.com wrote: #includestdio.h int main() { void print(int *,int *,int *,int *,int *); static int arr[]={97,98,99,100,101,102,103,104}; int *ptr=arr+1; print(++ptr,ptr--,ptr,ptr++,++ptr); return 0; } void print(int *a,int *b,int *c,int *d,int *e) { printf(%d\t%d\t%d\t%d\t%d\n,*a,*b,*c,*d,*e); } Why the output is: 10010010099100 -- Regards UDIT 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 this.....
the arguments are passed from right to left in a function... initially ptr is pointing to location of 98 (i =1) the last argument ++ptr makes it point to 99 therefore output of *e = 99 the second last argument passes pointer to 99 only and then increments its location to i=3 i.e 100...therefore output of *d = 99 and *c = 100 the second argument is pointing to location of i=3 only and then decrements to point to location of i=2..therefore output of *a =100 and *b =100.. hope you understood the sequence of outputs...:) :) On 6/22/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: r u sure the last output is also 100..for me its coming 99 On 6/22/11, udit sharma sharmaudit...@gmail.com wrote: #includestdio.h int main() { void print(int *,int *,int *,int *,int *); static int arr[]={97,98,99,100,101,102,103,104}; int *ptr=arr+1; print(++ptr,ptr--,ptr,ptr++,++ptr); return 0; } void print(int *a,int *b,int *c,int *d,int *e) { printf(%d\t%d\t%d\t%d\t%d\n,*a,*b,*c,*d,*e); } Why the output is: 10010010099100 -- Regards UDIT 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.