Re: [algogeeks] Re: Amazon Question
10 4 5 2 7 6 11 1 39 8 12 13 14 15 For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! On Tuesday, 19 April 2011 05:33:26 UTC+5:30, ashgoel wrote: This essentially becomes a two pass algo first find the parent and grand parent and find children of all the siblings of the parent Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the grandparent) and descend to the other child (to an aunt or uncle). The children of that node are the cousins. Dave On Apr 13, 11:13 pm, priya mehta priya.mehta...@gmail.com wrote: i hope all the cousins means all the nodes on the same level, so it should be done using level order traversal. On Thu, Apr 14, 2011 at 8:38 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes, this is correct, and to move the data in the array, its simple, just do a traverse and populate the array.. another way is to put data into queue and putting only one level of data at a time, this reduces the space consumption but... only by half... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. On Tuesday, 19 April 2011 05:33:26 UTC+5:30, ashgoel wrote: This essentially becomes a two pass algo first find the parent and grand parent and find children of all the siblings of the parent Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the grandparent) and descend to the other child (to an aunt or uncle). The children of that node are the cousins. Dave On Apr 13, 11:13 pm, priya mehta priya.mehta...@gmail.com wrote: i hope all the cousins means all the nodes on the same level, so it should be done using level order traversal. On Thu, Apr 14, 2011 at 8:38 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes, this is correct, and to move the data in the array, its simple, just do a traverse and populate the array.. another way is to put data into queue and putting only one level of data at a time, this reduces the space consumption but... only by half... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. On Tuesday, 19 April 2011 05:33:26 UTC+5:30, ashgoel wrote: This essentially becomes a two pass algo first find the parent and grand parent and find children of all the siblings of the parent Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the
[algogeeks] Re: Microsoft interview question
@Gaurav: you are taking ia and ib as int so they will have 32 bits in Java. So you can not set the bits for numbers in the array greater than 32. e.g if you have a[i]=59876 so you would want to set the 59876th bit in ia : ia=ia | (159876) but that is not possible. How do you handle this? Also how do you handle the case for negative numbers?? What I think we can do is: If we take ia and ib as BigInteger in Java then we don't have that constraint of 32 bits. I tried it out it works for large no as 35000 instantly. But that still doesn't solve the problem of -ve numbers. regards Abhishek Khanna On May 20, 1:42 am, GAURAV CHAWLA togauravcha...@gmail.com wrote: we can do it bitwise... i can set the corresponding bit by 1 of any int ... lets take int ia,ib=0; and set the a[i]th bit of ia as 1 , and similar for bth array and ib ... and finally check.. if(ia==ib){permutation of each other} hope this will work.. On Sun, May 20, 2012 at 1:39 AM, malay chakrabarti m1234...@gmail.comwrote: dat defeats the o(1) space constraint. :-) On May 19, 2012 8:05 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: @malay --- we can do it by precomputing the prime arrays On Sun, May 20, 2012 at 1:10 AM, malay chakrabarti m1234...@gmail.comwrote: method is ryt but to find ith prime u cannot to it in constant time. On May 19, 2012 7:30 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- HARSHIT PAHUJA M.N.N.I.T. ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, GAURAV CHAWLA +919992635751 +919654127192 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! the first cousins are 9,8 not 12,13...otherwise the question becomes really simple :) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question
bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[] path, int pos, vectorint firstCousins) { if ((!pThis) || (!pRoot)) return false; if (pRoot-data!=pThis-data) { path[pos] = pRoot; if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins)) return findCousins(pRoot-left, pThis, path, pos+1, firstCousins); } if (pos2) return false; //this node is at level 0 or level 1 struct node* pGP = path[pos-2]; struct node *pParent = path[pos-1]; struct node *pUncle = NULL; if (pParent == pGP-left) { pUncle = pGP-right; }else pUncle = pGP-left; if (pUncle-left) firstCousins.add(pUncle-left-data); if (pUncle-right) firstCousins.add(pUncle-right-data); return true; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 5:41 PM, Ashish Goel ashg...@gmail.com wrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! the first cousins are 9,8 not 12,13...otherwise the question becomes really simple :) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft interview question
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations of each other. Space = O(1) Time=O(n) I think this should work. Please correct me if you find mistakes. On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote: U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- * * *Kalyanasundaram N* *BE 2nd year, CSE* *College of Engineering Guindy,* *Chennai-600025* * * -- 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/-/i-WLn7rdzDYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft interview question
No way u can do it in O(1) space and O(n) time.sols above are not gonna work..yeah, it is possible in O(n) space and O(n) time. On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft interview question
Dave, Cant we have a hash table with the item as key and its count as value (walk over array A and build HT). For permutation check, walk over second array and start reducing the count and remove when count becomes zero for that particular key. If some char not there in HT, return false, else return true. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote: @Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations of each other. Space = O(1) Time=O(n) I think this should work. Please correct me if you find mistakes. On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote: U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- *Piyush Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- * * *Kalyanasundaram N* *BE 2nd year, CSE* *College of Engineering Guindy,* *Chennai-600025* * * -- 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/-/i-WLn7rdzDYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
[algogeeks] Re: Microsoft interview question
^not an O(n) On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote: Dave, Cant we have a hash table with the item as key and its count as value (walk over array A and build HT). For permutation check, walk over second array and start reducing the count and remove when count becomes zero for that particular key. If some char not there in HT, return false, else return true. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote: @Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations of each other. Space = O(1) Time=O(n) I think this should work. Please correct me if you find mistakes. On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote: U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- *Piyush Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- * * *Kalyanasundaram N* *BE 2nd year, CSE* *College of Engineering Guindy,* *Chennai-600025* * * -- 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/-/i-WLn7rdzDYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
[algogeeks] Re: Microsoft interview question
in space On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote: Dave, Cant we have a hash table with the item as key and its count as value (walk over array A and build HT). For permutation check, walk over second array and start reducing the count and remove when count becomes zero for that particular key. If some char not there in HT, return false, else return true. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote: @Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations of each other. Space = O(1) Time=O(n) I think this should work. Please correct me if you find mistakes. On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote: U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- *Piyush Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- * * *Kalyanasundaram N* *BE 2nd year, CSE* *College of Engineering Guindy,* *Chennai-600025* * * -- 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/-/i-WLn7rdzDYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Re: [algogeeks] Re: Microsoft interview question
@Ashish: Using a hash table violates the O(1) space requirement given in the original problem. Dave On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote: Dave, Cant we have a hash table with the item as key and its count as value (walk over array A and build HT). For permutation check, walk over second array and start reducing the count and remove when count becomes zero for that particular key. If some char not there in HT, return false, else return true. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote: @Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations of each other. Space = O(1) Time=O(n) I think this should work. Please correct me if you find mistakes. On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote: U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- *Piyush Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- * * *Kalyanasundaram N* *BE 2nd year, CSE* *College of Engineering Guindy,* *Chennai-600025* * * -- 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/-/i-WLn7rdzDYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to
Re: [algogeeks] Re: Microsoft interview question
constant space vs no additional space and then O(n) time complexity not possible.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 8:01 PM, Dave dave_and_da...@juno.com wrote: @Ashish: Using a hash table violates the O(1) space requirement given in the original problem. Dave On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote: Dave, Cant we have a hash table with the item as key and its count as value (walk over array A and build HT). For permutation check, walk over second array and start reducing the count and remove when count becomes zero for that particular key. If some char not there in HT, return false, else return true. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote: @Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations of each other. Space = O(1) Time=O(n) I think this should work. Please correct me if you find mistakes. On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote: U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/**ms**g/algogeeks/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegr**oups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- *Piyush Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegr**oups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group**/algogeeks?hl=enhttp://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+unsubscribe@**googlegr**oups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- * * *Kalyanasundaram N* *BE 2nd year, CSE* *College of Engineering Guindy,* *Chennai-600025* * * -- 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/**
[algogeeks] amazon qn
* given a number and its permutation, how can we find out the number of transformations by which the number could be transformed into its permutation ?* * * *eg: 2315 and 5213 are given. 2315 can be transformed into 5213 in a series of 2 transformations. first swap 2 and 3. then swap 3 and 5.* * * *suggestions will be welcome .* * * *with regards,* *rahul* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] amazon
Given a string. Tell its rank among all its permutations sorted lexicographically. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 qn
levenshtein distance --- Seshu Madhav Chaturvedula తమసోమా జ్యోతిర్గమయా... On Mon, May 21, 2012 at 10:53 PM, rahul venkat rahul911...@gmail.comwrote: * given a number and its permutation, how can we find out the number of transformations by which the number could be transformed into its permutation ?* * * *eg: 2315 and 5213 are given. 2315 can be transformed into 5213 in a series of 2 transformations. first swap 2 and 3. then swap 3 and 5.* * * *suggestions will be welcome .* * * *with regards,* *rahul* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 qn
basically question is asking for edit distance with transposition implementation only. no need of adding delete,replace condition On Mon, May 21, 2012 at 10:53 PM, rahul venkat rahul911...@gmail.comwrote: * given a number and its permutation, how can we find out the number of transformations by which the number could be transformed into its permutation ?* * * *eg: 2315 and 5213 are given. 2315 can be transformed into 5213 in a series of 2 transformations. first swap 2 and 3. then swap 3 and 5.* * * *suggestions will be welcome .* * * *with regards,* *rahul* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
consider string input = cabd now sort this string = abcd now search 1st character from original string(cabd) in sorted string abcd... index found = 3 (index starting from 1 ) now you can arrange left elements from found index i.e index-1 elements in (index-1) ! and right elements from found index in (lastIndex - index)! before character 'c' occurs at index 0. similarly find for other characters and at the end subtract it from n! (n = length of the string ) to find rank On Mon, May 21, 2012 at 11:02 PM, rahul venkat rahul911...@gmail.comwrote: Given a string. Tell its rank among all its permutations sorted lexicographically. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: Amazon Interview Question
I think adjacency list can be implemented by vector of vector. vector vectorint Nodes; The size of vector Nodes is total no of nodes. Every element of the vector will store all its adjacent edges. Nodes[i] is a vector containing all the edges adjacent to node i. So, we can copy the graph easily. On Wednesday, 25 April 2012 17:40:16 UTC+5:30, Radhakrishnan IT wrote: How will you implement a graph data structure ? Give an linked implementation as we do not know how many nodes will be there and how many edges will be there. Make a copy of this graph.. -- 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/-/w49HbR_IySIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Print longest string duplicated M times
I think a better approach can be :- using suffix array. Suffix array is an array data structure which stores all suffixes of the input string, sorted in lexicographical order. Now we need to consider that substring which is repeated m times. Now since all the suffixes starting with same character are contiguous, we can use the following logic :- 1:- iterate from left of suffix array till we get m suffixes having same prefix 2:- update the longest prefix P found so far 3:- if at any time we get a new prefix , start from that current suffix After we reach end , P contains the result if any string is repeated M times otherwise NULL Space Complexity :- O(N) , N is length of input string Time Complexity :- Building the suffix array is N^2 LogN (Worst Case ) + Finding_Substring - O(N) On Tuesday, 15 May 2012 12:22:25 UTC+5:30, ashgoel wrote: I am unclear about the answer provided by Programming Pearls on the question. What this does is to find longest string whose beginning is separated by exactly M chars. The original question is to find the longest string duplicated M times. Any ideas on the approach for this? I could think of having a suffix tree with each node keeping a count to keep track of while insertion how many times this node was passed while going down #include stdlib.h #include string.h #include stdio.h int pstrcmp(char **p, char **q) { return strcmp(*p, *q); } int comlen(char *p, char *q) { int i = 0; while (*p (*p++ == *q++)) i++; return i; } #define M 1 #define MAXN 500 char c[MAXN], *a[MAXN]; int main() { int i, ch, n = 0, maxi, maxlen = -1; while ((ch = getchar()) != EOF) { a[n] = c[n]; c[n++] = ch; } c[n] = 0; qsort(a, n, sizeof(char *), pstrcmp); for (i = 0; i n-M; i++) if (comlen(a[i], a[i+M]) maxlen) { maxlen = comlen(a[i], a[i+M]); maxi = i; } printf(%.*s\n, maxlen, a[maxi]); return 0; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/569uLe79pdcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Print longest string duplicated M times
You can use Suffix Arrays or Suffix Trees. On Mon, May 21, 2012 at 8:17 AM, Ashish Goel ashg...@gmail.com wrote: soln pls Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, May 20, 2012 at 5:49 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: I can give you a dynamic programming approach in O(n^2) and O(n) space . On Tue, May 15, 2012 at 12:22 PM, Ashish Goel ashg...@gmail.com wrote: I am unclear about the answer provided by Programming Pearls on the question. What this does is to find longest string whose beginning is separated by exactly M chars. The original question is to find the longest string duplicated M times. Any ideas on the approach for this? I could think of having a suffix tree with each node keeping a count to keep track of while insertion how many times this node was passed while going down #include stdlib.h #include string.h #include stdio.h int pstrcmp(char **p, char **q) { return strcmp(*p, *q); } int comlen(char *p, char *q) { int i = 0; while (*p (*p++ == *q++)) i++; return i; } #define M 1 #define MAXN 500 char c[MAXN], *a[MAXN]; int main() { int i, ch, n = 0, maxi, maxlen = -1; while ((ch = getchar()) != EOF) { a[n] = c[n]; c[n++] = ch; } c[n] = 0; qsort(a, n, sizeof(char *), pstrcmp); for (i = 0; i n-M; i++) if (comlen(a[i], a[i+M]) maxlen) { maxlen = comlen(a[i], a[i+M]); maxi = i; } printf(%.*s\n, maxlen, a[maxi]); return 0; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Jalaj Jaiswal Software Developer, Adobe Systems +91-9019947895 * * FACEBOOK http://www.facebook.com/jalaj.jaiswal89 LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Thanks, Jeevitesh Shekhar 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.
[algogeeks] Re: Algo for Search in a 2D Matrix
We can consider the 2-d matrix as a heap(also called Young Tableau). We just need to heapify(Youngify) it k-1times,then the element at 0,0 will be kth smallest element. This means we need to remove the k-1 smallest elements from matrix and still maintaining its Row-Col sorted property. Youngify algo:- 1:- put a sentinel value (i,e, INF) 0,0 2:- Now push it leftwards/downwards to maintain the initial property of matrix 3:- If at any point the current element is smaller than both its left and down element, then STOP. This is an in-place operation. We need to consider the sentinel value as highest value,not present in the matrix. It works.Although the matrix is being modified. On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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/-/GtGv_vms-WQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Shouldn't having 2 queues one storing the node and other corresponding level should be sufficient and do level order traversal? -mithun On Mon, May 21, 2012 at 5:54 PM, Ashish Goel ashg...@gmail.com wrote: bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[] path, int pos, vectorint firstCousins) { if ((!pThis) || (!pRoot)) return false; if (pRoot-data!=pThis-data) { path[pos] = pRoot; if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins)) return findCousins(pRoot-left, pThis, path, pos+1, firstCousins); } if (pos2) return false; //this node is at level 0 or level 1 struct node* pGP = path[pos-2]; struct node *pParent = path[pos-1]; struct node *pUncle = NULL; if (pParent == pGP-left) { pUncle = pGP-right; }else pUncle = pGP-left; if (pUncle-left) firstCousins.add(pUncle-left-data); if (pUncle-right) firstCousins.add(pUncle-right-data); return true; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 5:41 PM, Ashish Goel ashg...@gmail.com wrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! the first cousins are 9,8 not 12,13...otherwise the question becomes really simple :) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sorting in O(n)
using bit array we can sort elements in O(1) -mithun On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.comwrote: How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- 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/-/PGgMdaIbGIsJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 interview question
By doing Ex-OR we can find if b is permutation of A suppose a -- 3 5 4 b -- 4 3 5 if A ^ B = 0 then both are permutation or else not shout loud if this has flaws :P -mithun On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 question
@ashish.. it wont be constant space then.. surely it will be o(n) though On Mon, May 21, 2012 at 7:23 PM, Ashish Goel ashg...@gmail.com wrote: Dave, Cant we have a hash table with the item as key and its count as value (walk over array A and build HT). For permutation check, walk over second array and start reducing the count and remove when count becomes zero for that particular key. If some char not there in HT, return false, else return true. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote: @Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations of each other. Space = O(1) Time=O(n) I think this should work. Please correct me if you find mistakes. On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote: U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal piyushkhandelwal...@gmail.com wrote: Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; in;i++) { diff= diff+a[i]-b[i]; } if diff == 0 print: permutation else print: not permutation On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote: @Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- *Piyush Khandelwal*** Mobile No: 91-8447229204 91-9808479765 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- * * *Kalyanasundaram N* *BE 2nd year, CSE* *College of Engineering Guindy,* *Chennai-600025* * * -- 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/-/i-WLn7rdzDYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Re: [algogeeks] Re: Microsoft interview question
a[] = [-1,-3,4,0,7,0,36,2,-3] b[] = [0,0,6,2,-1,9,28,1,6] b1[] = [0,7,0,36,4,-6,3,0,0] b2[] =[-1,-3,11,0,0,0,35,0,0] suma = 42 proda = -84*72*3 sumb = 51 prodb = -84*72*3 sumb1 = 44 prodb1 = -84*72*3 sumb2 = 42 prodb2 = 33*35 do the sum and prod operation w/o 0s and compare the values.. if both are equal they are pormutations if i am missing any corner cases related to 0 or -e numbers u can keep a track of them while traversalO(N) and constant space On Mon, May 21, 2012 at 6:40 PM, karthikeya s karthikeya.a...@gmail.comwrote: No way u can do it in O(1) space and O(n) time.sols above are not gonna work..yeah, it is possible in O(n) space and O(n) time. On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
//considering node who's cousins need to be find as start.. node * a[10]; while(root!=start) { a[i]=root; i++; if(root-data start-data) root=root-left; else root=root-right; }//we can do this using recursion node *grand=a[i-2]; if(start-data grand-data) print(grand-left-left-data,gramd-left-right-data) else print... I may be wrong I am new to coding.. On Monday, 21 May 2012 21:44:56 UTC+5:30, mithun wrote: Shouldn't having 2 queues one storing the node and other corresponding level should be sufficient and do level order traversal? -mithun On Mon, May 21, 2012 at 5:54 PM, Ashish Goel ashg...@gmail.com wrote: bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[] path, int pos, vectorint firstCousins) { if ((!pThis) || (!pRoot)) return false; if (pRoot-data!=pThis-data) { path[pos] = pRoot; if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins)) return findCousins(pRoot-left, pThis, path, pos+1, firstCousins); } if (pos2) return false; //this node is at level 0 or level 1 struct node* pGP = path[pos-2]; struct node *pParent = path[pos-1]; struct node *pUncle = NULL; if (pParent == pGP-left) { pUncle = pGP-right; }else pUncle = pGP-left; if (pUncle-left) firstCousins.add(pUncle-left-data); if (pUncle-right) firstCousins.add(pUncle-right-data); return true; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 5:41 PM, Ashish Goel ashg...@gmail.com wrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! the first cousins are 9,8 not 12,13...otherwise the question becomes really simple :) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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/-/qqG_yzwRUhgJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 question
@Partha try with: A = {2, 2, 9} B= {1, 6, 6} On Mon, May 21, 2012 at 7:08 PM, partha sarathi Mohanty partha.mohanty2...@gmail.com wrote: a[] = [-1,-3,4,0,7,0,36,2,-3] b[] = [0,0,6,2,-1,9,28,1,6] b1[] = [0,7,0,36,4,-6,3,0,0] b2[] =[-1,-3,11,0,0,0,35,0,0] suma = 42 proda = -84*72*3 sumb = 51 prodb = -84*72*3 sumb1 = 44 prodb1 = -84*72*3 sumb2 = 42 prodb2 = 33*35 do the sum and prod operation w/o 0s and compare the values.. if both are equal they are pormutations if i am missing any corner cases related to 0 or -e numbers u can keep a track of them while traversalO(N) and constant space On Mon, May 21, 2012 at 6:40 PM, karthikeya s karthikeya.a...@gmail.comwrote: No way u can do it in O(1) space and O(n) time.sols above are not gonna work..yeah, it is possible in O(n) space and O(n) time. On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 qn
then waht will be it's recurrence relation On Mon, May 21, 2012 at 10:44 AM, atul anand atul.87fri...@gmail.comwrote: basically question is asking for edit distance with transposition implementation only. no need of adding delete,replace condition On Mon, May 21, 2012 at 10:53 PM, rahul venkat rahul911...@gmail.comwrote: * given a number and its permutation, how can we find out the number of transformations by which the number could be transformed into its permutation ?* * * *eg: 2315 and 5213 are given. 2315 can be transformed into 5213 in a series of 2 transformations. first swap 2 and 3. then swap 3 and 5.* * * *suggestions will be welcome .* * * *with regards,* *rahul* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *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.
Re: [algogeeks] amazon
actually we can think of above approach as follows :- input : cabd sort(input) = abcd find first element of the input i.e 'c' in the sorted form i.e abcd 'c' is at found_index=3 ( index starting from 1 ) so permutaion stating from 'c' will come after temp_rank=(found_index - start_index) * (total_lentgh - 1) ! now after temp_rank we know that permutation starting with 'c' will come. so to find out the exact index sort(input-1) i.e removing 1st character ('c') from the input(cadb) we will get abd now permute string abd and compare with input - 1 character i.e (abd). and keep inc the counter , if match is found then you have to add this counter to temp_rank. so for the input = cabd temp_rank = (3 - 1) * (4-1) ! = 2 * 3! = 12 counter found c = 1; rank = 12 + c = 13 but i dont think this would be good solution as be have to permute string and then compare at last...yes we did some optimization. i was wondering if instead of permuting at the end , we can calculate minimum number of swaps required to convert input - 1 to sorted input -1 (removing 1st character )using edit distance ...will this work?? . On Mon, May 21, 2012 at 11:33 PM, atul anand atul.87fri...@gmail.comwrote: consider string input = cabd now sort this string = abcd now search 1st character from original string(cabd) in sorted string abcd... index found = 3 (index starting from 1 ) now you can arrange left elements from found index i.e index-1 elements in (index-1) ! and right elements from found index in (lastIndex - index)! before character 'c' occurs at index 0. similarly find for other characters and at the end subtract it from n! (n = length of the string ) to find rank On Mon, May 21, 2012 at 11:02 PM, rahul venkat rahul911...@gmail.comwrote: Given a string. Tell its rank among all its permutations sorted lexicographically. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 interview question
@mithun: Try A = 1, 6 B = 4, 3 A ^ B = 0. Alone Ex-OR cant solve this in O(n) time. On Monday, 21 May 2012 21:48:30 UTC+5:30, mithun wrote: By doing Ex-OR we can find if b is permutation of A suppose a -- 3 5 4 b -- 4 3 5 if A ^ B = 0 then both are permutation or else not shout loud if this has flaws :P -mithun On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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/-/M16KXaNqGnEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] symmetric binary tree
How to check if a given binary tree is structurally symmetric ie. the left sub tree should be mirror image of right sub tree and vice-versa. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.