[algogeeks] Re: algorithm
Given that the list is in sorted order. Let us assume that the list in the form of an array A[1...n]. Case 1: If n is odd. Then the median is A[(n+1)/2]. Set MEDIAN:=A[(n +1)/2. Case 2: If n is even. Then the median is (A[n/2]+ A[n/2 +1])/2. Set MEDIAN:=(A[n/2]+ A[n/2 +1])/2. Assuming that the array accessing, the addition and division takes O(1) time. The running time of the algorithm is O(1). On Jul 26, 1:15 pm, Manjunath Manohar wrote: > @Anand...for better efficiency..we can find the pivot as a random > integer..for better worst case 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST
I think we can solve this problem by changing the right sub tree of the root
in to linked list in the following way. Here is an example
5
4 7
2 3 89
5
4 9
2 3 8
7
This gives us access to the lowest number and the highest number in the
tree. We can start with the left most child and first right child of the
root.
On 27 July 2010 07:06, Gene wrote:
> Look up threaded tree in wikipedia.
>
> On Jul 26, 9:12 pm, Snoopy Me wrote:
> > Hey could you please give a very brief on what is meant by threads in
> > bst?
> >
> > On Jul 27, 5:17 am, Gene wrote:
> >
> >
> >
> > > You don't thread the tree when you're ready to search it. Rather you
> > > maintain the threads as it's built, which adds nothing to the
> > > asymptotic run time. Parent pointers are a simpler way to get the
> > > same result. However, both solutions require O(n) extra memory for
> > > tag bits or pointers. You're better off just using iterators with
> > > O(log n) stacks. I don't think there's a way to solve this problem
> > > in
> > > O(n) time with less than O(log n) memory.
> >
> > > On Jul 26, 6:18 am, rahul patil wrote:
> >
> > > > @ Gene
> > > > Your solution seems great and most appropriate one.
> > > > Just need to create threads in BST first.What will be time complexity
> > > > for that?
> >
> > > > On Jul 25, 11:08 pm, Gene wrote:
> >
> > > > > You'd know how to do this if you had a sorted array A, right?
> Start a
> > > > > pointer at each end. Call the L and R.
> >
> > > > > L = 0;
> > > > > R = length(A) - 1
> > > > > while (L < R) {
> > > > > while (L < R && A[L] + A[R} > k) --R;
> > > > > if (A[L] + A[R} == k) return ;
> > > > > ++L;}
> >
> > > > > return
> >
> > > > > Since you have a BST, just replace L and R with iterators that scan
> > > > > from left to right and right to left through the tree. The
> ammortized
> > > > > cost of an iterator call is O(1), and there are clearly O(n) calls,
> > > > > where n = lengh(A).
> >
> > > > > The iterators can each contain a O(log n) stack, but you seem
> willing
> > > > > to ignore log n stack space. You could get rid of the stacks by
> > > > > threading the tree.
> >
> > > > > On Jul 24, 12:03 am, Priyanka Chatterjee
> wrote:
> >
> > > > > > Given a binary search tree of n nodes, find two nodes whose sum
> is equal to
> > > > > > a given number k in O(n) time and constant space.
> > > > > > (ignoring recursion stack space)
> >
> > > > > > I have got O(nlogn) time , O(1) space and O(n) time, O(n) space.
> Please
> > > > > > help me out with O(n) time and O(1) space.
> >
> > > > > > --
> > > > > > Thanks & Regards,
> > > > > > Priyanka Chatterjee
> > > > > > Final Year Undergraduate Student,
> > > > > > Computer Science & Engineering,
> > > > > > National Institute Of Technology,Durgapur
> > > > > > Indiahttp://priyanka-nit.blogspot.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.
>
>
--
Thanks and Regards,
N. Ravikanth
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Merging of Binary trees
You actually only need a singly linked list. See and old discussion
about this at
http://groups.google.com/group/comp.programming/msg/41f46b2801c4f84e
This will do the job in O(n).
On Jul 26, 11:00 pm, Ashish Goel wrote:
> Jalaj,
>
> How do you convert a Circular DLL to BST??
> Please refer my solution, and coorect it if needed;)
>
> Regards
> Ashish
>
> On 7/26/10, jalaj jaiswal wrote:
>
>
>
>
>
> > suppose both trees contains n nodes
> > then converting to dll both the trees O(n) + O(n)
> > then merging two dll's O(n)
> > converting back to tree also O(2*n)=O(n)..// not sure about it
>
> > code for converting tree to dll
> > node * bsttolist(node *root){
> > if(root==NULL) return NULL;
> > node *l=bsttolist(root->left);
> > node *r=bsttolist(root->right);
> > root->left=root;
> > root->right=root;
> > append(l,root);
> > append(l,r);
> > return l;
> > }
>
> > here append function merges two circular doubly linked lists , you can make
> > that on your own
>
> > On Mon, Jul 26, 2010 at 5:52 PM, Manjunath Manohar >> wrote:
>
> >> @jalaj: could u pls elaborate on that a bit more..will it have the
> >> complexity of O(n logn logn), and also can u provide the pseudocode pls..
>
> >> --
> >> 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 >> .com>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > With Regards,
> > Jalaj Jaiswal
> > +919026283397
> > B.TECH 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.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
> Ho
--
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: Merging of Binary trees
Jalaj,
How do you convert a Circular DLL to BST??
Please refer my solution, and coorect it if needed;)
Regards
Ashish
On 7/26/10, jalaj jaiswal wrote:
> suppose both trees contains n nodes
> then converting to dll both the trees O(n) + O(n)
> then merging two dll's O(n)
> converting back to tree also O(2*n)=O(n)..// not sure about it
>
> code for converting tree to dll
> node * bsttolist(node *root){
> if(root==NULL) return NULL;
> node *l=bsttolist(root->left);
> node *r=bsttolist(root->right);
> root->left=root;
> root->right=root;
> append(l,root);
> append(l,r);
> return l;
> }
>
>
> here append function merges two circular doubly linked lists , you can make
> that on your own
>
>
>
>
> On Mon, Jul 26, 2010 at 5:52 PM, Manjunath Manohar > wrote:
>
>> @jalaj: could u pls elaborate on that a bit more..will it have the
>> complexity of O(n logn logn), and also can u provide the pseudocode pls..
>>
>> --
>> 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.
>>
>
>
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH 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.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
Ho
--
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: pointer and array
@padnabhan.. u r correct..its clear now..thanks for the idea.
On Tue, Jul 27, 2010 at 4:35 AM, Varma wrote:
>
> 1.Array name is nothing but a const pointer to the first element of an
> array.
> 2.subscripting of an array can be visualized as incrementing a
> pointer . Pointer always increments by the size of the type of data it
> holds.
> 3. so, always sizeof(arr) is the sizeof a pointer , and sizeof(*arr)
> is the sizeof(1) i.e size of the first element. it is an integer
> here.
> 4. Pointers size and integers size are same in most compilers ( dont
> think of far pointers now) . so it resulted in 1 despite of the no.of
> elements in that array.
>
> Hope i made it more clear :)
>
> On Jul 25, 12:01 am, tarak mehta wrote:
> > 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.com
>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST
Look up threaded tree in wikipedia.
On Jul 26, 9:12 pm, Snoopy Me wrote:
> Hey could you please give a very brief on what is meant by threads in
> bst?
>
> On Jul 27, 5:17 am, Gene wrote:
>
>
>
> > You don't thread the tree when you're ready to search it. Rather you
> > maintain the threads as it's built, which adds nothing to the
> > asymptotic run time. Parent pointers are a simpler way to get the
> > same result. However, both solutions require O(n) extra memory for
> > tag bits or pointers. You're better off just using iterators with
> > O(log n) stacks. I don't think there's a way to solve this problem
> > in
> > O(n) time with less than O(log n) memory.
>
> > On Jul 26, 6:18 am, rahul patil wrote:
>
> > > @ Gene
> > > Your solution seems great and most appropriate one.
> > > Just need to create threads in BST first.What will be time complexity
> > > for that?
>
> > > On Jul 25, 11:08 pm, Gene wrote:
>
> > > > You'd know how to do this if you had a sorted array A, right? Start a
> > > > pointer at each end. Call the L and R.
>
> > > > L = 0;
> > > > R = length(A) - 1
> > > > while (L < R) {
> > > > while (L < R && A[L] + A[R} > k) --R;
> > > > if (A[L] + A[R} == k) return ;
> > > > ++L;}
>
> > > > return
>
> > > > Since you have a BST, just replace L and R with iterators that scan
> > > > from left to right and right to left through the tree. The ammortized
> > > > cost of an iterator call is O(1), and there are clearly O(n) calls,
> > > > where n = lengh(A).
>
> > > > The iterators can each contain a O(log n) stack, but you seem willing
> > > > to ignore log n stack space. You could get rid of the stacks by
> > > > threading the tree.
>
> > > > On Jul 24, 12:03 am, Priyanka Chatterjee wrote:
>
> > > > > Given a binary search tree of n nodes, find two nodes whose sum is
> > > > > equal to
> > > > > a given number k in O(n) time and constant space.
> > > > > (ignoring recursion stack space)
>
> > > > > I have got O(nlogn) time , O(1) space and O(n) time, O(n) space.
> > > > > Please
> > > > > help me out with O(n) time and O(1) space.
>
> > > > > --
> > > > > Thanks & Regards,
> > > > > Priyanka Chatterjee
> > > > > Final Year Undergraduate Student,
> > > > > Computer Science & Engineering,
> > > > > National Institute Of Technology,Durgapur
> > > > > Indiahttp://priyanka-nit.blogspot.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.
[algogeeks] Re: BST
Hey could you please give a very brief on what is meant by threads in
bst?
On Jul 27, 5:17 am, Gene wrote:
> You don't thread the tree when you're ready to search it. Rather you
> maintain the threads as it's built, which adds nothing to the
> asymptotic run time. Parent pointers are a simpler way to get the
> same result. However, both solutions require O(n) extra memory for
> tag bits or pointers. You're better off just using iterators with
> O(log n) stacks. I don't think there's a way to solve this problem
> in
> O(n) time with less than O(log n) memory.
>
> On Jul 26, 6:18 am, rahul patil wrote:
>
> > @ Gene
> > Your solution seems great and most appropriate one.
> > Just need to create threads in BST first.What will be time complexity
> > for that?
>
> > On Jul 25, 11:08 pm, Gene wrote:
>
> > > You'd know how to do this if you had a sorted array A, right? Start a
> > > pointer at each end. Call the L and R.
>
> > > L = 0;
> > > R = length(A) - 1
> > > while (L < R) {
> > > while (L < R && A[L] + A[R} > k) --R;
> > > if (A[L] + A[R} == k) return ;
> > > ++L;}
>
> > > return
>
> > > Since you have a BST, just replace L and R with iterators that scan
> > > from left to right and right to left through the tree. The ammortized
> > > cost of an iterator call is O(1), and there are clearly O(n) calls,
> > > where n = lengh(A).
>
> > > The iterators can each contain a O(log n) stack, but you seem willing
> > > to ignore log n stack space. You could get rid of the stacks by
> > > threading the tree.
>
> > > On Jul 24, 12:03 am, Priyanka Chatterjee wrote:
>
> > > > Given a binary search tree of n nodes, find two nodes whose sum is
> > > > equal to
> > > > a given number k in O(n) time and constant space.
> > > > (ignoring recursion stack space)
>
> > > > I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
> > > > help me out with O(n) time and O(1) space.
>
> > > > --
> > > > Thanks & Regards,
> > > > Priyanka Chatterjee
> > > > Final Year Undergraduate Student,
> > > > Computer Science & Engineering,
> > > > National Institute Of Technology,Durgapur
> > > > Indiahttp://priyanka-nit.blogspot.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.
[algogeeks] Re: BST
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem
in
O(n) time with less than O(log n) memory.
On Jul 26, 6:18 am, rahul patil wrote:
> @ Gene
> Your solution seems great and most appropriate one.
> Just need to create threads in BST first.What will be time complexity
> for that?
>
> On Jul 25, 11:08 pm, Gene wrote:
>
>
>
> > You'd know how to do this if you had a sorted array A, right? Start a
> > pointer at each end. Call the L and R.
>
> > L = 0;
> > R = length(A) - 1
> > while (L < R) {
> > while (L < R && A[L] + A[R} > k) --R;
> > if (A[L] + A[R} == k) return ;
> > ++L;}
>
> > return
>
> > Since you have a BST, just replace L and R with iterators that scan
> > from left to right and right to left through the tree. The ammortized
> > cost of an iterator call is O(1), and there are clearly O(n) calls,
> > where n = lengh(A).
>
> > The iterators can each contain a O(log n) stack, but you seem willing
> > to ignore log n stack space. You could get rid of the stacks by
> > threading the tree.
>
> > On Jul 24, 12:03 am, Priyanka Chatterjee wrote:
>
> > > Given a binary search tree of n nodes, find two nodes whose sum is equal
> > > to
> > > a given number k in O(n) time and constant space.
> > > (ignoring recursion stack space)
>
> > > I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
> > > help me out with O(n) time and O(1) space.
>
> > > --
> > > Thanks & Regards,
> > > Priyanka Chatterjee
> > > Final Year Undergraduate Student,
> > > Computer Science & Engineering,
> > > National Institute Of Technology,Durgapur
> > > Indiahttp://priyanka-nit.blogspot.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.
[algogeeks] Re: Merging of Binary trees
If the trees are not ordered or balanced, you can do this in O(n) time. Just walk the nodes of Tree A until you find one with a child missing and attach Tree B at that location. Some people are confused by the fact that each individual step of a tree walk can take up to O(log n) time. But for the whole tree, the costs amortize nicely so that the total cost of the walk is O(n), not O(n log n). If the trees _are_ ordered and/or balanced, then the solution you proposed (deconstructing both trees and building a new one) still takes only O(n log n) time. You don't need the extra log(n) time. Now if you meant n log(log(n)), that's harder. On Jul 26, 7:46 am, Manjunath Manohar wrote: > no just a BT, the tree can be in any form..it need not be balanced also.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem in
O(n) time with less than O(n) memory.
On Jul 26, 6:18 am, rahul patil wrote:
> @ Gene
> Your solution seems great and most appropriate one.
> Just need to create threads in BST first.What will be time complexity
> for that?
>
> On Jul 25, 11:08 pm, Gene wrote:
>
>
>
> > You'd know how to do this if you had a sorted array A, right? Start a
> > pointer at each end. Call the L and R.
>
> > L = 0;
> > R = length(A) - 1
> > while (L < R) {
> > while (L < R && A[L] + A[R} > k) --R;
> > if (A[L] + A[R} == k) return ;
> > ++L;}
>
> > return
>
> > Since you have a BST, just replace L and R with iterators that scan
> > from left to right and right to left through the tree. The ammortized
> > cost of an iterator call is O(1), and there are clearly O(n) calls,
> > where n = lengh(A).
>
> > The iterators can each contain a O(log n) stack, but you seem willing
> > to ignore log n stack space. You could get rid of the stacks by
> > threading the tree.
>
> > On Jul 24, 12:03 am, Priyanka Chatterjee wrote:
>
> > > Given a binary search tree of n nodes, find two nodes whose sum is equal
> > > to
> > > a given number k in O(n) time and constant space.
> > > (ignoring recursion stack space)
>
> > > I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
> > > help me out with O(n) time and O(1) space.
>
> > > --
> > > Thanks & Regards,
> > > Priyanka Chatterjee
> > > Final Year Undergraduate Student,
> > > Computer Science & Engineering,
> > > National Institute Of Technology,Durgapur
> > > Indiahttp://priyanka-nit.blogspot.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.
[algogeeks] Re: pointer and array
1.Array name is nothing but a const pointer to the first element of an
array.
2.subscripting of an array can be visualized as incrementing a
pointer . Pointer always increments by the size of the type of data it
holds.
3. so, always sizeof(arr) is the sizeof a pointer , and sizeof(*arr)
is the sizeof(1) i.e size of the first element. it is an integer
here.
4. Pointers size and integers size are same in most compilers ( dont
think of far pointers now) . so it resulted in 1 despite of the no.of
elements in that array.
Hope i made it more clear :)
On Jul 25, 12:01 am, tarak mehta wrote:
> 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.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] algorithm
@Anand...for better efficiency..we can find the pivot as a random integer..for better worst case 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] algorithm
*
*
*Using partition Logic of Quick Sort:
*
*Algoritm:*
1. pivot = 1st element.
2. Find the position of pivot in the array using partition logic of Quick
sort
3. If Rank lies on the right side of the position then call this function
with the right array
4. If rank lies on the left side of the position, then call this function
with the left array.
5. If rank == position
- return the element at position
On Sun, Jul 25, 2010 at 4:44 AM, Algoose chase wrote:
> Add Each number from the stream to a Doubly linked list in sorted fashion
>
> i = 1;
> j = 1;
> while( stream not empty)
> {
>if( i == 1&& j == 1)
>{
> Median = Cur ; /*Create New list with ist Number*/
>}
>Add_Node_In_Sorted_Order(Cur);
>
>If( If new node is added after median )
>i++; /*if the current median is 3rd node and new
> node is added @ 5th position*/
> bAddedBeforeMedian = False;
>else
>j++;
>bAddedBeforeMedian = true;
>
>if( i %2 == 1 && !bAddedBeforeMedian)
> Median = median ->next;
>else if (j%2==1 && bAddedBeforeMeidan)
> Median = Median->prev
>
> }
> return Median->Data;
>
> At any given point in time Median will point to the median among the
> numbers seen so far
>
> -
>
>
> On Sat, Jul 24, 2010 at 8:02 PM, jalaj jaiswal
> wrote:
>
>> You are given a stream of numbers which can be positive or negative. You
>> are required to provide an operation FIND MEDIAN..which when invoked should
>> be able return the median of the numbers in stream (in sorted order) in O(1)
>> time.
>>
>> Eg: 0 1 2 3 4
>> Right FIND MEDIAN returns 2 as median
>>
>> Now input is -2 -4
>> So Stream = 0 1 2 3 -2 -2 -4
>> Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1
>>
>> --
>> With Regards,
>> Jalaj Jaiswal
>> +919026283397
>> B.TECH 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.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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: Merging of Binary trees
@ashish..nice code..i think the complexity is O(n logn ) right.. am i right?? -- 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: Merging of Binary trees
@jalaj..thanks for ur help..really appreciate it.. :) -- 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: Merging of Binary trees
can proceed like this...writing it quite fast, may have issues...
lets say T2 is being merged into T1
//assumption, trees have different data values
struct node * merge(struct node *pT1, struct node *pT2)
{
if (!pT2) return NULL;
struct node *ptemp=NULL;
if (pT2->data data)
{
ptemp = pT2->right;
pT2->right =NULL;
pT1->left = merge(pT1->left, pT2);
pT1->right = merge(pT1, ptemp);
}
else {
ptemp = pT2->left;
pT2->left = NULL;
pT1->right= merge(pT1->right, pT2);
pT1->left= merge(pT1,ptemp);
}
}
On 7/26/10, Manjunath Manohar wrote:
> @jalaj: could u pls elaborate on that a bit more..will it have the
> complexity of O(n logn logn), and also can u provide the pseudocode pls..
>
> --
> 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.
>
>
--
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 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: Merging of Binary trees
suppose both trees contains n nodes
then converting to dll both the trees O(n) + O(n)
then merging two dll's O(n)
converting back to tree also O(2*n)=O(n)..// not sure about it
code for converting tree to dll
node * bsttolist(node *root){
if(root==NULL) return NULL;
node *l=bsttolist(root->left);
node *r=bsttolist(root->right);
root->left=root;
root->right=root;
append(l,root);
append(l,r);
return l;
}
here append function merges two circular doubly linked lists , you can make
that on your own
On Mon, Jul 26, 2010 at 5:52 PM, Manjunath Manohar wrote:
> @jalaj: could u pls elaborate on that a bit more..will it have the
> complexity of O(n logn logn), and also can u provide the pseudocode pls..
>
> --
> 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.
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Oracle-Java Developer interview question
one another solution using counting array...
void findwidth(BST* bt, int *arr, int count)//initially count is 0 for root
{
if(bt)
return;
arr[count]++;
count++;
if(bt->left)
findwidth(bt->left, arr, count);
if(bt->right)
findwidth(bt->right, arr, count);
return;
}
int maxwidth(BST* bt)
{
int count = 0, temp = 0, i = 0;
int arr = (int*) malloc(sizeof(int)*n); //here n is no of node
findwidth(bt, arr, count);
while(arr[i])
{
if(temp wrote:
> use levelorder traversal and calculate the number of node in same level by
> putting some condition :)
>
> On Mon, Jul 26, 2010 at 1:53 PM, vineel yalamarth <
> vineelyalamar...@gmail.com> wrote:
>
>>
>>
>> No dude, they asked me to find width , in the sense ... find the maximum
>> number of nodes in any level.
>> And if you know how to find the diameter do post it
>>
>>
>> --
>> 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.
>>
>
>
>
> --
> Thanks & Regards
>
> Umesh kewat
>
>
>
--
Thanks & Regards
Umesh kewat
--
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] Oracle-Java Developer interview question
use levelorder traversal and calculate the number of node in same level by putting some condition :) On Mon, Jul 26, 2010 at 1:53 PM, vineel yalamarth < vineelyalamar...@gmail.com> wrote: > > > No dude, they asked me to find width , in the sense ... find the maximum > number of nodes in any level. > And if you know how to find the diameter do post it > > > -- > 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. > -- Thanks & Regards Umesh kewat -- 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: Merging of Binary trees
@jalaj: could u pls elaborate on that a bit more..will it have the complexity of O(n logn logn), and also can u provide the pseudocode pls.. -- 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: Merging of Binary trees
convert both to dll and merge the two dll's and finally create the tree from a dll recursively On Mon, Jul 26, 2010 at 5:16 PM, Manjunath Manohar wrote: > no just a BT, the tree can be in any form..it need not be balanced also.. > > -- > 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. > -- With Regards, Jalaj Jaiswal +919026283397 B.TECH 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Free dell laptops offered by bill gates foundation
what is this? Don't spam this forum with such nonsense. On Jul 26, 9:16 am, thati srinivas wrote: > Free dell laptops offered by bill gates foundation….no need money… > No need registration fee….no need transport charges…..details > available on my blog. if you want to get free laptop, click A DELL > IMAGE at the TOP Side of my BLOG. .then open full detais. Get it free > 100% and enjoy. First 10,000 people only.hurry up. > > my blog is http://freelaptopsandfreewebhosting.blogspot.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] Re: Merging of Binary trees
no just a BT, the tree can be in any form..it need not be balanced also.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene wrote:
> You'd know how to do this if you had a sorted array A, right? Start a
> pointer at each end. Call the L and R.
>
> L = 0;
> R = length(A) - 1
> while (L < R) {
> while (L < R && A[L] + A[R} > k) --R;
> if (A[L] + A[R} == k) return ;
> ++L;}
>
> return
>
> Since you have a BST, just replace L and R with iterators that scan
> from left to right and right to left through the tree. The ammortized
> cost of an iterator call is O(1), and there are clearly O(n) calls,
> where n = lengh(A).
>
> The iterators can each contain a O(log n) stack, but you seem willing
> to ignore log n stack space. You could get rid of the stacks by
> threading the tree.
>
> On Jul 24, 12:03 am, Priyanka Chatterjee wrote:
>
> > Given a binary search tree of n nodes, find two nodes whose sum is equal to
> > a given number k in O(n) time and constant space.
> > (ignoring recursion stack space)
>
> > I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
> > help me out with O(n) time and O(1) space.
>
> > --
> > Thanks & Regards,
> > Priyanka Chatterjee
> > Final Year Undergraduate Student,
> > Computer Science & Engineering,
> > National Institute Of Technology,Durgapur
> > Indiahttp://priyanka-nit.blogspot.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] a google question
any element to the right of X in the same array is less than X. Any element to the top of X in the same column is less than X. so any element to the nrth east of X is less than X. All the elements to the south west, (including X) are not less than X. To the north west is a mix and to the south east there is a mix. So if we take a big north east, which leaves out only 2n-1 elements in the L they ought to be the largest. this is the same argument when u analyze the order statistics worst case O(n) bound. And this is the same argument u give when given 2 arrays of size N ( not sorted) u want to find whether there could be a sum =some constant C in O(NlogN) time becuas esorting takes NLogN. arrange one array as ascending(Y axis) and one descending(X axis). and form the grid. Property being any element X has its north east contaisn all the elements which are strickely less. and its south west, including it contaisn all elements which are greater than or equal to X. So we start from the top left hand corner and making our entire search start such that the N^2 sums form the south east ( where there is a mix) an then we go downwards if we need a bigger sum, and rightwards if we need a smaller sum. Since the north east and south west is clearly partitioned across any sum u r pointing to right now, and u have already ensured through ur operations that ur north west doesnt contain the sum of ur interest, u proceed south east and never travel back, making a total of 2N moves in the worst case. Its a similar argument. On Mon, Jul 26, 2010 at 2:25 PM, manish bhatia wrote: > How are we making sure that top n-elements would lie in this 'L' shaped > array? > > Also, why don't we take an extreme case, such that the origin is > bottom-left element of the grid, then we have only 2n-1 elements to chose n > biggest elements from. > > So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave > n-biggest out? What is the criterion to chose the Ist quardrant? > > manish... > > > -- > *From:* topojoy biswas > *To:* algogeeks@googlegroups.com > *Sent:* Thu, 22 July, 2010 10:10:58 AM > > *Subject:* Re: [algogeeks] a google question > > im sry the L should look like this: > > > >109 8 5 321 > 7 17 16 > 8 18 17 > 9 19 18 > 10 20 19 > 11 21 2019 1614 13 12 > 12 22 2120 1715 14 13 > 13 23 2221 1816 15 14 > > > I missed a row in the last mail. > > On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas > wrote: > >> consider these arrays: >> >> 10 9 8 5 3 2 1 >> >> and >> >> 13 12 11 10 9 8 7 >> >> >> form a grid like this: >> >>109 8 5 321 >> 7 17 1615 1210 98 >> 8 18 1716 1311 10 9 >> 9 19 1817 1412 12 10 >> 10 20 1918 1513 12 11 >> 11 21 2019 1614 13 12 >> 12 22 2120 1715 14 13 >> 13 23 2221 1816 15 14 >> >> basically have an array descending and have one array ascending. >> >> If you add them in a grid, check that for any sum, all sums to its right >> are less than it( in the same row), al sums above it( in the same column) >> are less than it, all sums below it( in the same row) are greater than it. >> >>109 8 5 321 >> 7 17 1615 *1210 98* >> 8 18 1716 *1311 10 9* >> 9 19 1817 *1412 12 10* >> 10 20 1918 *1513 12 11* >> 11 *21 2019* 1614 13 12 >> 12 *22 2120* 1715 14 13 >> 13 *23 2221* 1816 15 14 >> >> So all sums which form the first quadrant origining at 19 are less than >> 19. >> >> And the 3rd quadrant formed by origining 19 including 19 are strickedly >> grater than or equal to 19. >> >> This means in the added array will look like this: >> __ >> ||___|__| >> <---x--><--m---><-y-> >> >> x = no of elements in the underlined first quadrant >> y= no of elements in the 3rd quadrant excluding 19. >> m= the number of elements in the 2nd and the 4th quadrant including 19. >> >> So 19 would lie some whr in the 2n slot of this divided aray picture. >> >> So if we make x big enough so that m+y is small enough=O(n), we will >> reduce our load. >> >> so choose x=(n-2)(n-3) which means something like this: >> <--(n-2)---> >>109 8 5 321 >> 7 17 1615 1210 98 --- >> 8 18 1716 1311 10 9 >> 9 19 1817 1412 12 10 (n-3) >> 10 20 1918 1513 12 11 - >> 11 21 2019 1614 13 12 >> 12 22 2120 1715 14 13 >> 13 23 2221 1816 15 14 >> >> Then w
Re: [algogeeks] a google question
How are we making sure that top n-elements would lie in this 'L' shaped array? Also, why don't we take an extreme case, such that the origin is bottom-left element of the grid, then we have only 2n-1 elements to chose n biggest elements from. So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave n-biggest out? What is the criterion to chose the Ist quardrant? manish... From: topojoy biswas To: algogeeks@googlegroups.com Sent: Thu, 22 July, 2010 10:10:58 AM Subject: Re: [algogeeks] a google question im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas wrote: consider these arrays: > >10 9 8 5 3 2 1 > >and > >13 12 11 10 9 8 7 > > >form a grid like this: > > 109 8 5 321 >7 17 1615 1210 98 >8 18 1716 1311 10 9 >9 19 1817 1412 12 10 >10 20 1918 1513 12 11 >11 21 2019 1614 13 12 >12 22 2120 1715 14 13 >13 23 2221 1816 15 14 > >basically have an array descending and have one array ascending. > >If you add them in a grid, check that for any sum, all sums to its right are >less than it( in the same row), al sums above it( in the same column) are less >than it, all sums below it( in the same row) are greater than it. > > 109 8 5 321 >7 17 1615 1210 98 >8 18 1716 1311 10 9 >9 19 1817 1412 12 10 >10 20 1918 1513 12 11 >11 21 2019 1614 13 12 >12 22 2120 1715 14 13 >13 23 2221 1816 15 14 > >So all sums which form the first quadrant origining at 19 are less than 19. > >And the 3rd quadrant formed by origining 19 including 19 are strickedly grater >than or equal to 19. > > >This means in the added array will look like this: >__ >||___|__| > <---x--><--m---><-y-> > >x = no of elements in the underlined first quadrant >y= no of elements in the 3rd quadrant excluding 19. >m= the number of elements in the 2nd and the 4th quadrant including 19. > >So 19 would lie some whr in the 2n slot of this divided aray picture. > >So if we make x big enough so that m+y is small enough=O(n), we will reduce >our >load. > >so choose x=(n-2)(n-3) which means something like this: > <--(n-2)---> > 109 8 5 321 >7 17 1615 1210 98 --- >8 18 1716 1311 10 9 >9 19 1817 1412 12 10 (n-3) >10 20 1918 1513 12 11 - >11 21 2019 1614 13 12 >12 22 2120 1715 14 13 >13 23 2221 1816 15 14 > >Then we will be left with an array of size m+y=5n-6 which is >n for all n >2 >like this: > > 109 8 5 321 >7 17 16 >8 18 17 >9 19 18 >10 20 19 >11 21 20 >12 22 2120 1715 14 13 >13 23 2221 1816 15 14 > >Till this point it takes constant time. > >Now the first column of the "L" formed is sorted. So is the 2nd column. > >So is the horizonal part of L which is comprized of two sorted arays (20-13) >and >(21-14). > >All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the >biggest n elements. > > > > > > >On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal >wrote: > > >> >> >>this ques was asked by google.. i* could find any gud soln than order n*n >>> >>> >>> >> -- >>You received this message because you are subscribed to the Google Groups >>"Algorithm Geeks" group. >>To post to this group, send email to algoge...@googlegroups.com. >>To unsubscribe from this group, send email to >>algogeeks+unsubscr...@googlegroups.com. >>For more options, visit this group at >>http://groups.google.com/group/algogeeks?hl=en. >> > > >-- >Topo. > >There are days when solitude is a heady wine that intoxicates you with >freedom, >others when it is a bitter tonic, and still others when it is a poison that >makes you beat your head against the wall. ~Colette > -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge..
Re: [algogeeks] Oracle-Java Developer interview question
No dude, they asked me to find width , in the sense ... find the maximum number of nodes in any level. And if you know how to find the diameter do post it -- 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] Oracle-Java Developer interview question
shldnt max width be equal to diameter of the treecorrect me if im wrong On Mon, Jul 26, 2010 at 1:28 PM, vineel yalamarth < vineelyalamar...@gmail.com> wrote: > > > Dear Sharad,Maximum width of the tree you had drawn is 2...(3,8),(1,4) > > > > > -- > 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. > -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Oracle-Java Developer interview question
Dear Sharad,Maximum width of the tree you had drawn is 2...(3,8),(1,4) -- 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] Oracle-Java Developer interview question
5 / \ 3 8 max width is 4 (1-3-5-8) am i riteif so then use the approach as i stated earlier ... / \ 1 4 On Mon, Jul 26, 2010 at 1:03 PM, Sathaiah Dontula wrote: > I mean "maximum number of nodes in a breadth of a BST". > > Thanks, > Sathaiah > > On Mon, Jul 26, 2010 at 1:00 PM, sharad kumar > wrote: > >> the max width of bst is the largets diff betweeen the min node and max >> node rite? >> >> >> On Mon, Jul 26, 2010 at 12:30 PM, Chunyuan Ge wrote: >> >>> breadth-favorite search? >>> >>> >>> On Mon, Jul 26, 2010 at 2:28 PM, Sathaiah Dontula >>> wrote: >>> You mean maximum width of bst ? You can use BST to find the same. Thanks, Sathaiah On Mon, Jul 26, 2010 at 11:47 AM, aparichith < vineelyalamar...@gmail.com> wrote: > Can some one tell me the algorithm to find out the width of a binary > search tree. > > -- > 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. > > -- 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. >>> >>> -- >>> 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. >>> >> >> >> >> -- >> 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.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Oracle-Java Developer interview question
I mean "maximum number of nodes in a breadth of a BST". Thanks, Sathaiah On Mon, Jul 26, 2010 at 1:00 PM, sharad kumar wrote: > the max width of bst is the largets diff betweeen the min node and max node > rite? > > > On Mon, Jul 26, 2010 at 12:30 PM, Chunyuan Ge wrote: > >> breadth-favorite search? >> >> >> On Mon, Jul 26, 2010 at 2:28 PM, Sathaiah Dontula >> wrote: >> >>> You mean maximum width of bst ? >>> >>> You can use BST to find the same. >>> >>> Thanks, >>> Sathaiah >>> >>> >>> On Mon, Jul 26, 2010 at 11:47 AM, aparichith >> > wrote: >>> Can some one tell me the algorithm to find out the width of a binary search tree. -- 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. >>> -- >>> 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. >>> >> >> -- >> 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. >> > > > > -- > 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.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Merging of Binary trees
are you asking for BST or simple BT. what are the conditions you want to follow if simple BT On Jul 26, 12:59 am, AlgoBoy wrote: > Does anyone know how to merge two binary trees in O(n logn logn) > complexity.. > intiutive solution is to flatten both the trees (by inorder > traversal ) and then construct a new one... > but how to do this efficiently in O(n logn logn)..pls help -- 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] Oracle-Java Developer interview question
the max width of bst is the largets diff betweeen the min node and max node rite? On Mon, Jul 26, 2010 at 12:30 PM, Chunyuan Ge wrote: > breadth-favorite search? > > > On Mon, Jul 26, 2010 at 2:28 PM, Sathaiah Dontula wrote: > >> You mean maximum width of bst ? >> >> You can use BST to find the same. >> >> Thanks, >> Sathaiah >> >> >> On Mon, Jul 26, 2010 at 11:47 AM, aparichith >> wrote: >> >>> Can some one tell me the algorithm to find out the width of a binary >>> search tree. >>> >>> -- >>> 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. >>> >>> >> -- >> 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. >> > > -- > 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. > -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Oracle-Java Developer interview question
breadth-favorite search? On Mon, Jul 26, 2010 at 2:28 PM, Sathaiah Dontula wrote: > You mean maximum width of bst ? > > You can use BST to find the same. > > Thanks, > Sathaiah > > > On Mon, Jul 26, 2010 at 11:47 AM, aparichith > wrote: > >> Can some one tell me the algorithm to find out the width of a binary >> search tree. >> >> -- >> 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. >> >> > -- > 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. > -- 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.
