Re: [algogeeks] Re: finding subarray
maintaining cumulative sums of left side of array from index i in in hash, and maintaining variable for right cumulative sums at each j ( j=i+1 till n-1) and check at each value on hash will solve in O(n^2), let me know if im wrong.. surender On Wed, Jan 11, 2012 at 9:12 PM, sravanreddy001 sravanreddy...@gmail.comwrote: @Lucifer: a very good counter example involving the -ve numbers..[:)] I never thought of negative numbers while looking for solution. And I don't see a O(N) solution for this -- 1) Find the first pair (i,j) such that: sum( A[0] .. till A[i]) = sum(B[0] ... B[i]) -- ESP when there are -ve numbers, If No negative numbers its same as one provided before. And, sorting the sums comparing them like you suggested leads us to O(n^2 log n) -- 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/-/4DoZ5nKZd5wJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: MS Q
@gene in that case ur erase() should even consider diagonal elements as well, else there would be 2 islands in example surender On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote: Guys, You are making this way too hard. It's really a graph problem. The nodes are the 1's and adjacent 1's are connected by undirected edges. You must count components in the graph. So the algorithm is easy: Find a component, erase it, repeat. Count components as you go. What's an efficient way to do this with this special kind of graph we have? Just erase components by erasing 1's. So we get: #include stdio.h int a[100][100] = { {1, 1, 0, 0}, {1, 1, 0, 0}, {0, 0, 1, 1}, }; int m = 3, n = 4; // Erase the undirected component rooted at i,j. void erase(int i, int j) { // If we're off the graph or already erased, // there's nothing to do. if (i 0 || j 0 || i = m || j = n || !a[i][j]) return; // Erase! a[i][j] = 0; // Recursively erase the 4 neighbors. erase(i+1, j); erase(i-1, j); erase(i, j+1); erase(i, j-1); } void count_islands() { int i, j, n_islands = 0; // Search for a component. for (i = 0; i m; i++) { for (j = 0; j n; j++) { if (a[i][j] == 1) { // Found one! Count and erase. n_islands++; erase(i, j); } } } printf(found %d islands\n, n_islands); } int main(void) { count_islands(); return 0; } On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote: row, col, diag all 1-1-1 is a single island :) 1 1 0 0 1 1 0 0 0 0 1 1 this has only 2 islands Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com wrote: Can you give an example Say matrix is 1 1 0 0 1 1 0 0 0 0 1 1 Has it got 3 islands i.e 1-1 be in same row or they can be column wise also i.e. 5 On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com wrote: there is a matrix of 1 and 0 1 is a island and 0 is water 1-1 together makes one island calculate total no of islands -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] finding subarray
using extra space of O(n) we can do it in O(n^2) take an array for storing cumulative sums from index i till 0, then from i+1 till n-1 find summing each array value find whether it exists in array. if its so display indexes eg Array: 2,2,13,4,7,3,8,12,9,1,5 i = 3 ^ temp array: 4, 17, 19, 21 finding for cumulative sums from i+1 till i=(any of values in temp array) i = 6 ^ temp array: 8, 11, 18, 22 finding for cumulative sums from i+1 till i=(any of values in temp array) found values from i+1 till i+3 Repeating for every i, surender On Mon, Jan 9, 2012 at 11:22 PM, priyanka jaggi priyankajag...@gmail.comwrote: Given an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray. For e.g. Array: 2,2,13,4,7,3,8,12,9,1,5 Output: 4,7,3,8,12,9,1 [4+7+3+8=12+9+1] Could this be done with a complexity better than O(n^3) k is not given . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Suggest Algo for this Question
Nice Soln Lucifer, i had problem of tracking kth value when coming across two siblings, each sibling has many childs so i think a bottom up approach would be better for finding number of elements(say* y*) x finally at root we have y, if y=k then kth element is x else kth elemnt is x Surender On Sun, Dec 18, 2011 at 12:49 AM, Lucifer sourabhd2...@gmail.com wrote: @atul.. Complexity would be 2(n-k+1) = O(2*(n-k)) Basically the condition based on which the traversal is performed willow change. I have modified some part of the original post to show that: Instead of having the initial count as K have it as N-K+1 .. when taking a max-heap.. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is X then skip the processing of the tree rooted at the current node. 2) If current node is = X , then decrement the initial count i.e (n-k +1) by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of initial count 0 then the kth smallest element is X. b) If during tree traversal the value of initial count reaches 0, that means there are atleast (n-k+1) elements which are = X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element = X. On Dec 17, 1:28 pm, atul anand atul.87fri...@gmail.com wrote: @Lucifer : if for the same question , we consider a Max heap instead of Min heap then complexity of the same algo will be O(N) ... right??? On Fri, Dec 16, 2011 at 8:50 PM, Lucifer sourabhd2...@gmail.com wrote: @my previous post.. While explaining the run-time I have made an editing mistake... instead of 'N' nodes it should be 'K' nodes.. i.e. Hence, for any given bin- tree having 'K' nodes, the number of null nodes is 'K+1'. These null nodes are nothing but the nodes where the check nodeValue X failed while traversing the original tree. Hence, the total number of checks will be 2K+1 = O(2K) On Dec 16, 1:04 am, sunny agrawal sunny816.i...@gmail.com wrote: oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.com wrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for
Re: [algogeeks] Frequency Sort Algo
MinHeap with frequency of data is constructed, then sorting it. But don't see with same frequency it maintains the order of the first appeared element Regards Surender On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg ankurga...@gmail.com wrote: how can one do frequency sort . Suppose we have an integer array like 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 Then 1 is appearing 4 times 2 - 3 3- 5 4-2 5-1 Then if we sort by frequency we shud have this as result 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 How to do it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] smallest segment in a document containing all the given words
Hi how about finding this for an integer array and finding i and j such that Min(j-i) surender On Fri, Dec 2, 2011 at 3:09 AM, sravanreddy001 sravanreddy...@gmail.comwrote: An idea is to start with a heap of size k. Its tricky how to keep track of the start and end indices of the smallest length. Do not enter a duplicate element in the heap. -- 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/-/XbqIrf1Z6MUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
@myself if number of distinct characters are equal then its final string size is 2. else there are more repeated characters other than distinct characters then its 1 correct me !!! surender On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.com wrote: All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
@nitin yes i meant the same, if each different character have equal number of frequency like abcabcabc a's -3, b's - 3 c's- 3 then resultant string size is 2 else 1 surender On Sun, Nov 13, 2011 at 12:21 AM, Ankur Garg ankurga...@gmail.com wrote: @Srinivas Wat if the string is abc then it reduces to cc :) ...So size 2 can also be there.so u cant say it will be 1 always On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T tschaitanya@gmail.com wrote: On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? 1) if the string a..aaa, or bb..bb, etc... string cannot be modified 2) if string starts with ac = this can be reduced to b - aaac - aab - ac - b 3) So if string not of type (1), then it can be reduced to single character always using method 2 e.g: *aab*cacaab // first reduce aab to b *bbc*acaab // reduce bbc to c *ca*caab *bc*aab *aaab* c .. i guess u got the idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- T Srinivasa Chaitanya -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Finding the indexes of a repeated element??
this finds first and last index in pair structure in logn void repindxs(int array[],int start, int end, int k, pairint, int *p, int n/*last index*/) { if(startend) return ; int m = (start+end)/2; if( array[m] == k (m-10?-1:array[m-1] k) ) p-first = m; else if(array[m] k || (array[m]==k array[m-1]==k)) repindxs(array,start,m-1,k,p,n); if( array[m] == k (m+1n?-1:array[m+1] !=k) ) p-second = m; if(array[m]k || (array[m]==k array[m+1]==k)) return repindxs(array,m+1,end,k,p,n); } surender On Wed, Nov 9, 2011 at 1:11 AM, PIYUSH MADAN piyushmadan2...@gmail.comwrote: Suppose the array is not sorted and we have to find if an element has occurred earlier or not; and if yes, then remove it.what is the best achievable time and how? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Binary tree to BST
unlink each node in original tree in postorder, and insert these nodes in new bst tree surender On Tue, Nov 8, 2011 at 4:48 AM, vikas vikas.rastogi2...@gmail.com wrote: @ Above no need to have another array or nything binTreeToBST(node *root) { if(!root )return; node *newRoot; binTreeToBSTConv(root, newRoot); } binTreeToBSTConv(node *old, node *new) { if(!old ) return; binTreeToBSTConv(old-left, new); binTreeToBSTConv(old-rigth, new); if(old){ if(!new) new =old else{ insertNode(new, old); } } } On Nov 6, 11:30 am, Anika Jain anika.jai...@gmail.com wrote: @mohit: your algo will add assurance that the tree is balanced.. otherwise ankit's approach is sufficient. On Sat, Nov 5, 2011 at 8:49 PM, mohit verma mohit89m...@gmail.com wrote: another way is : convert binary tree to link list , sort the list and using divide and conquer approach create the BST. From link list to BST : find mid of sorted link list , make it root node and put left of it to recursive(list,start,mid-prev) and root-right=recursive(list,mid-next,last); Let me know if something is wrong in this approach. On Sat, Nov 5, 2011 at 3:48 PM, ankit agarwal ankit.agarwal.n...@gmail.com wrote: I think it's the only way as you need to traverse the entire binary tree to do it. On Oct 31, 9:45 pm, Ankuj Gupta ankuj2...@gmail.com wrote: How to convert a Binary tree to BST ? Naive way is to create each node of Binary tree one by one and keep on creating the BST. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Finding Maximum subarray in a circle
iterate it twice the length max_sub_array() { int a[] = {200 -10 -10 -10 -10 -10 100} ; int len = sizeof(a) / sizeof(a[0]); int max_sum =0; int max_till_now =0; for(int i=0; ilen*2; i++) { if(max_till_now + a[i%len] 0) max_till_now =0; else max_till_now += a[i%len]; if(max_sum max_till_now) max_sum = max_till_now } return max_sum; } surender On Wed, Nov 2, 2011 at 10:13 PM, atul anand atul.87fri...@gmail.com wrote: @praveen : thats the tricky part of this question bcoz it is a circle , this algo will fail... *[200 -10 -10 -10 -10 -10 100] *for this input , answer should be 300 (200+100). but simple kadane algorithmn will not give the desired output On Wed, Nov 2, 2011 at 4:14 PM, praveen raj praveen0...@gmail.com wrote: This can be done by kadanes algo.. //suppose n numbers has been stored in array // i is the intial point // n is the number of points to be considered in O(n) int maxsum(int a[], int N,int i,int n) { int max=0; int max_end_ here =0; int max_so_far=0; for(int j=i;jN;j++) { if(j==N) { j=0; N=n-(N-i); } if(maxa[j]) max=a[j]; } if(max0) // // check Is there any positive value or notif not then return max value..could be least negative number { for(int j=i;jN;j++) // { if(j==N) { j=0; N=n-(N-i); } max_end_ here= max_end_ here+a[j]; if(max_end_ here0) max_end_ here=0; if(max_so_farmax_end_ here) max_so_far= max_end_ here } } else { max_so_far=max; // return max value..could be least negative number } return (max_so_far); } With regards, Praveen Raj DCE-IT 735993 praveen0...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Print all path of the tree that sums up to the given value
i think the solution requires to end at a leaf node with given sum 'k'. if we gather the path from root till its leaf, once we reach leaf we have root to leaf values in our path array now create another array of same SIZE having sub_array_sum starting from root. we check the last value of sub_array_sum[n] against all values of sub_array_sum[i] i = 1..n-1; such that sub_array_sum[n]-sub_array_sum[i] = k if so print from i-1 to n in path array O(n^2) surender On Tue, Nov 1, 2011 at 10:44 PM, Navneet navneetn...@gmail.com wrote: It's most probably a DP problem on trees. To know all paths which sum up to S, we must have information about subpaths having sum smaller than S and adding the node's value making the sum S. On Nov 1, 8:36 am, Ankuj Gupta ankuj2...@gmail.com wrote: No constraint on path. Though it is not necessary that it starts from root only On Oct 31, 10:02 pm, Prakash D cegprak...@gmail.com wrote: any constraints for path? On Mon, Oct 31, 2011 at 11:19 AM, Ankuj Gupta ankuj2...@gmail.com wrote: Print all path of the tree that sums up to the given value. The path may start from any node. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Questions
@vikas ur algo will search for 1st element of 1d in whole 2d array, on worst case u'll search it in n^2, then search for all 1d elements in 2d in O(n) so whole complexity goes to O(n^2 +n) it can be reduced if we use hashing of 1d array, and count_found and while searching for 1st element of 1d in 2d array, if it's found make temp[i][j] as true(even though its not first element) and false if its not in 1d hash, and increase count_found this will reduce to O(n^2) surender On 11/1/11, vikas vikas.rastogi2...@gmail.com wrote: ok, so do it like this; 1. create boolean array boolean temp[][] = new boolean[row][column]; init(temp, true); 2. traverse the array for the 1d array of 0th index and then a recursive search if search fails, or position already contains false, return and search again boolean search(int searchArray[][], int givenArray[], int rpos, int cpos, int gpos){ if(gpos givenArray.len) return false; if(temp[rpos][cpos] == false) return false; if(searchArray[rpos][cpos] == givenArray[gpos]) { temp[rpos][cpos] = search(searchArray, givenArray, rpos +1, cpos, gpos+1)| search(searchArray, givenArray, rpos-1, cpos, gpos+1) | search(searchArray, givenArray, rpos, cpos+1, gpos+1)| search(searchArray, givenArray, rpos+1, cpos-1, gpos+1) } if(temp[rpos][cpos]) return true; if(cpos searchArray.len) search(searchArray, givenArray, rpos, cpos+1, 0); else search(searchArray, givenArray, rpos+1, 0, 0); } On Nov 1, 4:25 pm, SAMM somnath.nit...@gmail.com wrote: For example :- 2d array :: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 we hav 1d array as :-- 13 2 21 10 23 12 So the 1d array is a subset of 2d array ... On 11/1/11, vikas vikas.rastogi2...@gmail.com wrote: what do you mean by subset of 1D present in the 2D array? is it something like 3245 , the search may be 3245/ 24/ 45/ all 16 subsets need to be searched? On Oct 28, 12:02 pm, SAMMM somnath.nit...@gmail.com wrote: How do u plan to implement it ??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST in file
@asit dhal, in order of any BST is increasing order. so required is only either preorder/postorder surender On Tue, Sep 27, 2011 at 12:42 AM, Gene gene.ress...@gmail.com wrote: Here is a little program to show how it works. It's a nice little problem. There is also a coding with recursion. #include stdio.h #include stdlib.h typedef struct node_s { int data; struct node_s *left, *right; } NODE; void print_tree(NODE *tree) { if (tree == NULL) return; print_tree(tree-left); printf( %d, tree-data); print_tree(tree-right); } void save_tree(NODE *tree) { if (tree == NULL) return; printf(%d\n, tree-data); save_tree(tree-left); save_tree(tree-right); } NODE *new_node(int data) { NODE *node = malloc(sizeof *node); node-data = data; node-left = node-right = NULL; return node; } NODE *read_tree(void) { int data, sp = 0; NODE *root, *node, *last, *stack[1]; // Loop invariants: Root holds tree root. // Last holds last node added. // Stack[i] holds the unique node at // level i to which a right child might // still be added. root = last = NULL; while (scanf(%d, data) == 1) { node = new_node(data); if (root == NULL) root = node; else { // If new node has key last, it must // be the left child of last. Attach and // push onto stack because we still // may receive a right child. if (data last-data) { last-left = node; stack[sp++] = last; } // Else it has key last, so if the key is also // the deepest level waiting for a right child, it // can only be right child of the last node. else if (sp == 0 || data stack[sp - 1]-data) last-right = node; // Else it must be the right child of an ancestor. // The possible ancestors are on the stack. // Pop the stack until we find the last ancestor // with larger key and attach there. else { while (sp 1 data stack[sp - 2]-data) --sp; stack[--sp]-right = node; } } last = node; } return root; } int main(void) { print_tree(read_tree()); return 0; } On Sep 24, 8:28 pm, vikas vikas.rastogi2...@gmail.com wrote: if this is simple BST then only preorder will suffice On Sep 24, 10:16 pm, wetheart gumnaamsm...@yahoo.com wrote: You can put the array representation of binary tree directly, with some obvious modifications ofcourse :) On Sep 24, 5:38 pm, asdqwe ayushgoel...@gmail.com wrote: you can put two traversals of three (inorder, preorder or postorder) in the file.. Two traversals are enough to dedicate a particular tree. On Sep 24, 4:05 pm, Asit Dhal lipu...@gmail.com wrote: I need to print a binary search tree in file. When I will retrieve the same tree from the file. I have thought about printing in xml format like this 100 / \ 50 150 / \ / \ 30 70 120 200 Level 0 100 Level 1 50 Level 2 30 /Level2 Level 2 70 /Level 2 /Level 1 Level 1 150 Level 2 120 /Level 2 Level 2 200 /level 2 /level 1 /level 0 I don't know will this be the best solution or not. Please suggest me how to approach it or some better solution. Regards Asithttp://kodeyard.blogspot.com/- 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.
[algogeeks] print all numbers in a given range without using any loop statements, jump statements and recursion
print all numbers in a given range *without* using any loop statements, jump statements and recursion surender -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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]
based on minmax in minimum number of comparisons.. struct pa { int max; int secmax; }; struct pa getmm(int arr[], int low, int high) { struct pa mm = {-1,-1}, mml, mmr; int mid; /* If there is only on element */ if(low == high) { mm.max = arr[low]; mm.secmax = arr[low]; return mm; } /* If there are two elements */ if(high == low + 1) { if(arr[low] arr[high]) { mm.max = arr[low]; mm.secmax = arr[high]; } else { mm.max = arr[high]; mm.secmax = arr[low]; } return mm; } /* If there are more than 2 elements */ mid = (low + high)/2; mml = getmm(arr, low, mid); mmr = getmm(arr, mid+1, high); /* compare maximums of two parts*/ if(mml.max mmr.max) { int temp = mm.max; mm.max = mml.max; if(mmr.maxtemp) mm.secmax = mmr.max; else mm.secmax = temp; } else { int temp = mm.max; mm.max = mmr.max; if(mml.maxtemp) mm.secmax = mml.max; else mm.secmax = temp; } return mm; } surender On Tue, Sep 20, 2011 at 7:48 AM, Sandy sandy.wad...@gmail.com wrote: @Utkarsh: In Yogesh's code assigning a[1] to largest and second_largest in the beginning, -VE case will be handled. On Mon, Sep 19, 2011 at 12:10 PM, asdqwe ayushgoel...@gmail.com wrote: @Yogesh:fails for negative numbers.. (though I am also confused with the ques) On Sep 19, 10:38 am, Yogesh Yadav medu...@gmail.com wrote: current position is index n (say) largest=0; second_largest=0; for(i=1;i=n;i++) { if(a[i]a[n]) { if(a[i]largest) { second_largest=largest; largest=a[i];} elseif(a[i]second_largest) second_largest=a[i]; } } On Mon, Sep 19, 2011 at 2:15 AM, sagar pareek sagarpar...@gmail.com wrote: Give some examples ,i m not getting ur question On Mon, Sep 19, 2011 at 1:45 AM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: how to find second largest element than current element in an array given condition that we have to find that second largest element from index 1 to the index of the current element -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @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 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Question --
t = j-i+1; // total number bits (t) between i and j , i=2,j=6 t = 2^t-1; // value would be 2^5-1 .. 0001 t = ~t ;// ...1110 t = ti | 2^i-1 // 1000 0011 N = N t; // resets all bits between i and j to 0 in N N = N | Mi; sets bits in N with bits in M surender On Tue, Sep 20, 2011 at 1:13 PM, abhinav gupta guptaabhinav...@gmail.comwrote: You can also solve the problem by using bit operators. by using| ! . Need sm thinking in dat..No time rite nw! On Tue, Sep 20, 2011 at 1:12 PM, abhinav gupta guptaabhinav...@gmail.comwrote: Its because o/p should look like dat.Bt dats simple you can do it by multiplying bits to power(2, i) and adding all expressions.Simple! On Tue, Sep 20, 2011 at 1:09 PM, abhinav gupta guptaabhinav...@gmail.com wrote In the first loop bits are added into the array N and M .I have taken two integers n and m . Caution : declare int N[31]={0}; int M[31]={0}; int n,m,i,j; On Tue, Sep 20, 2011 at 1:02 PM, Ishan Aggarwal ishan.aggarwal.1...@gmail.com wrote: What are u doing in the first loop running for k=31 to k =0? On Tue, Sep 20, 2011 at 12:50 PM, abhinav gupta guptaabhinav...@gmail.com wrote: U can use single walker (from 0 till 31) to convert integers N and M into array of bits, then another walker from i to j to replace values. for(k=31;k=0;k++) { N[k]=n 01; M[k]=m 01; n=1; m=1; } for(k=i;k=j;k++) N[k]=M[k]; On Tue, Sep 20, 2011 at 12:44 PM, abhinav gupta guptaabhinav...@gmail.com wrote: I can tell you the logic.Take two arrays N and M, put their bits in the array. Now using i and j index replace the value of N[j] to n[i] by M[j] to M[i]. On Tue, Sep 20, 2011 at 12:33 PM, Ishan Aggarwal ishan.aggarwal.1...@gmail.com wrote: You are given two 32-bit numbers, N and M, and two bit positions, i and j.Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j). EXAMPLE: Input: N = 100, M = 10101, i = 2, j = 6 Output: N = 10001010100 -- Kind Regards Ishan Aggarwal [image: Aricent Group] Presidency Tower-A, M.G.Road,Sector-14 Gurgaon,Haryana.122015 INDIA Phone : +91-9654602663 ishan2.aggar...@aricent.com puneet.ar...@aricent.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. -- @ |3 # ! /\/ @ \./ -- @ |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. -- Kind Regards Ishan Aggarwal [image: Aricent Group] Presidency Tower-A, M.G.Road,Sector-14 Gurgaon,Haryana.122015 INDIA Phone : +91-9654602663 ishan2.aggar...@aricent.com puneet.ar...@aricent.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. -- @ |3 # ! /\/ @ \./ -- @ |3 # ! /\/ @ \./ -- @ |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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] matrix
take another matrix of same size, calculate sum at each element if a[][] is the matrix,SM[][] stores sum till that point SM[0,i] = a[0][i] SM[i,0] = a[i][0] SM[i][j] = SM[i][j-1]+SM[i-1][j]-SM[i-1][j-1]+a[i][j]; i,j=1 to n-1 track max value as u does this. surender On Sat, Sep 17, 2011 at 6:58 PM, prasanth n nprasnt...@gmail.com wrote: @ aditya kumar: can you give the algorithm about how to get the sub matrix?? i know how to get the max sum from an array..but how to do it to find the sub matrix with max sum?? On Sat, Sep 17, 2011 at 5:07 PM, aditya kumar aditya.kumar130...@gmail.com wrote: i guess kadane's algo doesnt tell u abt the subarray element instead it tells abt max sum of subarray . to get the element of subarray store the end_offset whenever your max_sum changes . On Sat, Sep 17, 2011 at 4:47 PM, sukran dhawan sukrandha...@gmail.comwrote: kadane s algo On Sat, Sep 17, 2011 at 3:25 PM, prasanth n nprasnt...@gmail.comwrote: given a matrix with +ve and -ve numbers, find the submatrix with maximum sum?? -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: algorithm problem
@ankur, does this actually connects from start station to end station?? i think ur solution creates path which could be discontinuous, but we want end to end connected path surender On Sat, Sep 17, 2011 at 5:39 AM, Ankur Garg ankurga...@gmail.com wrote: Some typos in my solution :( Use a Max heap.. first take the first 10 stations and build a* Max *heap O(10)..Heap contains distance between 2 stations . Initial Heap will contain 10 *minimum *distances with maximum of those at the top . Now 11 th comes u compare with the root of the heap . If its less than that than replace it with the top and run heapify (O(log10) ) ..keep doing the same . In the end u have 10 stations with min distance between them Complexity O(10) + O(log(10)) = O(1) ..Comparision takes constant time So total complexity O(1) Regards Ankur On Sat, Sep 17, 2011 at 5:00 AM, Dave dave_and_da...@juno.com wrote: @Pankaj: Let's number the stations from 0 to 101, where stations 0 and 101 are the end stations and stations 1 through 100 are the intermediate stations. Let a[i], i = 1, 2, ..., 100 be the distance of station i from station 0, and finally assume that the a's are increasing, i.e., that the stations are presented in order. We want to find i[1], i[2], ..., i[10] such that 0 = i[0] i[1] i[2] ... i[10] i[11] = 101. Given any x, 0 x = a[101] (the distance between the end stations), we can find the last station that is within x of station 0. Call this station i1. In other words, a[i1] = x but a[i1+1] x. Now find the last station that is within x of station i[1] and call it i[2]. Etc until you find the last station that is within x of station i10. If you get to station 101 in the process, the rest of the i's = 101. This can be done with a linear search in O(100), or using 10 binary searches in O(10 log 100). Now the problem is to find the smallest x such that I[11] = 101. We can do this with a binary search on x. Initialize xmin = a[101]/11 (that would have the 10 intermediate stations equally spaced) and xmax = a[101] and begin a loop. Let x = xmin + (xmax - xmin)/2. If x == xmin or x == xmax, break; xmax is the minimax distance between stations and i[1], ..., i[10] are the stations. Otherwise, calculate i[1] through i[11] as above. If i[11] 101, then x is too small, so set xmin = x and loop. If i[11] = 101, then x is too large, so set xmax = x and loop. Dave On Sep 16, 1:22 pm, pankaj kumar p9047551...@gmail.com wrote: You are given two end points ( consider them as two end stations at some distance ) there are 100 stations between these two . Now you need to build a train track between these two end points which includes only 10 stations and not more than that . Now the objective is to find such 10 stations such that the maximum distance between any two consecutive stations is minimum . mine solution is find all possible subset of 10 elements and answer is that subset for which sum (of distance between consecutive stations )is minimum.. is it correct or any other solution. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.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.
Re: [algogeeks] Re: Amazon ques
however maximum subarray can be found in O(n) just needs to get maximum difference in entries of each A[i] [-2]-[5] [-1]-[0, 2, 4, 6] maxdiff[-1] = 6-0 [0]-[-1, 1, 3, 7] maxdiff[0] = 7-(-1) [1]-[8, 10] maxdiff[1] = 10-8 [2]-[9] max(maxdiff[i]) = 8 surender On Sun, Sep 11, 2011 at 4:31 PM, Ankur Garg ankurga...@gmail.com wrote: Yeah :( U r right dude ...I dont think O(n) solution can exist for this problem On Sun, Sep 11, 2011 at 4:27 PM, Kunal Patil kp101...@gmail.com wrote: As the author correctly mentions it: Building the array is O(n) , but printing these intervals must be done in linear time to the number of intervals. Assuming n means number of elements in the original array There are O(n^2) possible intervals, how can you print them in O(n) ??? On Sun, Sep 11, 2011 at 4:20 PM, Ankur Garg ankurga...@gmail.com wrote: This solution is not in O(n) time :( Unfortunately interviewer wants O(n) . On Sun, Sep 11, 2011 at 4:01 PM, Kunal Patil kp101...@gmail.com wrote: @Brijesh: +1 On Sun, Sep 11, 2011 at 2:14 PM, Brijesh brijeshupadhyay...@gmail.comwrote: This is the fastest way I can think of to do this, and it is linear to the number of intervals there are. Let L be your original list of numbers and A be a hash of empty arrays where initially A[0] = [0] sum = 0 for i in 0..n if L[i] == 0: sum-- A[sum].push(i) elif L[i] == 1: sum++ A[sum].push(i) Now A is essentially an x y graph of the sum of the sequence (x is the index of the list, y is the sum). Every time there are two x values x1 and x2 to an y value, you have an interval (x1, x2] where the number of 0s and 1s is equal. There are m(m-1)/2 (arithmetic sum from 1 to m - 1) intervals where the sum is 0 in every array M in A where m = M.length Using your example to calculate A by hand we use this chart L # 0 1 0 1 0 0 1 1 1 1 0 A keys 0 -1 0 -1 0 -1 -2 -1 0 1 2 1 L index-1 0 1 2 3 4 5 6 7 8 9 10 (I've added a # to represent the start of the list with an key of -1. Also removed all the numbers that are not 0 or 1 since they're just distractions) A will look like this: [-2]-[5] [-1]-[0, 2, 4, 6] [0]-[-1, 1, 3, 7] [1]-[8, 10] [2]-[9] For any M = [a1, a2, a3, ...], (ai + 1, aj) where j i will be an interval with the same number of 0s as 1s. For example, in [-1]-[0, 2, 4, 6], the intervals are (1, 2), (1, 4), (1, 6), (3, 4), (3, 6), (5, 6). Building the array A is O(n), but printing these intervals from A must be done in linear time to the number of intervals. In fact, that could be your proof that it is not quite possible to do this in linear time to n because it's possible to have more intervals than n and you need at least the number of interval iterations to print them all. Unless of course you consider building A is enough to find all the intervals (since it's obvious from A what the intervals are), then it is linear to n THis is the solution..go through it, its very easy to understand... PS: copied from http://stackoverflow.com/questions/6967853/dynamic-programming-can-interval-of-even-1s-and-0s-be-found-in-linear-time -- 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/-/wM8Xhc1tUXQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Re: [algogeeks] stack implementation with a constraint
@bharat take two hashmaps of hash1data, freq and hash2freq,linked_list take frequency of a data from hash1, and find its list in hash2. if ur poping, reduce frequency in hash1 and in corresponding hash2 remove its entry in that list and put it in freq-1 entry and keep track of max and second max of highest frequncy value of hash2 in vars max and second_max surender On Fri, Sep 9, 2011 at 11:42 AM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: @surender: say the hash table of freq,linked_lis is as follows... 1,2-3-4 2,5-6 3,7-8 pop(7) would decrease the frequency of element 7 means that element has to be added to 2nd key i.e 2,5-6-7 here how do u get the element 7 from hash table as freq is the key element in u'r table? And after getting element u have to add 7 LinkedList linked_list=hash.get(new_freq(7)); linked_list.addLast(7); hash.add(new_freq(7),linked_list); Any better approach? On Fri, Sep 9, 2011 at 11:09 AM, surender sanke surend...@gmail.comwrote: maintain a hash of freq,linked_list linked_list consists of values of that frequency. values with same frequency comes under same list if pop of a particular value is done, then frequency is changed of that number, a new record would be created if required. maintain two values tracking max and second_max, which would track of highest frequency value. let me know ur suggestions surender On Wed, Sep 7, 2011 at 1:03 PM, kARTHIK R k4rth...@gmail.com wrote: The frequency is also stored in the heap right? So to do heapify based on frequency, first you have to spot the element on the heap. That itself will take O(n). [ Heapfying after that takes only O(log n) ] If you use a hashmap and store frequencies, and each time mostFrequent is called, do a linear search on the map, it will have the same complexity. Can anyone come up with a better solution? Karthik R, RD Engineer, Tejas Networks. On Wed, Sep 7, 2011 at 8:49 AM, *$* gopi.komand...@gmail.com wrote: HI, Need logic to implement a stack which should support push , pop , top as well as mostFrequent. mostFrequent should return the most frequently pushed element. I have provided the following logic have one general stack implementation and one Heap .. (Heapify based on frequeny not based on element value) can any one tell me the time complexity for the above logic .. as well as any other good algo for the same. Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] answer these interesting questions
explanation would be appreciated surender On Thu, Sep 8, 2011 at 12:12 AM, Piyush Grover piyush4u.iit...@gmail.comwrote: 4) a and b On Thu, Sep 8, 2011 at 12:08 AM, Piyush Grover piyush4u.iit...@gmail.comwrote: 1.)a 2.)b 3.)b 4)b On Wed, Sep 7, 2011 at 11:08 PM, Mani Bharathi manibharat...@gmail.comwrote: “Kya-Kya” is an island inhabitants of which always answer any question with two answers , one of which is true and the other is false . 1.You are walking on a road and came to a park . You ask the inhabitants Ram , Laxman and Lila , “which road will take me to the village ?”Ram says “I never speak to strangers . I am new to these parts .”Laxman says,”I am married to Lila . Take the left road .”Lila says “I am married to Ram . He is not new in these place .”Which of the following is true ?(a)Left road takes you to the village(b)Right road takes you to the village(c)Lila is married to Laxman.(d)none. 2.You find that your boat is stolen . You question three inhabitants of the island and reply as follows . John saya “I didn’t do it . Mathew did not do it .”Mathew says “I did not do it . Krishna did not do it .”Krishna says “I did not do it . I do not know who did it .” Who stole your boat ? (a)John(b)Mathew(c)Krishna(d)All three (e)none. 3.You want to speak to the chief of the village . You question three inhabitants Amar , Bobby and Charles . Only Bobby is wearing a red shirt . Amar says “I am not Bobby’s son .The chief wears a red shirt.”Bobby says “I am Amar’s father . Charles is the chief.”Charles says “The chief is one among us . I am the chief .”Who is the chief? (a)Amar(b)Bobby(c)Charles(d)None. 4.There is only one pilot in the island.You interview three men:Koik,lony and Mirna.You also notice that Koik is wearing a cap.Mirna says “Lony’s father is the pilot.Lony is not the priest’s son.”Koik says “I am the pilot.On this island only priests can wear cap.”Lony says “I am the priest’s son.Koik is not the priest .”Which of the following is true?(a)Lony is not Koik’s son(b)Koik is the pilot(c)Mirna is the pilot(d)Lony is the priest. -- 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/-/QsepdSoM9esJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] stack implementation with a constraint
maintain a hash of freq,linked_list linked_list consists of values of that frequency. values with same frequency comes under same list if pop of a particular value is done, then frequency is changed of that number, a new record would be created if required. maintain two values tracking max and second_max, which would track of highest frequency value. let me know ur suggestions surender On Wed, Sep 7, 2011 at 1:03 PM, kARTHIK R k4rth...@gmail.com wrote: The frequency is also stored in the heap right? So to do heapify based on frequency, first you have to spot the element on the heap. That itself will take O(n). [ Heapfying after that takes only O(log n) ] If you use a hashmap and store frequencies, and each time mostFrequent is called, do a linear search on the map, it will have the same complexity. Can anyone come up with a better solution? Karthik R, RD Engineer, Tejas Networks. On Wed, Sep 7, 2011 at 8:49 AM, *$* gopi.komand...@gmail.com wrote: HI, Need logic to implement a stack which should support push , pop , top as well as mostFrequent. mostFrequent should return the most frequently pushed element. I have provided the following logic have one general stack implementation and one Heap .. (Heapify based on frequeny not based on element value) can any one tell me the time complexity for the above logic .. as well as any other good algo for the same. Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: convert a word into a palindrome with minimum addition of letters to it
@sukran, string shouldn't be replaced, only addition of characters allowed On Tue, Sep 6, 2011 at 1:48 PM, sukran dhawan sukrandha...@gmail.comwrote: my soln works without increasing the string length just start with first and last character copy last character with first increment i and decrement j and contibue the procedure continue the same till u get mid element :) On Tue, Sep 6, 2011 at 12:56 PM, Atul Modi atul.a...@gmail.com wrote: can u remove letters also?as in the example 1 'o' seems to have been removed? On Tue, Sep 6, 2011 at 12:25 PM, anshu mishra anshumishra6...@gmail.comwrote: http://www.spoj.pl/problems/AIBOHP/ same problem u have asked!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Find the non-duplicate element in sorted array in O(n) time
{ 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also comes under this problem? surender On Thu, Aug 25, 2011 at 8:12 AM, Dave dave_and_da...@juno.com wrote: @Shailesh: Sir, your response is unresponsive, because the original poster specifically asked for a solution that was O(n). Please don't waste our time giving answers that so obviously do not meet the problem statement. Dave On Aug 24, 6:33 pm, smb shaileshbir...@gmail.com wrote: XOR all the elements, the answer is the number you want. On Aug 24, 5:11 pm, Don dondod...@gmail.com wrote: I assume that elements in pairs means that each value occurs exactly twice except for the one single. This algorithm is O(log n) and is nonrecursive. Writing it recursively would make it a couple of lines shorter, but because it is purely tail recursion, that is not necessary. // Given an array a of size elements in which all elements occur in pairs except for one single item, // find the single item and return its value. int findSingle(int *a, int size) { while(1) { // For an array of size 1, the only element is the single. if (size == 1) return a[0]; // The logic below won't work for size three, but it is simple to find the single. else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0]; else { // Pick the midpoint of the array int midpoint = size/2; // If we are looking at the second element of a pair, move back to the first element if (a[midpoint] == a[midpoint-1]) --midpoint; // If midpoint is not a pair, that is the single. else if (a[midpoint] != a[midpoint+1]) return a[midpoint]; // If midpoint is odd, look at left half of the array if (midpoint % 2) size = midpoint; else // If midpoint is even, look at the right half of the array { a += midpoint; size -= midpoint; } } } } On Aug 24, 4:49 am, atul purohit gonewiththe...@gmail.com wrote: Hi, A* sorted *integer array contains elements in pairs. All the pairs are complete except one element whose pair is missing. Find that element. Ex. { 1,1,2,2,2,2,3,3,4,5,5} result = 5 There is a standard solution which returns an XOR of all the elements. But this needs O(n) time complexity. The person who asked me this question said that this can be done in O(n). Maybe we can eliminate some elements. Anyone knows how to do this? Cheers, Atul- 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.
Re: [algogeeks] find a solution
concatenate both and find all permutations of that string surender On Thu, Aug 11, 2011 at 5:34 PM, Gayathri Anandan gayathriananda...@gmail.com wrote: Given two strings say AB and CD you should print all the possible combinations. Use any language. output: ABCD, ABDC, ACDB, ADBD, ADBC, ADCB etc. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Sort IT
@dave, ur converting array values into baseN and doing radix? then every time there will be N*N = 100(baseN). i think ur code doesn't works as ur checking against msd first(/) , then lsd(%) we need to exchange these operations, then it works fine. surender On Wed, Aug 3, 2011 at 3:55 PM, Dave dave_and_da...@juno.com wrote: @Arun: Look up Radix sort and then read the comments in the code. Dave On Aug 3, 4:23 am, Arun Vishwanathan aaron.nar...@gmail.com wrote: yes dave it wud be better if u cud post an explanation of what u r doing in each step..thanks On Wed, Aug 3, 2011 at 6:51 AM, payel roy smithpa...@gmail.com wrote: @Dave, Can you please explain the algo? It's getting very difficult to understand the code .. On 3 August 2011 01:14, Dave dave_and_da...@juno.com wrote: @Pankaj: Assuming generously that by N^2 you mean N*N instead of N exclusive-or 2, your very first statement is already O(N^2), as it will take that long just to set the array to zero. Here is a radix sort to sort an array x[N] containing values from 1 to N*N in O(N): int a[N], b[N], i; // initialize and tally occurrences of first radix-N digit of x[i]-1: for( i = 0 ; i N ; ++i ) a[i] = 0; for( i = 0 ; i N ; ++i ) a[(x[i]-1)/N]++; // compute starting point for each radix digit: a[N-1] = N - a[N-1]; for( i = N-2 ; N = 0 ; --i ) a[i] = a[i+1] - a[i]; // move numbers from array x to temp array b: for( i = 0 ; i N ; ++i ) b[a[(x[i]-1)/N]++] = x[i]; // initialize and tally occurrences of second radix-N digit of x[i]-1: for( i = 0 ; i N ; ++i ) a[i] = 0; for( i = 0 ; i N ; ++i ) a[(x[i]-1)%N]++; // compute starting point for each radix digit: a[N-1] = N - a[N-1]; for( i = N-2 ; N = 0 ; --i ) a[i] = a[i+1] - a[i]; // move numbers from temp array b back to array x: for( i = 0 ; i N ; ++i ) x[a[(x[i]-1)%N]++] = b[i]; // array is now sorted. Run time is O(N). Space is O(N). Dave On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote: int a[N^2]={0},i,j; for(i=0;iN^2;i++) { cinj; a[j]++; } for(i=0;iN^2;i++) { if(a[i]!=0) { while(a[i]--) { couti\t; } }- 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.- 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.
Re: [algogeeks] Amazon Question
Hi, for 1 do +1 for 0 do -1 maintain count at every index of array eg: 100110 array X 1 0 0 0 0 0 0 1 1 0 count 0 1 0 -1 -2 -3 -4 -5 -4 -3 -4 index -1 0 1 2 3 4 5 6 7 8 9 find count with same value having max index difference. -3 is count at index 4 and 8 max difference is 8-4 = 4 -4 is count at index 5 and 9 max difference is 9-5 = 4 to reduce traverse time after count calculation take a mapcount,i,j; i - first index of array having same count, j - last index of array having same count as and when u encounter count create map value with i else if already exist update j, and update max with MAX(j-i,max) Surender On Fri, Aug 5, 2011 at 2:25 PM, Arun Vishwanathan aaron.nar...@gmail.comwrote: by the way doesnt it look like an O(n^2) algo? On Fri, Aug 5, 2011 at 10:53 AM, Arun Vishwanathan aaron.nar...@gmail.com wrote: would u mind giving a short explanation of yr code too if possible? On Thu, Aug 4, 2011 at 5:38 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: I think this should worktell me if this works... void longest_0_1_substring(char *str) { int size=0,count=0,max=0,pos=0,prev=0,prev_pos=0,ptr=0,i=0,j=0; while(*str++) size++; str -= (size + 1); while(isize) { for(j=i;(j size) (str[j]==str[j+1]);++j) count++; count++; if(ptr 1) { if(count = prev) { if(prev max) { max = prev; pos = prev_pos; } } else { if(count max) { max = count; pos = i - prev; } } } prev = count; prev_pos = i; i += count; ++ptr; count = 0; } printf(substring starts at position %d and is of size %d .,pos,max); } On Thu, Aug 4, 2011 at 6:25 PM, himanshu kansal himanshukansal...@gmail.com wrote: okie...can someone do it in O(n) space...bt time shld be linear only On Thu, Aug 4, 2011 at 2:13 AM, Prakash D cegprak...@gmail.com wrote: O(1) space is t hard for this task On Thu, Aug 4, 2011 at 12:55 AM, payel roy smithpa...@gmail.comwrote: Is there any solution for the above? On 3 August 2011 21:09, coder coder i.code.program...@gmail.comwrote: ya amazon will be visiting our campus within few days -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Himanshu Kansal Msc Comp. sc. (University of Delhi) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Re: [algogeeks] Google Telephonic interview
@Anand Shastri, if tasks enter randomly in runtime, structure needs to add a member start_time, which will be different from reference_time (till now u been considering it as same start time of every task). finally GOOD work!! surender On Fri, Aug 5, 2011 at 9:42 AM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: Then that has to be mentioned in the question. Premature optimization is the root of all evil, in the words of Don Knuth. On Fri, Aug 5, 2011 at 9:38 AM, Anand Shastri anand.shastr...@gmail.com wrote: what if new task gets added every time. On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: Instead of a heap, sort the array once. Pick the first element every time, and remove it from the array, or just move the 'head pointer' ahead. On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri anand.shastr...@gmail.com wrote: /* Create a Timer Task that takes in the running time and it's associated function to be called after its running time is elapsed */ #include time.h #define NUM 5 typedef void (*funcToBeCalled)(void); typedef struct timer TIMER; struct timer { int runningTime; funcToBeCalled func; }; static TIMER timerArray[NUM]; static time_t reference; static int count; int LEFT(int index) { if(index NUM) return (index * 2 + 1); } int RIGHT(int index) { if(index NUM) return (index * 2 + 2); } static void print(void) { printf(Timer task has been called\n); } // Initialise the timer data structure void Init() { int index; count = NUM; // Note down the reference time reference = time(0); printf(reference : %ld\n, reference); // Initialise the data structure such that associate function gets // called after 3, 6, 9, 12, 15 seconds respectively. for(index = 0; index count; index++) { timerArray[index].runningTime = (index + 1) * 3; timerArray[index].func = print; } } // This function check the min heap property and arrange // the element such that at every node, root node should be // less than its right and left child element. Heapify(int index) { int left, right, minIndex; TIMER temp; left = LEFT(index); right = RIGHT(index); if(left (count) (timerArray[left].runningTime timerArray[index].runningTime)) { minIndex = left; } else { minIndex = index; } if(right (count) (timerArray[right].runningTime timerArray[minIndex].runningTime)) { minIndex = right; } if(minIndex != index) { temp.runningTime = timerArray[index].runningTime; temp.func = timerArray[index].func; timerArray[index].runningTime = timerArray[minIndex].runningTime; timerArray[index].func = timerArray[minIndex].func; timerArray[minIndex].runningTime = temp.runningTime; timerArray[minIndex].func = temp.func; Heapify(minIndex); } } // This function builds the MIN heap data structure void BuildHeap() { int len, i; len = sizeof(timerArray)/sizeof(timerArray[0]); i = (len - 1)/2; while(i = 0) { Heapify(i); i--; } Heapify(0); } // This function extract the top element of the heap // Min heap has the min element at the top always. int HeapExtract() { TIMER temp; // Swap the 0 the element with last element of the array temp.runningTime = timerArray[0].runningTime; temp.func = timerArray[0].func; timerArray[0].runningTime = timerArray[count-1].runningTime; timerArray[0].func = timerArray[count-1].func; timerArray[count-1].runningTime = temp.runningTime; timerArray[count-1].func = temp.func; count--; // Check the heap property heapify if it got violated Heapify(0); // return the minimum element of the heap return (count); } void scheduler() { time_t now; int diff_time, minIndex; while(count = 0) { now = time(0); printf(Current Time: %ld\n, time(0)); diff_time = now- reference; printf(diff_time : %ld\n, diff_time); if(diff_time = timerArray[0].runningTime) { minIndex = HeapExtract(); timerArray[minIndex].func(); } else { sleep(timerArray[0].runningTime - diff_time); } } } main() { int index, minIndex; TIMER temp; // Initialise the data structure Init(); // Build MIn heap data structure BuildHeap(timerArray); // Run the scheduler scheduler(); return; } The ouput of above code is Timer Task is about to run reference : 1312510772 Current Time: 1312510775 diff_time : 3 Timer task has been
Re: [algogeeks] Re: Amazon Question
@sunny consider *uncompressed* suffix tree, even with distinct elements maximum number of nodes with string length n formed will be 2n. once suffix tree is constructed, needs to traverse in dfs order appending the node found on the way. total complexity would be O(construction of suffix tree ) + O(traverse time). surender On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal sunny816.i...@gmail.comwrote: @shiva viknesh this is a different Question... @saurabh how is nlgn possible, total no of possible substrings are n^2 this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh for(int l = 0; l len; l++){ for(int i = 0; i len-l; i++){ int j = i+l; char temp = s[j+1]; s[j+1] = 0; printf(%s\n, s+i); s[j+1] = temp; } } saurab...@gmail.com wrote: using suffix tree this can be done in o(nlogn) though will take extra space. On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com wrote: http://geeksforgeeks.org/?p=767 On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote: how? On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote: @vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Pratima :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- 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.
Re: [algogeeks] Re: Amazon Question
* / \\ a bc /\ b c / c prints *a* comes to b, appends a with bprints *ab* comes to c ,appends ab with c prints *abc* starts with new child prints *b* prints *bc* prints *c* surender On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal sunny816.i...@gmail.comwrote: But still Printing O(N^2) substrings will take O(N^2) time isn't it ? On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote: @sunny consider *uncompressed* suffix tree, even with distinct elements maximum number of nodes with string length n formed will be 2n. once suffix tree is constructed, needs to traverse in dfs order appending the node found on the way. total complexity would be O(construction of suffix tree ) + O(traverse time). surender On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal sunny816.i...@gmail.comwrote: @shiva viknesh this is a different Question... @saurabh how is nlgn possible, total no of possible substrings are n^2 this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh for(int l = 0; l len; l++){ for(int i = 0; i len-l; i++){ int j = i+l; char temp = s[j+1]; s[j+1] = 0; printf(%s\n, s+i); s[j+1] = temp; } } saurab...@gmail.com wrote: using suffix tree this can be done in o(nlogn) though will take extra space. On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com wrote: http://geeksforgeeks.org/?p=767 On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote: how? On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote: @vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Pratima :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- 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.
Re: [algogeeks] Re: Amazon Question
@ sunny , ur right!! surender On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal sunny816.i...@gmail.comwrote: i don't find difference between your suffix tree approach and my simple O(N^2) method in both cases printf statement will be executed O(N^2) times and in Suffix Tree approach will take some extra time of construction of tree and extra space too ! On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.comwrote: * / \\ a bc /\ b c / c prints *a* comes to b, appends a with bprints *ab* comes to c ,appends ab with c prints *abc* starts with new child prints *b* prints *bc* prints *c* surender On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal sunny816.i...@gmail.comwrote: But still Printing O(N^2) substrings will take O(N^2) time isn't it ? On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote: @sunny consider *uncompressed* suffix tree, even with distinct elements maximum number of nodes with string length n formed will be 2n. once suffix tree is constructed, needs to traverse in dfs order appending the node found on the way. total complexity would be O(construction of suffix tree ) + O(traverse time). surender On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal sunny816.i...@gmail.com wrote: @shiva viknesh this is a different Question... @saurabh how is nlgn possible, total no of possible substrings are n^2 this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh for(int l = 0; l len; l++){ for(int i = 0; i len-l; i++){ int j = i+l; char temp = s[j+1]; s[j+1] = 0; printf(%s\n, s+i); s[j+1] = temp; } } saurab...@gmail.com wrote: using suffix tree this can be done in o(nlogn) though will take extra space. On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com wrote: http://geeksforgeeks.org/?p=767 On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote: how? On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote: @vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com . To unsubscribe from 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 Pratima :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- 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
Re: [algogeeks] microsoft ques
@anurag , it fails for {4,5,-2,0,-3,-4,4,2,3,5,-7}; urs calculates from index 4 to 9. but maximum product is from index 5 to 10 surender On Mon, Jul 25, 2011 at 11:38 AM, Anurag atri anu.anurag@gmail.comwrote: Time O(n) , Space O(1) int maximum_continuous_product ( int numbers[] , int size ) { int i ; int before_negative = 0 ; int current_p = 1 ; int max_p = 0 ; int is_negative = 0 ; for ( i = 0 ; i size ; i ++ ) { if ( numbers[i] 0 ) { if ( is_negative == 0 ) { is_negative = 1 ; } else { is_negative = 0 ; } if ( before_negative == 0 ) { before_negative = current_p ; current_p *= -1 ; } else { current_p *= -1 ; current_p *= before_negative ; before_negative = 0 ; } } current_p *= numbers[i] ; if ( is_negative == 0 ) { if ( current_p max_p ) { max_p = current_p ; } } if ( current_p == 0 ) { current_p = 1 ; before_negative = 0 ; is_negative = 0 ; } } return max_p ; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Shooters in a circle
here's O(1) x = n-pow(2,floor(log2(n))); pos = x*k+1; surender On Fri, Jul 22, 2011 at 1:19 PM, Interstellar Overdrive abhi123khat...@gmail.com wrote: Yes, the solution with Circular linked list works fine but it certainly involves great space considerations. I guess solving Josephus problem using dynamic programming more apt. It's O(n) as well. -- 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/-/R6u41EDvGlcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Shooters in a circle
small change here x = n-pow(2,floor(log(n))); pos = (x*k)%n+1; surender On Fri, Jul 22, 2011 at 4:54 PM, surender sanke surend...@gmail.com wrote: here's O(1) x = n-pow(2,floor(log2(n))); pos = x*k+1; surender On Fri, Jul 22, 2011 at 1:19 PM, Interstellar Overdrive abhi123khat...@gmail.com wrote: Yes, the solution with Circular linked list works fine but it certainly involves great space considerations. I guess solving Josephus problem using dynamic programming more apt. It's O(n) as well. -- 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/-/R6u41EDvGlcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Shooters in a circle
@kunal patil ur right, i forgot to mention k=2. refer http://www.exploringbinary.com/powers-of-two-in-the-josephus-problem/ surender On Fri, Jul 22, 2011 at 7:21 PM, Kunal Patil kp101...@gmail.com wrote: @surender: I assume you want to give general solution to Josephus problem in which we shoot every kth person...In that case formula for pos must be: pos = ( x*k )%n + (k-1) In current context, k=2...thus the formula which you gave also holds true..but not when k != 2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Shooters in a circle
josephus problem with mentioned k, k determines after how many persons to execute, u guys are considering k=1 as josephus problem. its with k=2 and still remains josephus problem. On Fri, Jul 22, 2011 at 12:40 AM, chetan kapoor chetankapoor...@gmail.comwrote: yeah u r wrong...the question says the person will kill the person standing next to its neighbor.. On Thu, Jul 21, 2011 at 4:16 PM, SAMMM somnath.nit...@gmail.com wrote: Consider this Example:- 1 2 3 4 5 6 7 1 In CIrcle 1 kills 2 3 kills 4 5 kills 6 7 kills 1 Remaining ppl :- 3 5 7 3 kills 5 7 kills 3 Remain- 7 This is the sequence .. i guess Isit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] interview question
needs explicit function specialisation. be careful with constant strings. T Add(T a, T b) {return a+b ;} template char* Add char* a, char* b) {return strcat((char*)a,b); } surender On Tue, Jul 19, 2011 at 10:17 PM, Anika Jain anika.jai...@gmail.com wrote: here T becomes char *.. u r trying to add two addreses here... On Tue, Jul 19, 2011 at 9:46 PM, nidhi jain nidhi.jain311...@gmail.comwrote: Consider a c++ template funtion templateclass T T Add(T a, T b) {return a+b ;} if this function is called as T c = Add(SAM, SUNG); what will happen? What is the problem in the template declaration/ How to solve the problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Microsoft
try from back end surender On Wed, Jul 20, 2011 at 9:54 PM, Soumya Prasad Ukil ukil.sou...@gmail.comwrote: Two passes over the original array is required. On 20 July 2011 08:10, SAMMM somnath.nit...@gmail.com wrote: You can do it using stack concept:-- Pop the element from the end , taking two variable index1, index2 and Ch(character to Iterate) Eg:- a1b4 here index1=4 , Ch='b', index2=1; Start filling the element of Ch from the extreme end of the array .. From right hand side . The array will look like this :- a b b b b In next iteration : Index1=index2,ch=a, index= no value( Underflow) repeat the same process giving:- a b b b b. (soln). Add element at the end .. Like character 'b' is added from the Right hand end of the array . If any bug in my approach ... comments me ... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Output
how to deal with it?? surender On Wed, Jul 20, 2011 at 9:02 PM, sunny agrawal sunny816.i...@gmail.comwrote: http://groups.google.com/group/programming-puzzles/browse_thread/thread/4fecd0d904624a0d this will clarify all doubts :) On Wed, Jul 20, 2011 at 8:52 PM, SAMMM somnath.nit...@gmail.com wrote: Yaa even if it is 8 bytes long . Compiler will treat the value 10 as 8 bytes only . It should be able to assign it to the pointer of the same size (type) .. Try to free the dynamically allocated memory just before return 0 and tell me the result after compilation . Try this :- int main() { int* p; p = (int*)malloc(sizeof(int)); *p = 10; free(p); /* Try This */ 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. -- 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.
Re: [algogeeks] Re: Find valid anagrams
sort each string according to their alphabetical order then hash it as key, for hashing use preferably linked list as value for key surender On Thu, Jul 21, 2011 at 12:58 AM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote: Use trie for dictionary.Use permutaion to generate all anagrams and check finally. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon
take two ptrs ptr1 and ptr2 pointing to head move ptr1 until 1/4th of size of list. move ptr1 and ptr2 until ptr1=null ptr2 is pointing at 3/4th surender On Tue, Jul 19, 2011 at 3:42 PM, SAMMM somnath.nit...@gmail.com wrote: Yaa this will work , you need to handle the case for odd number of nodes . For even number of node it will serve the purpose . Yaa for the second part also you can use the ratio concept fast pointer : slow pointer = 4:3 slow = ptr-next-next-next fast = ptr-next-next-next-next Here also we need to handle the case if the number of node is not a multiple of 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.
Re: [algogeeks] Re: Google interview question
@Dave awesome..! On Sat, Jul 16, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote: @Anand: Assuming that the file contains unsigned 32-bit integers. Set an integer array a[65536] to zero, read through the file and tally the numbers based on their low-order 16 bits: a[j0x]++. Since 4.3 billion exceeds 2^32, by the pigeonhole principle, there will be at least one tally, say a[k], that has a value greater than 65536. Set the array to zero again. Read through the file again. Ignore all of the numbers whose low-order 16 bits are not k, and tally numbers based on their upper 16 bits: a[(j16)0x]++. Again by the pigeonhole principle, there will be at least one number that exceeds 1. Now you know the high-order 16 bits and the low-order 16 bits of a number that occurs at least twice. You can quit the second pass as soon as you have your first tally equalling 2. Dave On Jul 15, 8:28 pm, Anand Shastri anand.shastr...@gmail.com wrote: Given a file containing 4,300,000,000 integers, how can you *find **one* that *appears* at *least **twice* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: MICROSOFT
@Dumanshu it also doesn't works, as min node doesn't satisfies bst conditions, u swap it but it again creates inconsistencies with its left subtree. void binarytreetobst(btree *root) { if(root == NULL) return; else if(root-left == NULL root-right == NULL) //base-case tree of size 1 return; else { binarytreetobst(root-left); binarytreetobst(root-right); btree* max = max_tree(root-left); if(max max-data root-data) { swap(max-data,root-data) binarytreetobst(root); return; } btree* min = min_tree(root-right); if(min min-data root-data) { swap(min-data,root-data) binarytreetobst(root); return; } } } other solutions 1. if O(n) space is allowed. fill array elements with tree elements - sort array - create BST 2. create a new BST from scratch while deleting from BT and inserting node into BST surender On Mon, Jul 18, 2011 at 10:55 PM, Dumanshu duman...@gmail.com wrote: got the code for BT to BST from a site.. btree* max_tree(btree *root) { if(root == NULL) return root; btree * current = root; while(current-right != NULL) { current = current-right; } return current; } btree * min_tree(btree *root) { if(root == NULL) return root; btree * current = root; while(current-left != NULL) { current = current-left; } return current; } void binarytreetobst(btree *root) { //base-case tree is empty if(root == NULL) return; else if(root-left == NULL root-right == NULL) //base-case tree of size 1 return; else { binarytreetobst(root-left); binarytreetobst(root-right); btree* max = max_tree(root-left); if(max max-data root-data) { int temp = root-data; root-data = max-data; max-data = temp; binarytreetobst(root-left); } btree* min = min_tree(root-right); if(min min-data root-data) { int temp = root-data; root-data = min-data; min-data = temp; binarytreetobst(root-right); } } } On Jul 18, 7:24 pm, Dumanshu duman...@gmail.com wrote: 1. //BT to BST - function used is to swap values Node* bubbleData(Node *root) { if(!root) return NULL; if(root-right) { if(root-data root-right-data) swap((root-data),(root-right-data)); root-right = bubbleData(root-right);} if(root-left) { if(root-data root-left-data) swap((root-data),(root-left-data)); root-left = bubbleData(root-left);} return bubbleData(root); } any case missing?? 3. Do we have to give an algorithm for garbage collection like Mark sweep algo or Do we have to write a code? if code, plz tell how to write? On Jul 18, 4:59 pm, Balaji S balaji.ceg...@gmail.com wrote: 1. Convert a binary tree to binary search tree inplace.. 2. Convert a DLL to a binary search tree that is balanced. 3. Implement a C++ garbage collector efficiently -- With Regards, Balaji.S- 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.
Re: [algogeeks] Re: MS: BST
@omega9 there's nothing like inorder hashing. maintain a map while traversing through in order traversal of tree and make entry of sum-value,value. i didn't thought of k/2 or k, if u have any idea pls suggest. surender On Mon, Jul 18, 2011 at 9:42 PM, omega9 tvssarma.ome...@gmail.com wrote: Can you please tell me what inorder hashing is? Do you hash all the numbers or just all those between K/2 and K? On Jul 11, 2:46 pm, aanchal goyal goyal.aanch...@gmail.com wrote: we should not deform the tree. - converting into dll and solving. - doing inorder and hashing - doing inorder and saving in array All above solutions I know, so dont post them, i dont know how to solve this using inorder and reverse inorder approach.. On Mon, Jul 11, 2011 at 3:13 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: 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. -- 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: MICROSOFT
@Damanshu for 1 / \ 2 3 / \ 4 5 / \ 67 im ending up at some non BST surender On Tue, Jul 19, 2011 at 4:06 AM, Dumanshu duman...@gmail.com wrote: @Gaurav: The best solution would be to manipulate the given BTree in place and get the BST. We don't need a separate tree but convert the existing one using the same space occupied by nodes of BT already in BST. On Jul 19, 2:06 am, Gaurav Popli gpgaurav.n...@gmail.com wrote: cant we just dotraverse using recursion and instead of printing it just pass to function which is making BST?? and is this right as someone above said first sort it and then make BST... dont we want that root of both Tree to be same or something like that...?? On Tue, Jul 19, 2011 at 2:17 AM, Dumanshu duman...@gmail.com wrote: @Balaji: for third question, were u asked to write the code? On Jul 18, 10:04 pm, Balaji S balaji.ceg...@gmail.com wrote: wats the mistake.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp:// 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.
Re: [algogeeks] Counting the ways.
i have an idea of changing each row to decimal equilant so we have an array of size n each array element has logn bits, resetting each all bits except one everytime and checking for AND of all n array it should take maximum of O(logn)^n. improvements or ideas are welcome surender On Sat, Jul 16, 2011 at 12:47 AM, Kunal Patil kp101...@gmail.com wrote: I agree with skript: Number of ways of doing this is n! One in the first row can be placed in n ways. After one in first row has been placed, we can place One in second row in n-1 ways and so on. So total num of ways is n*(n-1)*...*1 = n! One possible solution to this problem can be coded as follows: Input: integer n Output: different matrices satisfying given criteria Create an array of integers 1 to n. do { // Omega( n! ) For (i =0 to n-1) // Omega(n) print binary representation of (1 arr[i] ) upto n bits // Omega(n) } while( Next_Permutation( arr, arr+n ) ); TC: Omega ( n! ) * Omega ( n ) * omega ( n ) SC: O(n)...( I dunno [?] whether Next_permutation uses any extra space or what, so i am not considering it... [?] ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. 1B2.png324.png
Re: [algogeeks] Re: Free memory
apart from stack and heap and text/code segment, there's another segment called data segment for holding global and static vars. Data segment itself has two variants for initialised and uninitialised data(BSS). surender On Sun, Jul 17, 2011 at 5:09 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: holy sh*t . I need to switch from MinGw was using codeblocks. Thanks :) On Sun, Jul 17, 2011 at 4:02 PM, saurabh singh saurab...@gmail.comwrote: http://www.ideone.com/LmFES On Sun, Jul 17, 2011 at 3:59 PM, saurabh singh saurab...@gmail.comwrote: Machine/OS? I am pretty sure it will give. On Sun, Jul 17, 2011 at 3:09 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: local stack is different and global is different ? and runtime memory is going to memory heap that i know. Saurabh : above snippet does not give runtime error. On Sun, Jul 17, 2011 at 3:04 PM, saurabh singh saurab...@gmail.comwrote: Global too goes to stack,the data stack.Static variables also go to the stack.That's how they retain their values during function calls. On Sun, Jul 17, 2011 at 3:02 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: more generally what is the memory structure of local , global and runtime allocated variable . I guess , runtime allocation is done from memory heap , local goes in to a stack . What about global ? On Sun, Jul 17, 2011 at 2:57 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: Can we do this ? int i=12; free(i); Regards, Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 -- 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. -- Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Problem: Longest Increasing Seq code
p[i] maintains previous index from which b[i] has reached longest sequence till i. to get the actual list of non-decrease sequence, p has to be traversed through back indices for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; surender On Sat, Jul 16, 2011 at 9:06 AM, Neeraj Gupta neeraj.gupta...@gmail.comwrote: Hi Can anyone help me in understanding the following code http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp I am not able to understand what is the exact purpose of vector p in the above mentioned code. A little detail explanation will be helpful. I have already read this the basic idea of the algorithm * Let Ai,j be the smallest possible tail out of all increasing subsequences of length j using elements a1, a2, ... , ai. Observe that, for any particular i, Ai,1, Ai,2, ... , Ai,j. This suggests that if we want the longest subsequence that ends with ai + 1, we only need to look for a j such that Ai,j ai + 1 = Ai,j + 1 and the length will be j + 1. Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai + 1,k will be equal to Ai,k for k!=j+1. Furthermore, there is at most one difference between the set Ai and the set Ai + 1, which is caused by this search. Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single a 1, a2, ... , an. * ~Neeraj Hi, -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft Interview Qn
im a bit confused with child-sibling term, this expects output for A /\ B C / \ / \ DE F G 1 A / B C / / DE FG 2 A / B-- C / DEFG is output expected 1 or 2 surender On Sun, Jul 17, 2011 at 1:32 AM, DK divyekap...@gmail.com wrote: void convert(Node * root, Node* sibling) { if(root == NULL) return; convert(root-left, root-right); convert(root-right, NULL); root-right = sibling; } convert(root, NULL); -- 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/-/UTKqLB7fawgJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
@rishab, here it generates numbers which are powers of 2 until n gets to 0 int bit_generator(); // function which returns 1 and 0 with equal probabilities int generator(int n) { int generated_num[10],i; int lg = (int)floor(log(n)); n -= pow(lg,2); int m = 0; i=0; if(n==0)return 0; while(ilg) { m*=10; m+=bit_generator(); i++; } return m + generator(n); } surender On Fri, Jul 15, 2011 at 10:58 PM, Rishabh Maurya poofiefoo...@gmail.comwrote: but suppose you have to generate numbers between [1,513] then also it would generate numbers them each with probability 1/1024 which could make a big difference and I feel the above solution to be incorrect . May be we could think of a better one . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Linked list
count number of elements from both lists and reverse list with minimum number of elements, go ahead with checking and deleting linearly surender On Fri, Jul 15, 2011 at 10:38 PM, Nishant Mittal mittal.nishan...@gmail.com wrote: delete all the numbers found in list2 from list1 recursively or iteratively Also optimize ur algo when list1 is sorted in ascending order and list2 is sorted in descending order -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Linked list
if lists are unordered, make a map of list2 and during traversal of list1 search for map, if found delete that node surender On Sat, Jul 16, 2011 at 2:02 AM, Nishant Mittal mittal.nishan...@gmail.comwrote: @surender thanx for ur algo but tell me about the 1st part when numbers are not sorted. i think if we apply merge sort on both the list then it would be easy to delete after sorting. correct me if i m wrong On Sat, Jul 16, 2011 at 12:40 AM, surender sanke surend...@gmail.comwrote: count number of elements from both lists and reverse list with minimum number of elements, go ahead with checking and deleting linearly surender On Fri, Jul 15, 2011 at 10:38 PM, Nishant Mittal mittal.nishan...@gmail.com wrote: delete all the numbers found in list2 from list1 recursively or iteratively Also optimize ur algo when list1 is sorted in ascending order and list2 is sorted in descending order -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] MS
its failing for 9*12 with n=7, if i take max square considered of hcf(9,12), left space is 6*6 and 3*3. i'll have more left space than what i consider three 4*4 squares, four 1*1 squares. leftspace is 1*5. i think needs different trick surender On Mon, Jul 11, 2011 at 9:59 PM, Yogesh Yadav medu...@gmail.com wrote: largest size of square would be = H.C.F of width and height . now with size known we have to just arrange squares this can be done such that we can make a big square by adding them... for ex 1st square can be made by just (1 square) 2nd square can be made by adding 3 sqaures around it like 1 2 //suppose 2,3,4 are newly addded squares 4 3 3rd square can be made by adding 5 sqaures around it like 1 2 5 3 4 6 9 8 7 4th square can be made by adding 7 sqaures around it like 1 2 5 10 3 4 6 11 9 8 7 12 13141516 and so on so we have to first check the no of squares and try to make largest possible square...*we have to check also that the largest possible square should not exceed either length or breadth.*.. and then we can add rest around it anywhere in this case height =3, width=2 so HCF=1 hence side of square will be 1 and n=5 given ...so largest possible square can be of 4 and rest can be added around it... On Sun, Jul 10, 2011 at 10:44 PM, vaibhav shukla vaibhav200...@gmail.comwrote: with n=(height*width)/side^2 .. u can calculate the side if n would be given. On Sun, Jul 10, 2011 at 10:37 PM, vaibhav agarwal vibhu.bitspil...@gmail.com wrote: @vaibhav this fails as n will be provided in the question. On Sun, Jul 10, 2011 at 9:56 PM, vaibhav shukla vaibhav200...@gmail.com wrote: wastage can be minimized if side of square is maximized. so largest size of square would be = H.C.F of width and height . and also number of squares needed will be = (width*height)/side^2 . On Sun, Jul 10, 2011 at 9:11 PM, Akshata Sharma akshatasharm...@gmail.com wrote: Given a rectangle with known width and height, design an algorithms to fill the rectangle using n squares(n is integer, also given) and make sure in the result the wasting area is minimized. Length of square doesn't have to be integer. I.e, given width=3,height=2,n=5, one solution is that rectangle can be filled with five 1x1 squares and the wasting area is 1. Another solution could be filled with five 0.9x0.9 squares, but the wasting area is more than first solution. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: MS: BST
i extend anurag's idea, instead of using an extra array,use map with keys (k-ai , ai). while traversing through a, check if element found in map. if found print pairs else add entry in map. surender 2011/7/12 ●αηυяαg ∩ ℓιƒє ≈ Φ anuragmsi...@gmail.com In order traversal results in a sorted list of elements of BST say [a,b,c,d,e]. make another array containing [k-a,k-b,k-c,k-d,k-e].Reverse yeilds [k-e,k-d,k-c,k-b,k-a]. Now apply the standard merge function (Merge sort). on [a,b,c,d,e] [k-e,k-d,k-c,k-b,k-a]. Finally adjacent equal entries represent a valid pair. U can see that each valid pair will be repeated twice (select only one). In case in the BST there is an entry k/2 then you must find its duplicate by a linear time search to find its correctness. :) -- 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/-/C1MPFDKg1P8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] microsoft ques
space o(2n) int LSM() { int a[] = {2,-8,-3,1,2}; int b[50],b1[50]; int n = sizeof(a)/sizeof(a[0]); int i=0; b[0]=a[0]; for(i=1;in;i++) { if(b[i-1]==0) b[i]=a[i]; else b[i]*=a[i]; } b1[n-1] = a[n-1]; for(i=n-2;i=0;i--) { if(b1[i+1]==0) b1[i]=a[i]; else b1[i]*=a[i]; } int m=INT_MIN; for(i=0;in;i++) m = ( (b[i]b1[i])?(b[i]m?b[i]:m):(b1[i]m?b1[i]:m) ); return m; } surender On Thu, Jul 14, 2011 at 8:17 AM, Aakash Johari aakashj@gmail.comwrote: typo: for Min[i] change max(...) to min(...) On Tue, Jul 12, 2011 at 11:09 PM, Neeraj Gupta neeraj.gu...@nsitonline.in wrote: Oppalis algo- Please let me know if there is a bug in it. http://www.ideone.com/u1m07 On Wed, Jul 13, 2011 at 11:36 AM, Aniket Dutta aniketdutt...@gmail.comwrote: @sunny: right thanks for correcting On Wed, Jul 13, 2011 at 11:33 AM, sunny agrawal sunny816.i...@gmail.com wrote: @Aniket Dutta Solution for your case will be 96 Algorithm Posted by Oppilas will do and is O(n). On Wed, Jul 13, 2011 at 11:28 AM, Aniket Dutta aniketdutt...@gmail.com wrote: @vaibhav: Sir ur algo fails in this array {2,-8,-3,1,2} it should give answer as 24 but ur algo gives 2 On Wed, Jul 13, 2011 at 11:02 AM, varun pahwa varunpahwa2...@gmail.com wrote: please ignore my previous post that solution is wrong. On Wed, Jul 13, 2011 at 11:01 AM, sameer.mut...@gmail.com sameer.mut...@gmail.com wrote: @kranthi : d solution u ve given is only for 2 continuous elements.. wr as d question doesnt limit it to 2.. It can be d product of any no. of continuous elements. So if the array is 200, 5, -2, -3, -1 den ans shd be 200*5*-2*-3 = 6000 N if m workin ur algo in d right way, den it ll give 1000 On Wed, Jul 13, 2011 at 10:52 AM, kranthi kumar damarlakran...@gmail.com wrote: I think this is the solution what u need U can do in O(n) time... #includeiostream using namespace std; main() { int a[7] = { 0, 0, 0, 19, 380, -1, 2}; int prod, nprod; bool x = false; for(int i=0;i6;i++) { nprod = a[i] * a[i+1]; coutnprodendl; if( x == false) { x = true; prod = nprod; } else if( x== true prod nprod ) prod = nprod; } cout\nResult: prod; } -- Regards: --- D Kranthi kumar Computer Science Engg. 1st Mtech, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.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 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group,
Re: [algogeeks] Re: GOOGLE Q
Hi, here i maintained two pair of indexes with respect to a and b, reply if u found any test case which fails.. int npairs() { int a[] = {0,1,4,5,9,11,20}; int b[] = {0,2,3,6,8,11,15}; int c[20]; int len = sizeof(a)/sizeof(a[0]); int i1,j1,i2,j2; i1=len-1; j1=len-2; i2=len-2; j2=len-1; int count = 0; c[count++] = a[len-1]+b[len-1]; //obvious while(count=len) { if( (a[i1-1]+a[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) ) { c[count++] = a[i1-1]+b[j2-1]; //highest sum with higher numbers have exhausted i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1; continue; } if(a[i1]+b[j1] = a[i2]+b[j2] ) { c[count++] = a[i1]+b[j1]; j1--; } else { c[count++] = a[i2]+b[j2]; i2--; } } for(int i =0;ilen;i++) printf(%d ,c[i]); return 0; } surender On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal sunny816.i...@gmail.comwrote: A = 0, 1, 4, 5, 9, 11, 20 B = 0, 2, 3, 6, 8, 13, 15 (20, 15) (20, 15) - (20,15) (20,13) (11,15) - (20,13) (20,8) (11,15) - (20,8) (20,6) (11,15) - assume (20,6) (20,3) (11,15) - (11,15) (20,3) (9,15)- (9,15) (20,3) (5,15)- (20,3) .problem (11,13) has higher value but did i missed something ?? -- 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.
Re: [algogeeks] Re: GOOGLE Q
small mistake change a to b if( (a[i1-1]+b[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) ) surender On Mon, Jul 11, 2011 at 3:54 PM, DK divyekap...@gmail.com wrote: @surender: Your algo fails. See the counterexample posted by Sunny. -- 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/-/ITTX48LIzcUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Random Number Generator
if b-a is exactly 2^k-1 , k0 then a + k bits (each bit is set using rand(0 1) ) with equal probability surender On Thu, Jul 7, 2011 at 1:20 PM, Nitish Garg nitishgarg1...@gmail.comwrote: Yes, Random(0, 1) gives values 0 or 1 only with equal probabilities. But your solution won't work. -- 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/-/rBDR-cunF0EJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Random Number Generator
@nitish i think all above meant 3+rand(0,1)+rand(0,1)+rand(0,1) surender On Thu, Jul 7, 2011 at 12:36 AM, Nitish Garg nitishgarg1...@gmail.comwrote: If I understood you properly, Random(a,b)=(b-a)*Random(0,1)+**a -Random(3, 6) = (3)*Random(0, 1) + 3 = 3 + 3 = 6 or 0 + 3 = 3 Just generates 3 and 6 with equal probability, what about 4 and 5? -- 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/-/I5enuEx37eQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] help to code
val = 2*3*5*7*11 for(i = 0 to n-1) if(val%a[i] == 0) count++,sum+=a[i]; surender On Tue, Jul 5, 2011 at 10:10 PM, Rajeev Bharshetty rajeev.open.1...@gmail.com wrote: Clarification : The number (count) is the number of elements between 1 and n which are not evenly divisible by 5 prime numbers and the result is the sum of all the numbers between 1 and n which are not evenly divisible by 5 prime numbers . Right??? For Example : if n=5 then count -2 (i.e 1 and 3 ) and result = 5 If I am wrong ,Please Correct me and give me the outputs expected Thank You Rajeev N B On Tue, Jul 5, 2011 at 12:17 PM, shiv narayan narayan.shiv...@gmail.comwrote: Write a program that accepts an input integer n, and calculates the number and sum of all the numbers between 1 and n (inclusive) that are NOT evenly divisible by ANY of the first 5 prime numbers (2,3,5,7,11). The program should print out a clearly labeled count and sum my code is : it is not giving correct result #include iostream #includeconio.h using namespace std; int main() { int userInteger = 0; cout Enter A Number endl; cin userInteger; // Ask For a number from the user if (userInteger 0) // Is the number valid? { int result = 0; int prime[5] = { 2, 3, 5, 7, 11 }; int a = 1, count = 0; while (a userInteger) // Looping to user's input { int b = 0; while (b 5) // Looping the prime numbers array { if (a % prime[b]) { result += a; // If Not evenly divisible by prime number at index 'b' count++; } b++; } a++; // Increment the counter } cout Numbers Not evenly divisible by 5 prime numbers: count endl; cout The Sum of numbers not evenly divisible by 5 prime numbers: result endl; } getch(); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: VIRTUAL INHERITANCE
its two ints from X and Y classes :8 2 copies of int from Base class via Class X and Class Y :8 surender On Tue, Jul 5, 2011 at 10:39 PM, oppilas . jatka.oppimi...@gmail.comwrote: @T3rminal Then how would you explain size of Z in case of normal inheritance( sizeof(Z)=16 On Mon, Jul 4, 2011 at 4:08 AM, T3rminal piyush@gmail.com wrote: @abc abc 4th class= two ints from X and Y classes + one int from base class( as this class is shared ) + 2 virtual pointers of X and Y classes. According to your logic it should be 12 On Jul 3, 2:24 pm, abc abc may.i.answ...@gmail.com wrote: In the second case , the size of vptr will be added to each and every object . 1st class = one int :4 2nd class = one int +one int from base + vptr =12 3rd class = one int + one int from base + vptr =12 4th class =one int from each base class + one int from each of the grand parent +one vptr =20 On Sun, Jul 3, 2011 at 2:43 PM, himanshu kansal himanshukansal...@gmail.com wrote: class Base { public: int a; }; class X: public Base { public: int x; }; class Y: public Base { public: int y; }; class Z:public X,public Y { }; int main() {coutsizeof(Base)endl; cout sizeof(X) endl; cout sizeof(Y) endl; cout sizeof(Z) endl; } o/p is 4 8 8 16... which is absolutely fine. but the problem arises here class Base { public: int a; }; class X:virtual public Base { public: int x; }; class Y:virtual public Base { public: int y; }; class Z:public X,public Y { }; int main() {coutsizeof(Base)endl; cout sizeof(X) endl; cout sizeof(Y) endl; cout sizeof(Z) endl; } o/p is 4 12 12 20 why the size is 12 and 20 for x and Zdoes this is because that some sort of VPTR IS maintained in the classif yes then then what does that points to PS:HERE.i am talking about virtual inheritanceNOT ABOUT VIRTUAL FUNCTIONS... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Amazon Telephonic Interview Questions
chk_bst doesnt works as its checking only for its immediate child's values. i think inorder non decreasing sequence checking would require here which is iteratively programmed surender On Thu, Jun 30, 2011 at 4:05 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: 1. int chk_bst(node *root) { if(root) { enqueue(root); while(!isempty()) { p=dequeue(); if(p-left) { if(!(p-left-data p-data)) return 0; enqueue(p-left); } if(p-right) { if(!(p-right-data = p-data)) return 0; enqueue(p-right); } } } return 1; } 2. void mirror(node **root) { if(root) { enqueue(*root); while(!isempty()) { *p = dequeue(); if(*p-left) enqueue(*p-left); if(*p-right) enqueue(*p-right); swap(*p-left,*p-right); } } } On Thu, Jun 30, 2011 at 2:12 PM, vikas mehta...@gmail.com wrote: for 1 i did implement exactly the same algorithms. and for 2 i donot know why but at that time i was not able to implement it iteratively and hense implemented its recursive version only. -- 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/-/hJswdQGammMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Telephonic Interview Questions
seems its failing for 3 2 5 1 4 N N Surender On Mon, Jul 4, 2011 at 3:12 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: @surender: in the while loop all the nodes are being checked...please tell me where u r stuck??? On Mon, Jul 4, 2011 at 2:13 PM, surender sanke surend...@gmail.comwrote: chk_bst doesnt works as its checking only for its immediate child's values. i think inorder non decreasing sequence checking would require here which is iteratively programmed surender On Thu, Jun 30, 2011 at 4:05 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: 1. int chk_bst(node *root) { if(root) { enqueue(root); while(!isempty()) { p=dequeue(); if(p-left) { if(!(p-left-data p-data)) return 0; enqueue(p-left); } if(p-right) { if(!(p-right-data = p-data)) return 0; enqueue(p-right); } } } return 1; } 2. void mirror(node **root) { if(root) { enqueue(*root); while(!isempty()) { *p = dequeue(); if(*p-left) enqueue(*p-left); if(*p-right) enqueue(*p-right); swap(*p-left,*p-right); } } } On Thu, Jun 30, 2011 at 2:12 PM, vikas mehta...@gmail.com wrote: for 1 i did implement exactly the same algorithms. and for 2 i donot know why but at that time i was not able to implement it iteratively and hense implemented its recursive version only. -- 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/-/hJswdQGammMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Telephonic Interview Questions
think it might work.. its a variant of in order iterative version.. checking each time previous value from current node's data bool isBST(tree *t) { if(!t) return true; bool done = false; int last_value = INT_MIN; Stack s; while(!done) { if(t) { s.push(t); t=t-left; } else if(!s.empty()) { t = s.pop(); if(last_value t-data) return false; else last_value = t-data; t=t-right; } else done = true; } return true; } surender On Mon, Jul 4, 2011 at 3:34 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: @surender: ok man...got it...thanks :) On Mon, Jul 4, 2011 at 3:28 PM, surender sanke surend...@gmail.comwrote: seems its failing for 3 2 5 1 4 N N Surender On Mon, Jul 4, 2011 at 3:12 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: @surender: in the while loop all the nodes are being checked...please tell me where u r stuck??? On Mon, Jul 4, 2011 at 2:13 PM, surender sanke surend...@gmail.comwrote: chk_bst doesnt works as its checking only for its immediate child's values. i think inorder non decreasing sequence checking would require here which is iteratively programmed surender On Thu, Jun 30, 2011 at 4:05 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: 1. int chk_bst(node *root) { if(root) { enqueue(root); while(!isempty()) { p=dequeue(); if(p-left) { if(!(p-left-data p-data)) return 0; enqueue(p-left); } if(p-right) { if(!(p-right-data = p-data)) return 0; enqueue(p-right); } } } return 1; } 2. void mirror(node **root) { if(root) { enqueue(*root); while(!isempty()) { *p = dequeue(); if(*p-left) enqueue(*p-left); if(*p-right) enqueue(*p-right); swap(*p-left,*p-right); } } } On Thu, Jun 30, 2011 at 2:12 PM, vikas mehta...@gmail.com wrote: for 1 i did implement exactly the same algorithms. and for 2 i donot know why but at that time i was not able to implement it iteratively and hense implemented its recursive version only. -- 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/-/hJswdQGammMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Implementing QUEUE with Singly link list
always maintain front and rear pointers, updating them accordingly during insertion and deletion can achieve this in O(1) surender On Mon, Jul 4, 2011 at 9:59 PM, vaibhav shukla vaibhav200...@gmail.comwrote: How to implement a QUEUE using a singly link list such that the operations ENQUEUE and DEQUEUE takes O(1) time ? -- best wishes!! Vaibhav Shukla -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: VIRTUAL INHERITANCE
@t3erminal u r right!!! thanks surender On Mon, Jul 4, 2011 at 4:16 PM, T3rminal piyush@gmail.com wrote: @himanshu: http://en.wikipedia.org/wiki/Virtual_inheritance Go through the last paragraph before reference. On Jul 4, 12:02 pm, himanshu kansal himanshukansal...@gmail.com wrote: @piyush:what does this two virtual pointers storing???nd how does they help in eliminating ambiguity?? On Mon, Jul 4, 2011 at 4:08 AM, T3rminal piyush@gmail.com wrote: @abc abc 4th class= two ints from X and Y classes + one int from base class( as this class is shared ) + 2 virtual pointers of X and Y classes. On Jul 3, 2:24 pm, abc abc may.i.answ...@gmail.com wrote: In the second case , the size of vptr will be added to each and every object . 1st class = one int :4 2nd class = one int +one int from base + vptr =12 3rd class = one int + one int from base + vptr =12 4th class =one int from each base class + one int from each of the grand parent +one vptr =20 On Sun, Jul 3, 2011 at 2:43 PM, himanshu kansal himanshukansal...@gmail.com wrote: class Base { public: int a; }; class X: public Base { public: int x; }; class Y: public Base { public: int y; }; class Z:public X,public Y { }; int main() {coutsizeof(Base)endl; cout sizeof(X) endl; cout sizeof(Y) endl; cout sizeof(Z) endl; } o/p is 4 8 8 16... which is absolutely fine. but the problem arises here class Base { public: int a; }; class X:virtual public Base { public: int x; }; class Y:virtual public Base { public: int y; }; class Z:public X,public Y { }; int main() {coutsizeof(Base)endl; cout sizeof(X) endl; cout sizeof(Y) endl; cout sizeof(Z) endl; } o/p is 4 12 12 20 why the size is 12 and 20 for x and Zdoes this is because that some sort of VPTR IS maintained in the classif yes then then what does that points to PS:HERE.i am talking about virtual inheritanceNOT ABOUT VIRTUAL FUNCTIONS... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Himanshu Kansal Msc Comp. sc. (University of Delhi) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] please explain
why two loops, find max and min and returns its difference surender On Fri, Jul 1, 2011 at 11:32 AM, sunny agrawal sunny816.i...@gmail.comwrote: in function it is pointer pointing to an array of 6 elements , pointer have size equal to word size in the system which is 4bytes for 32 bit operating system in main it is array of 6 integers so 24 bytes Don't get confused with same names, see the scope and type of arr in both On Fri, Jul 1, 2011 at 11:28 AM, shady sinv...@gmail.com wrote: why is the value of sizeof(arr) in maxdiff function = 4 ? where as in main function it is 24 On Fri, Jul 1, 2011 at 11:05 AM, Vishal Thanki vishaltha...@gmail.comwrote: Rujin is right, here is the code which compiles.. vishal@ubuntu:~/progs/c\ 11:04:37 AM $ cat alg.c #includestdio.h int maxdiff(int arr[]); int main() { int p,arr[]={2,4,1,6,23,4}; p=maxdiff(arr); printf(\n MAX Diff is \t %d,p); return 0; } int maxdiff(int arr[]) { int diff=0,len,i,j; unsigned p; len=sizeof(arr)/sizeof(arr[0]); for(i=0;ilen;i++) { for(j=i;jlen;j++) { p=arr[j]-arr[i]; if((p-diff)0) diff=p; } } return diff; } vishal@ubuntu:~/progs/c\ 11:04:40 AM $ gcc alg.c -Wall On Fri, Jul 1, 2011 at 7:20 AM, varun pahwa varunpahwa2...@gmail.com wrote: actually u r passing arr,and receiving arr[] which actually receives the first element address. So arr will be a reference to first address. so its size will be 4 bytes and arr size will also be 4 bytes. so ur len contains only 1. so ur loop runs only once.i hope it clears. On Thu, Jun 30, 2011 at 4:49 PM, ashwini singh asingh...@gmail.com wrote: still it's not working On Thu, Jun 30, 2011 at 4:42 PM, Rujin Cao drizzle...@gmail.com wrote: int maxdiff(int ); int maxdiff(int arr[]); The signatures of maxdiff function are not the same. On Fri, Jul 1, 2011 at 6:53 AM, ashwini singh asingh...@gmail.com wrote: this code gives an error ([Warning] passing arg 1 of `maxdiff' makes integer from pointer without a cast) . Please explain the reasons. #includestdio.h #includeconio.h int maxdiff(int ); main() { int p,arr[]={2,4,1,6,23,4}; p=maxdiff(arr); printf(\n MAX Diff is \t %d,p); getch(); } int maxdiff(int arr[]) { int diff=0,len,i,j; unsigned p; len=sizeof(arr)/sizeof(arr[0]); for(i=0;ilen;i++) { for(j=i;jlen;j++) { p=arr[j]-arr[i]; if((p-diff)0) diff=p; } } return diff; } -- with regards, Ashwini kumar singh ECE Final yr. 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Ashwini kumar singh ECE Final yr. MNNIT Allahabad Mobile: 7505519402 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.