Re: [algogeeks] Determine if BST has single child for every node given pre order
Hey Below is a solution. Hope it works. Let 'n' be the size of the array we have. max = min = array(n-1) flag=1; for(i=(n-2) to 0) { if(array(i)array(i+1)) { if(min array(i)) { flag = 0; break; } else { min = array(i); } } else { if(min array(i)) { flag = 0; break; } else { max = array(i); } } } flag?printf(yes):printf(no); On Fri, Dec 30, 2011 at 1:21 PM, top coder topcode...@gmail.com wrote: Input : You have been given a sequence of integers. Now without actually constructing BST from the given sequence of integers (assuming the sequence is pre-order) determine if each node of BST has single child (either left or right but not both). Output : YES if given integer sequence corresponds to such a BST. otherwise say NO. Ex. Say NO for 16,10,8,9,29,27,22. Say YES for 10,19,17,14,15,16 I know the algo O(N^2) as follows: For every node in array(traverse from left to right), all the other nodes must be less or all the nodes must be greater than it. But interviewer is expecting O(N). Any ideas? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Determine if BST has single child for every node given pre order
Hey It was a typo error. here it goes.. max = min = array(n-1) flag=1; for(i=(n-2) to 0) { if(array(i)array(i+1)) { if(min array(i)) { flag = 0; break; } else { min = array(i); } } else { if(max array(i)) { flag = 0; break; } else { max = array(i); } } } flag?printf(yes):printf(no ); On Sat, Dec 31, 2011 at 9:20 PM, Lucifer sourabhd2...@gmail.com wrote: @apoorve say the input is 9 8.. I think it will fail... Secondly, i see that max is not being used On Dec 31, 8:19 pm, Apoorve Mohan apoorvemo...@gmail.com wrote: Hey Below is a solution. Hope it works. Let 'n' be the size of the array we have. max = min = array(n-1) flag=1; for(i=(n-2) to 0) { if(array(i)array(i+1)) { if(min array(i)) { flag = 0; break; } else { min = array(i); } } else { if(min array(i)) { flag = 0; break; } else { max = array(i); } } } flag?printf(yes):printf(no); On Fri, Dec 30, 2011 at 1:21 PM, top coder topcode...@gmail.com wrote: Input : You have been given a sequence of integers. Now without actually constructing BST from the given sequence of integers (assuming the sequence is pre-order) determine if each node of BST has single child (either left or right but not both). Output : YES if given integer sequence corresponds to such a BST. otherwise say NO. Ex. Say NO for 16,10,8,9,29,27,22. Say YES for 10,19,17,14,15,16 I know the algo O(N^2) as follows: For every node in array(traverse from left to right), all the other nodes must be less or all the nodes must be greater than it. But interviewer is expecting O(N). Any ideas? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- 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.
Re: [algogeeks] C doubt
@rohit: why do you think this should give error??? On Sun, Aug 28, 2011 at 5:17 PM, rohit raman.u...@gmail.com wrote: Thanks for your reply himanshu, ...I am aware of the above stated fact but my doubt is that when i pass this char array to a function and accept it as a char pointer (char *a), and then when write a[0] = 'a', why don't i get an error? -- 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/-/uoEq0N1M1t0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Urgent...plz help
Create a B+ tree and extract the first 100 leaf nodes On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg ankurga...@gmail.com wrote: U can use selection Algorithm to achieve the same ...it has got expected running time complexity as O(n) ...Read Wikipedia to see the proper implementation.. Just some tweak with Quick Sort ..Also there is one method median of medians one which has worst case complexity as O(n) Regards Ankur On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma amolsharm...@gmail.comwrote: it will be max heap only.in which root denotes the largest number in your set of 100 smallest -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Thu, Aug 18, 2011 at 9:14 AM, aditi garg aditi.garg.6...@gmail.comwrote: @ dave : i hv one doubt,we wud be maintaining a max or a min heap?? On Thu, Aug 18, 2011 at 9:11 AM, aditi garg aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com wrote: @Aditi: Form a max-heap of the first 100 numbers. Then as you read the remaining numbers, if a number is less than the root of the max-heap, replace the root with it and restore the heap condition. When you reach the end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Urgent...plz help
or rather u can just have 100 iterations of selection sort...u'll get the min 100 iterations...and this is inplace as well... On Thu, Aug 18, 2011 at 1:18 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: Create a B+ tree and extract the first 100 leaf nodes On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg ankurga...@gmail.com wrote: U can use selection Algorithm to achieve the same ...it has got expected running time complexity as O(n) ...Read Wikipedia to see the proper implementation.. Just some tweak with Quick Sort ..Also there is one method median of medians one which has worst case complexity as O(n) Regards Ankur On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma amolsharm...@gmail.comwrote: it will be max heap only.in which root denotes the largest number in your set of 100 smallest -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Thu, Aug 18, 2011 at 9:14 AM, aditi garg aditi.garg.6...@gmail.comwrote: @ dave : i hv one doubt,we wud be maintaining a max or a min heap?? On Thu, Aug 18, 2011 at 9:11 AM, aditi garg aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com wrote: @Aditi: Form a max-heap of the first 100 numbers. Then as you read the remaining numbers, if a number is less than the root of the max-heap, replace the root with it and restore the heap condition. When you reach the end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Merging Sorted Arrays
@aman: Let size of *first array be m* and that of the *second array be* *n*. For m elements in first array you perform binary search therefore time O(mlogn) And for those some elements of the first array you perform shifting in array two...in the worst case for all the elements of first array you might have to perform shifting in second array and also you might just have to shift all the present (n-1) elements each time...so again in worst case this whole procedure will take O(mn) time so total coplexity of your idea is: O(mlogn) + O(mn) And if m is of the O(n) then this will take O(n^2) time in worst case. On Fri, Jul 8, 2011 at 2:40 PM, Aman Goyal aman.goya...@gmail.com wrote: Algo: 1 3 77 78 90 2 5 79 81 compare 1 2 =1 compare 3 2 =2 and call binary search on 2nd array widot 2 to identify a proper position for 3 and place it there. now arrays 1 2 77 78 90 3 5 79 81 3 and 77= swap + binary compare 3 and 77, swap them find position of 77 in second array and place there. using binary search 1 2 3 78 90 5 77 79 81 78 and 5 = swap + binary search 1 2 3 5 90 77 78 79 81 90 and 77= swap+ binary 1 2 3 5 77 78 79 81 90 ans found O(nlogn) binary search is O(logn) . On Fri, Jul 8, 2011 at 8:29 AM, durgesh kumar durgesh1...@gmail.comwrote: @dumanshu ok ! i got a O(n lgn) finally i don know exact complexity Let N = size of first array Find the first N smallest elements using one pointer in each array now swap the list of elements from index 0 to second-pointer in second array to first array with first_poiner+1 to N in first Array now,after swapnig we need to sort both array so complexity= n + n log n+ m log m (n is the size of of first array and m is the size of second array) . . . O(n) = (n log n ) or (m log m) thanks Durgesh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Merging Sorted Arrays
@aman: wat u dint get??? On Fri, Jul 8, 2011 at 6:34 PM, Aman Goyal aman.goya...@gmail.com wrote: i dint get you.. one loop to access the first array elements and compare with second array, and one logn (for) loop to binary search the second array , thts it.. O(mlogn) is what i am able to understand. On Fri, Jul 8, 2011 at 5:52 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: @aman: Let size of *first array be m* and that of the *second array be* *n*. For m elements in first array you perform binary search therefore time O(mlogn) And for those some elements of the first array you perform shifting in array two...in the worst case for all the elements of first array you might have to perform shifting in second array and also you might just have to shift all the present (n-1) elements each time...so again in worst case this whole procedure will take O(mn) time so total coplexity of your idea is: O(mlogn) + O(mn) And if m is of the O(n) then this will take O(n^2) time in worst case. On Fri, Jul 8, 2011 at 2:40 PM, Aman Goyal aman.goya...@gmail.comwrote: Algo: 1 3 77 78 90 2 5 79 81 compare 1 2 =1 compare 3 2 =2 and call binary search on 2nd array widot 2 to identify a proper position for 3 and place it there. now arrays 1 2 77 78 90 3 5 79 81 3 and 77= swap + binary compare 3 and 77, swap them find position of 77 in second array and place there. using binary search 1 2 3 78 90 5 77 79 81 78 and 5 = swap + binary search 1 2 3 5 90 77 78 79 81 90 and 77= swap+ binary 1 2 3 5 77 78 79 81 90 ans found O(nlogn) binary search is O(logn) . On Fri, Jul 8, 2011 at 8:29 AM, durgesh kumar durgesh1...@gmail.comwrote: @dumanshu ok ! i got a O(n lgn) finally i don know exact complexity Let N = size of first array Find the first N smallest elements using one pointer in each array now swap the list of elements from index 0 to second-pointer in second array to first array with first_poiner+1 to N in first Array now,after swapnig we need to sort both array so complexity= n + n log n+ m log m (n is the size of of first array and m is the size of second array) . . . O(n) = (n log n ) or (m log m) thanks Durgesh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: array or matrix problems...anyone?
try rotaion of matrix by 90, 180, 270 and 360 degree in both clockwise and anti clockwise directand try printing matirx in spiral order... On Sat, Jul 9, 2011 at 12:08 AM, Nitish Garg nitishgarg1...@gmail.comwrote: Try the Array Section on geeksforgeeks.org obviously without looking at the solutions. -- 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/-/XsqWbXVJ8CkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Amazon Telephonic Interview Questions
@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.com wrote: 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.
Re: [algogeeks] Re: Amazon Telephonic Interview Questions
@surender: ok man...got it...thanks :) On Mon, Jul 4, 2011 at 3:28 PM, surender sanke surend...@gmail.com wrote: 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.
Re: [algogeeks] find output
5 On Mon, Jul 4, 2011 at 1:01 AM, amit the cool amitthecoo...@gmail.comwrote: int main() { int a[]={5,10,15,8}; int *x=a; int y; y=*x++; printf(%d,y); } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Amazon Telephonic Interview Questions
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.
[algogeeks] 2 D array(dynamic allocation)
Is there any way to dynamically allocate a 2-D array using *using single call to malloc* in C ? -- 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.
Re: [algogeeks] 2 D array(dynamic allocation)
though thankx :) On Thu, Jun 30, 2011 at 12:44 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: @above: man i need a 2d array not a 1d array... On Thu, Jun 30, 2011 at 12:38 AM, hary rathor harry.rat...@gmail.comwrote: #includestdlib.h int main () { int *mat; int i,j; int ROW=4; int COL=3; int k=0; mat=(int *)malloc(ROW*COL*sizeof(int)); for(i=0;iROW;i++) for(j=0;jCOL;j++) mat[i*COL+j]=++k; for(i=0;iROW;i++) for(j=0;jCOL;j++) printf(%d,,mat[i*COL+j]); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 2 D array(dynamic allocation)
@piyush: only one call to malloc...ur sol has 2 On Thu, Jun 30, 2011 at 12:58 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: int **p; p = (int **)malloc(sizeof(int *)*row); for(i = 0;irow;i++) p[i] = (int *)malloc(sizeof(int)*column); On 6/30/11, Apoorve Mohan apoorvemo...@gmail.com wrote: though thankx :) On Thu, Jun 30, 2011 at 12:44 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: @above: man i need a 2d array not a 1d array... On Thu, Jun 30, 2011 at 12:38 AM, hary rathor harry.rat...@gmail.comwrote: #includestdlib.h int main () { int *mat; int i,j; int ROW=4; int COL=3; int k=0; mat=(int *)malloc(ROW*COL*sizeof(int)); for(i=0;iROW;i++) for(j=0;jCOL;j++) mat[i*COL+j]=++k; for(i=0;iROW;i++) for(j=0;jCOL;j++) printf(%d,,mat[i*COL+j]); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Sorting Array
u can use radix sort On Sun, Jun 26, 2011 at 9:44 PM, ross jagadish1...@gmail.com wrote: @Divye: Good theoretical proof and analysis as well.. As you mentioned, this one works like charm for uniformly distributed inputs :) On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote: Use a radix sort. Complexity of the radix sort is O(N k) where k is the number of digits used to represent the number in some base b. If we use the convenient fiction that both N and N^2 fit into the same 32 bit integer then k is a constant and we get an O(N) sort. (It's kindof cheating :) ). Okay, since we don't want to cheat on this one, keep reading below: :) Another method is to divide the Numbers into N bins of size N numbers. Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ... Assuming uniform distribution, the bins will have N/N ~ 1 element each. If the distribution is non-uniform then no bin will have more than N elements. For small bins, apply a variant of insertion sort (which performs faster than O(n log n) sorts for 12 elements) and if N is large, will perform much faster than counting sort. For large bins, apply an O(n log n) sort or radix sort or counting sort. (make a choice depending on number of elements in the bin. eg. Num_elements ~ N then choose counting sort, else choose radix or O(n log n) sorts) Complexity analysis: 1. No bin will have more than N elements. 2. No bin while being sorted will have a range N. If the data distribution is uniform, the solution will be very very quick (order of N) as the sorting time for bins with just 2 to 3 elements is approximately O(num_elements) ~ O(1) and number of such bins is O(N). If the data distribution is non-uniform, then complexity will depend on the number of bad bins and the size of bad bins. Let K bins be bad. Here, K is a value dependent on data distribution of the input. If K is small, number of elements per bin is large - apply counting sort on the bins - complexity O(K N) which is approximately O(N) If K - log N, apply an O(N log N) sort to the bins - complexity O( K * N/K log (N/K)) - O(N log (N/log N)) If K log N but K N, worst case - complexity Sum over K bins{min{O(Ni log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix sort) If K - N - Not possible as you won't have that many bad bins as the number of elements per bin will approach 1. So, in short, you can get a complexity of the kind O(N log (N/log N)) which is slightly better than O(N log N). Hope this helps! -- DK http://twitter.com/divyekapoorhttp://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] c doubt
@anika: the negation operation returns 0 or 1 which is an integerso u get this output On Thu, Jun 23, 2011 at 10:29 PM, piyush kapoor pkjee2...@gmail.com wrote: Thanks a lot :) -- *Regards,* *Piyush Kapoor,* *CSE-IT-BHU* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: sort the array
@ankit: we need an inplace algorithm :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] String Swapping Problem
@sharma: dis has been explained to tiwari...ask him...:) On Fri, Jun 17, 2011 at 3:12 AM, DIPANKAR DUTTA dutta.dipanka...@gmail.comwrote: instead of calling swap(ps[0],ps[1]) can u try with swap(ps[0],ps[1]) or swap(ps[0][0],ps[1][0]) ? On Fri, Jun 17, 2011 at 5:05 AM, udit sharma sharmaudit...@gmail.comwrote: #includestdio.hvoid swap(char *,char *);int main(){char *ps[2]={ Hello, Good Mornning, };swap(ps[0],ps[1]);printf(%s \t %s\n,ps[0],ps[1]);return 0;} void swap(char *p,char *q){char *t;t=p;p=q;q=t;} why the output is: Hello Good Mornning -- Regards UDIT DU- MCA -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, -- *DIPANKAR DUTTA* Visiting Research Scholar Dept of Computing, Macquarie University, Sydney, Australia ph.no-+61 2 98509079 ( Mon-Fri 10:15-7:00) Sydney time email: dipankar.du...@mq.edu.au -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Microsoft ques : reverse of dutch national flag problem
@piyush: at every call to merge u create 3 variables...so u consider this an in-place solution??? On Tue, Jun 7, 2011 at 11:03 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: void merge(int a[], int n, int i) { if(i == 1) { arr[1] = arr[n]; arr[2] = arr[n 1]; return; } int a = arr[i - 1]; int b = arr[n + i - 1]; int c = arr[2*n + i - 1]; merge(arr, n, i - 1); int x = 3 * (i - 1); arr[x] = a; arr[x + 1] = b; arr[x + 2] = c; } Call merge(a, n/3, n/3); I am assuming n is a multiple of 3...I don't know whether the above solution satisfies ur conditions... On 6/6/11, siva viknesh sivavikne...@gmail.com wrote: @piyush...i think u can use anything..but give a optimal solution On Jun 5, 9:22 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: Can we use recursion/internal stack memory??? On 6/5/11, hary rathor harry.rat...@gmail.com wrote: it it is possible in order of O(n ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.
Re: [algogeeks] repeted element
if there is no space complexity constraint then *hashing* can be used i guess On Tue, Jun 7, 2011 at 9:57 PM, Ashish Goel ashg...@gmail.com wrote: abba what will be first repeated element? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 7, 2011 at 12:06 AM, the coder coder.du...@gmail.com wrote: can we find the first repeated element in array in O(N) complexity. Array may contain more than 1 repeated elements. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Odd Even Sort array
int j=1; for(i=2;in;i+=2) swap(a[i],a[j++]); if the input array is like: 2 3 4 5 6 7 8 then after this step u'll get: 2 4 6 8 3 7 5 now u can sort the two halves using any in-place sorting algo and u'll get: 8 6 4 2 3 5 7 i guess dis'll work... On Sat, May 28, 2011 at 12:26 AM, ross jagadish1...@gmail.com wrote: Hi all, Sort all elements in odd indices of an array in ascending order and even indices in descending order. Finally, rearrange so that all even indexed elements come first. eg: input – 7 2 6 4 8 3 1 even indexed : 7 6 8 1 = sort 8 7 6 1 odd indexed: 2 4 3 = sort 2 3 4 output – 8 7 6 1 2 3 4 What could be the best algo to solve it? Is it possible to arrive at the output using only O(1) extra space? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: sum of two
1. use radix sort and sort the array. 2. take two pointers(say i and j). Point the first to head and the second to the tail of the array. then check for a[i] + a[j]. If this sum is greater the decrement the pointer j else if the sum is less than k increment the i pointer. If you get the sum equal to k then stop else move untill j i. I think this solution will have O(n) time complexity and O(n space complexity). On Fri, May 20, 2011 at 7:22 PM, Aakash Johari aakashj@gmail.comwrote: One possible solution is using maps. But i think that won't be in O(n) On Fri, May 20, 2011 at 6:49 AM, Gunjan Sharma gunjan.khan...@gmail.comwrote: First of all there is an infinite loop in this code Secondly it works only for sorted array. On Fri, May 20, 2011 at 7:16 PM, hari rajakin...@gmail.com wrote: In while loop have i,j which points first and last index of array. In while loop, Check the sum of a[i],a[j], If sumk,increment i or else decrement j. Run the while loop till ij.. CODE: int arraysum(int a[], int k, int i, int j) while(ij) { int p=0; int b[10]; //to store index of selected nos sum=a[i]+a[j]; if (sum==k) { b[p++]=i;b[p++]=j; } elseif(sumk) i++; else(sumk) j++; return b; } On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote: given an array of integers, and an integer k, find out two elements from the array whose sum is k in O(n) time. if no such element exists output none. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Gunjan Sharma B.Tech IV year CSE Contact No- +91 9997767077 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT 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 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.
Re: [algogeeks] PUZZLE
@piyush: how??? On Sat, May 21, 2011 at 12:19 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: 500 On 5/20/11, Bhavesh agrawal agr.bhav...@gmail.com wrote: 1 elephant can take 1000 banana at a time and eat 1 banana after each 1km travel. total bananas are 3000 and distance have to travel from A to B is 1000km. So how many max bananas he can take from A to B. (he'll eat in return travel too) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [brain teaser ] FUN MATH PUZZLE 13 may
12111 = 11000+1100+11 On Fri, May 13, 2011 at 10:28 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *FUN MATH PUZZLE * * *** * * ** *If six thousand six hundred and six dollar is written as $6,606, then write eleven thousand eleven hundred and eleven dollars.* * * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/05/fun-math-puzzle-13-may.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe 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. -- 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.
Re: [algogeeks] Re: Extract Top K elements from a List of N elements based on frequency
@Dave: Can there be an in-place O(n) solution to this??? On Mon, May 9, 2011 at 7:01 PM, Dave dave_and_da...@juno.com wrote: @Ashish: By compress, I meant to transfer the active entries in the hash table into contiguous elements of an array. Since the hash table itself is probably stored in an array, it just means to go through the hash table array and move the active entries to the front of the array. Dave On May 9, 1:14 am, Ashish Goel ashg...@gmail.com wrote: Dave, w.r.t statement, After all integers are processed, compress out the unused hash table entries and find the Kth largest element, I could not understand the compress concept...are you saying something on counting sort philosophy? say the list is 5 4 4 3 3 3 2 2 2 2 1 1 1 1 1 so the hash map will have 5,1 5 is 1 time 4,2,4 is two time 3,3,... 2,4,... 1,5... so if the question is to find say 3rd largest element based on frequency, it would be 4 This essentially means that we probably need dynamic order statistics where the node contains the starting rank for a particular entry in the RBTree. Each RBTree node contains the number, its frequency and rank. then this becomes O(n) +O(lgn) i.e. O(n) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, May 7, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Gaurav: As I understand your solution, you are finding the K largest integers based on value, rather than the K with the highest frequency of occurrence. @Amit: Hash the integers into a hash table that includes a field for the frequency count. When a new entry is made, set the frequency count to 1. When an integer already is in the table, increment its count. After all integers are processed, compress out the unused hash table entries and find the Kth largest element. The overall algorithm can be done in O(n). Dave On May 7, 12:06 pm, Gaurav Aggarwal 0007gau...@gmail.com wrote: It can be done without sorting. Take the first element as pivot element. Calculate its position using Partition algorithm. If its new index is K, then on left side are top K integers. If indexK, apply algo on left side Else apply algo on right side. Best Case: O(1) Worst Case: O(n^2) But there are very less chances of worst case. It is when the list is already sorted. On Thu, May 5, 2011 at 1:06 AM, amit amitjaspal...@gmail.com wrote: Hi , We are give a list of integers now our task is to find the top K integers in the list based on frequency. Apart from sorting the data can there be any other algorithm? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Gaurav Aggarwal SCJP- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.
Re: [algogeeks] Puzzle
9 + 1 - ( 1 / 9 ) On Wed, Jan 26, 2011 at 10:29 PM, satish satish@gmail.com wrote: 19-(9/1). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] GENETIC ALGORITHM TOOLBOX IN MATLAB
If anyone has used the *genetic algorithm toolbox of matlab* then please reply as soon as possible as we urgently need help with that. -- regards Apoorve Mohan (apoorvemo...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Adobe Question
what is the data type of 'j' ? On Thu, Sep 23, 2010 at 6:49 PM, Krunal Modi krunalam...@gmail.com wrote: for(k=1 ; kn ; k++){ j=k; while(j0){ j=j/2; } } How many times while loop gets executed (for any n) ? I don't want answer in terms of series (i.e, don't want any sigma, I have that) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Cube root of a number
Depending upon the accuracy you need you can fix the number of iterations On Sun, Aug 22, 2010 at 10:25 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: Using this method u can find any root of any number See this link... http://en.wikipedia.org/wiki/Newton%27s_method On Sun, Aug 22, 2010 at 10:16 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: @apporve ..can u pls elaborate on that ..also on the square root of a number.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Cube root of a number
Using this method u can find any root of any number See this link... http://en.wikipedia.org/wiki/Newton%27s_method On Sun, Aug 22, 2010 at 10:16 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: @apporve ..can u pls elaborate on that ..also on the square root of a number.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Cube root of a number
use newton raphson method On Thu, Aug 19, 2010 at 2:36 AM, asdfghjk georgymk...@gmail.com wrote: Can somebody suggest an efficient algorithm to find the cube root of a number? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
how about using hashing??? at the first collision we will know the repeated element worst case time here will be ( n/2 +1 ) On Fri, Aug 6, 2010 at 12:04 AM, Anand anandut2...@gmail.com wrote: http://codepad.org/8eDVyeBT Using XOR logic we can find Duplicates in O(n) On Thu, Aug 5, 2010 at 11:25 AM, ravindra patel ravindra.it...@gmail.comwrote: Your test case is wrong. With this pattern you can have at max n/3 occurrences of 1. The questions says that repeated element has n/2 occurrences On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: consider the test case of... 1 2 3 1... 1 repeated n/2 times and 2,3 are distinct n/2 elements for this the algo will not work -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorting range of numbers in O(n)
Counting Sort. On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote: There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
is n not the number of nodes? On Fri, Jul 30, 2010 at 11:58 AM, Pramod Negi negi.1...@gmail.com wrote: Follow up on Catalon Nubmer... On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal amitjaspal...@gmail.comwrote: n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to be calculated On Fri, Jul 30, 2010 at 9:08 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: @AMIT: what does n represents? On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar aryansmit3...@gmail.comwrote: @amit is it BST or binary tree??cos BST is unique rite???binary tree meas use catalan numbers 2nCn/(n+1)! On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote: Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: What is the time complexity of multiplying two n-digit numbers base b
If suppose we want to Do N*K then we add N K-times or K N-times. hence the complexity should be O(N*K) On Sat, Jul 31, 2010 at 9:12 PM, Dave dave_and_da...@juno.com wrote: If by repeated addition method, you mean m + m + m + ... + m (where m occurs k times) for forming the product k*m, then the work of forming k*m where k and m are n digit numbers is O((k-1)*n). Using the elementary school algorithm, the work can be reduced to O(n^2). See http://en.wikipedia.org/wiki/Multiplication_algorithm for even faster algorithms. Dave On Jul 31, 7:58 am, sourav souravs...@gmail.com wrote: When you first learned to multiply numbers, you were told that x * y means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is the time complexity of multiplying two n-digit numbers in base b using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes O(1) time. Show how you arrive at your answer. (Hint that was given : how big can y be as a function of n and b?) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ALGORITHM
@above: but this may lead to overflow of the integer as you don't know what is n. if the value of n is large then you can;t do this On Thu, Jul 29, 2010 at 3:26 AM, Minotauraus anike...@gmail.com wrote: If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 - sum of all elements in the array. That'll require one less loop compared to XORing twice. -Minotauraus. On Jul 28, 8:51 am, Apoorve Mohan apoorvemo...@gmail.com wrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.com wrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
@AMIT: what does n represents? On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar aryansmit3...@gmail.comwrote: @amit is it BST or binary tree??cos BST is unique rite???binary tree meas use catalan numbers 2nCn/(n+1)! On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote: Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] pointer and array
@tarak: You can see it like this. When we create an array then 'a' points to the whole array not just the first element so it returns the size of the whole array. when you pass the array though by default in c it is pass by value but as you are passing the address of the array so it acts like pass by reference. So the formal parameter acts as a pointer when you pass the address of the array to it. And you know that the size of a pointer is always equal to the size of int. On Sun, Jul 25, 2010 at 12:31 AM, tarak mehta tarakmeht...@gmail.comwrote: void hell(int arr[]); main() { int arr[]={1,2,3,4,5}; hell(arr); } void hell(int arr[]) { printf(%d,sizeof(arr)/sizeof(*arr)); } even this gives 1 !! @manjunath ur idea seems correct..but could u plz elaborate a bit On Sat, Jul 24, 2010 at 10:51 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: when arrays are passed as arguments to a function,the starting address of the array is passed like a pointer, thus sizeof(arr)=2..thus 2/2=1..this is the precise reason for always specifying the column length in the definition of function when functions have arrays as one of the arguments.. Hope i made any sense.. :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Get the number of pairs of “ones ” in a given integer. Eg: if the integer is 7 (binary: 011 1), then the number of pairs of ones is 2
#includestdio.h main() { unsigned num; int ctr=0; printf(Enter the number: ); scanf(%d,num); while(num) { if( (num 1) ((num 1) 1) ) { ctr++; num=1; } else { num=1; } } printf(number of pair: %d ,ctr); } On Fri, Jul 23, 2010 at 12:39 AM, vijay auvija...@gmail.com wrote: Get the number of pairs of “ones” in a given integer. Eg: if the integer is 7 (binary: 0111), then the number of pairs of ones is 2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return t
Assuming that both the array are sorted. For all elements of array1 Pick up an element from array1. Subtract that element from the number passed. The difference you got search that number in second array using binary search. If elements found come out of the loop and return 1 else return 0. I think this approach will take O(nlogn) time. If the array are not sorted then use linear search. Then this approach will take O(n^2) time. On Fri, Jul 23, 2010 at 12:01 AM, vijay auvija...@gmail.com wrote: You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return true, since 1 (from array 1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each array) is equal to 3). Func(13) should return false -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.