Re: [algogeeks] Efficient Algo for Merging 2 Binary Search Trees
Actually, it doesn't have to be inorder. The naive approach is to traverse through the smaller tree (using any traversal in|pre|post|level order) and insert each node into the bigger tree. The order of this would be n2logn1 A better approach is to try and fit as much of the smaller bst into the larger bst. To explain, imagine the second (and smaller) bst can go and fit snugly as a leaf of the first bst, then you just need to do a logn1 traversal to find this location to insert the smaller bst into the larger bst. However you might not always have a spot in the first bst for the second bst to go as a whole. Here you break up the second tree into three pieces, root node, left subtree and right subtree. You insert the root node into BST1 and recursively call the merge on BST1 LeftSubTreeOfBST2 AND BST1 and RightSubTreeOfBST2. I think the worst case of this is not going to be much better than the naive approach but asymptotically this one should kick ass. ( To ensure that an adversary cannot make it perform badly, we can decide which BST to use as bst1 randomly.) Can anyone try and deduce the actual order of this algorithm (if it works) merge (bst1, bst2): if (bst2 is null) return bst1 if (bst1 is null) return bst2 if (bst2.max_element bst1.val) bst1.left = merge (bst1.left, bst2) else if (bst2.min_element bst1.val) bst1.right = merge (bst1.right, bst2) else // it means bst2 needs to be split up right away insertIntoBst(bst1, bst2.val) bst1 = merge (bst1, bst2.left) bst1 = merge (bst1, bst2.right) On Sun, Oct 9, 2011 at 3:38 AM, Vandana Bachani vandana@gmail.comwrote: Inorder traversal of one tree insert into another? On Sat, Oct 8, 2011 at 4:33 PM, Ankur Garg ankurga...@gmail.com wrote: Hi , Can anyone think of any better for doing this other than converting into List and then converting back again to BST .. Regards -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Urgent...plz help
When the interviewer says there are a million numbers to consider, it might mean that we don't have enough memory to hold all those in a single datastructure. In which case Dave's solution of using a heap of size 100 is the better one I suppose. I am sure a B+ tree takes O(nlogn to the base b) while a heap takes only O(nlogk) and kn 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 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Re: [algogeeks] Re: array question
Step 1: Sort the smaller array mlogm Step 2: For every element in the bigger array, do a binary search on this sorted smaller array. n*logm Total complexity (m+n)logm You could sort the other array and binary search from the smaller array but then it would be (m+n)logn which is bigger than (m+n)logm On Mon, Aug 15, 2011 at 7:18 PM, mohit verma mohit89m...@gmail.com wrote: thanks guys. On Mon, Aug 15, 2011 at 1:12 PM, Nikhil Veliath nve...@gmail.com wrote: Dave tu mahan hai . . . . -- Forwarded message -- From: Dipankar Patro dip10c...@gmail.com Date: 14 Aug 2011 23:27 Subject: Re: [algogeeks] Re: array question To: algogeeks@googlegroups.com @Dave nice algo. Really like it. So the whole complexity depends on the sorting. On 14 August 2011 22:58, Dave dave_and_da...@juno.com wrote: @Dipankar: If extra space is not allowed, I think the optimal solution is to sort the two arrays, which takes O(max(m log m, n log n)). Then the common element can be found in O(m + n) by a simple search that starts at i = j = 0 and increments the index of the lesser of a[i] and b[j]. Overall complexity is O(max(m log m, n log n)). Dave On Aug 14, 8:24 am, Dipankar Patro dip10c...@gmail.com wrote: @ Sagar: What if extra space in not allowed? I think then we have to use the binary search method... On 14 August 2011 18:50, sagar pareek sagarpar...@gmail.com wrote: Hashing O(n+m) On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.com wrote: how about binary search of each element from array 1 on array 2? overall complexity : O(nlogn) On 14 August 2011 18:46, mohit verma mohit89m...@gmail.com wrote: example: array 1 :: 1 2 3 4 5 6 7 8 9 10 15 array 2:: 23 34 56 13 15 57 432 348 On Sun, Aug 14, 2011 at 6:44 PM, shady sinv...@gmail.com wrote: meaning ? what is a common element ? example ??? On Sun, Aug 14, 2011 at 6:37 PM, mohit verma mohit89m...@gmail.comwrote: given two arrays : with all distinct elements but one element in common. Find the common element in optimal time. -- *MOHIT VERMA* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *MOHIT VERMA* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ** Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. --
