Re: [algogeeks] Interview Question
For the 2nd ques, wat i think is the interviewer has kept the restriction of not moving the data since you may have a linked list about which you donot have much information about the structure of the node of the list(only know about the next pointer) and hence you cannot move the data. For that, you can free the middle node and copy the last node bit by bit at the location of the middle node. If you still dont want to use the method above, you will have to free the middle node and reallocate the next node at the location of the middle node. For this wat i could think was to use the realloc() and put it in a while loop and terminate the loop only when the address returned matches with the address possesed by the middle node. But this method is not efficient and also unwise. If anyone can think of something better, he/she is invited -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Problem
we can merge the 2 arrays in sorted manner. Now from the 2nd last number,we can have the first pair (last,second last).From the 3rd last,we can have 2 pairs (last,3rd last) and (2nd last,3rd last). similarly we will keep on taking till we get n pairs. time complexity: O(2n+n)- O(n) space complexity: O(2n)-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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array Problem
ignore my last post :( -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
@Amir: how you have found this relation dp[i][j]=dp[i-1][j]+dp[i][j-1] i am not able to understand it. Plz explain it. thanx On Tue, Jul 13, 2010 at 3:39 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: dp[i][j] is the number of strings that have i As and j Bs dp[0][0]=1; // s= for (i=1;i=n/2;i++) dp[i][0]=1; // s=AAA... for (i=1;i=n/2;i++) dp[0][i]=0; // the 2nd constraint for (i=1;i=n/2;i++) for (j=1;j=n/2;j++) if (ji) dp[i][j]=0; // the 2nd constraint else dp[i][j]=dp[i-1][j]+dp[i][j-1]; dp[n/2][n/2] would be the result -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the duplicate
we can do one thing. compare first element with all others. if it matches with any of them, we have found our number, else leave the first number and now the required number is available (n/2)+1 times in the rest of the array, which can be found 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorting range of numbers in O(n)
i dont think counting sort can be applied since its time cpmplexity is O(n+k) where numbers are in the range 1...k and here k=O(n^2). so the overall complexity will again go to O(n^2) :( On Mon, Aug 2, 2010 at 10:22 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: Counting Sort. On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote: There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
int num_of_BST(int n) { int sum=0; int left,right,root; if(n=1) return 1; else { for(root=1;root=n;root++) { left=num_of_BST(root-1); right=num_of_BST(n-root); sum+=left*right; } } return sum; } On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote: Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Amazon: sort array
Given an array of n elements and an integer k where kn. Elemnts {a[0].a[k] and a[k+1].a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon: sort array
@anand: this code will not work when n is not power of 2. check for this example: {2, 4, 55, 25, 15} Output was: 0 4 0 2 1 3 0 1 2 3 2 4 25 55 15 0 0 0 ascending order -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.