Re: [algogeeks] question
copy the array(A) in a different array(B) to store the index info.(space O(n)) sort(A) take each pair's sum ( complexity O(n^2) ) and with that do a binary search for the 3rd element needed.(O(log(n))). Check for the indices in B. i believe it can be done in better time somehow. On Mon, May 3, 2010 at 6:48 PM, jalaj jaiswal wrote: > > given an array(unsorted) may contain negative numbers too > find the index of three numbers whose sum is closest to zero in O(N2 log > N) time and O(N) space. > > P.S -3 is more close to zero then -6 (number line ...) > -- > 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.
Re: [algogeeks] Re: Finding the mode in a set of integers
@rohit : thats more than 1000 elements in the array On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf wrote: > say u choose the last value as pivot > > 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4 > > 4 is your pivot > try out > > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > On Thu, Apr 15, 2010 at 5:26 PM, vivek bijlwan wrote: > >> @rohit : can you give me any counter examples? >> >> PS: one value is occuring >=501 times. >> >> On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf > > wrote: >> >>> It cannot just be partitioned in such a manner that the middle element is >>> *always *the mode ! >>> >>> -- >>> Rohit Saraf >>> Second Year Undergraduate, >>> Dept. of Computer Science and Engineering >>> IIT Bombay >>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>> >>> >>> On Thu, Apr 15, 2010 at 11:23 AM, Gauri wrote: >>> >>>> Can you illustrate it with an example ? >>>> How are you deciding the pivot for partitioning the array ? >>>> How the middle element can be the mode of the array ? >>>> >>>> Regards >>>> Gauri >>>> >>>> >>>> On Apr 14, 5:39 pm, vivek bijlwan wrote: >>>> > complexity : On) >>>> > extra - memory required : no >>>> > >>>> > have the first iteration of quick sort. return the middle element. >>>> > >>>> > >>>> > >>>> > On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: >>>> > > Say If I have an array of 1,000 32-bit integers .And one of the >>>> value >>>> > > is occuring 501 number of times or more in the array. Can someone >>>> help >>>> > > me devise an efficient algorithm for the same ? >>>> > >>>> > > Thanks & Regards >>>> > > Gauri >>>> > >>>> > > -- >>>> > > 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. >>> >> >> -- >> 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: Finding the mode in a set of integers
@rohit : can you give me any counter examples? PS: one value is occuring >=501 times. On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf wrote: > It cannot just be partitioned in such a manner that the middle element is > *always *the mode ! > > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > On Thu, Apr 15, 2010 at 11:23 AM, Gauri wrote: > >> Can you illustrate it with an example ? >> How are you deciding the pivot for partitioning the array ? >> How the middle element can be the mode of the array ? >> >> Regards >> Gauri >> >> >> On Apr 14, 5:39 pm, vivek bijlwan wrote: >> > complexity : On) >> > extra - memory required : no >> > >> > have the first iteration of quick sort. return the middle element. >> > >> > >> > >> > On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: >> > > Say If I have an array of 1,000 32-bit integers .And one of the value >> > > is occuring 501 number of times or more in the array. Can someone help >> > > me devise an efficient algorithm for the same ? >> > >> > > Thanks & Regards >> > > Gauri >> > >> > > -- >> > > 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. > -- 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] Finding the mode in a set of integers
complexity : On) extra - memory required : no have the first iteration of quick sort. return the middle element. On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: > Say If I have an array of 1,000 32-bit integers .And one of the value > is occuring 501 number of times or more in the array. Can someone help > me devise an efficient algorithm for the same ? > > Thanks & Regards > Gauri > > -- > 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: Complexity of searching in this alternate representation of tree
@Himanshu.
from what i think the complexity would be log(n) but the base would be the
no. of siblings that the node has.
Check if this answer is correct.
On Sun, Apr 11, 2010 at 2:08 PM, Himanshu Aggarwal
wrote:
> @Dave n Harshi, thanks for your answer.
>
> I am still not clear very much . May be u can help in elucidating your
> replies.
>
> If such a tree is degenerate, then the complexity of search is O(n), but if
> it is a well-balanced tree, where some nodes may have 'k' children and some
> nodes may have 'm' children , (where 'k' and 'm' are more than 2 and may not
> be necessarily equal) , then what would be the comlexity of searching?
>
> Would it of the order of log_2(n) or some other order like log_k(n) ? Or,
> Is it that the base of the logarithm is not at all important here?
>
> I hope I have made my doubt clear.
>
> ~Himanshu Aggarwal
>
>
> On Sun, Apr 11, 2010 at 9:01 AM, Dave wrote:
>
>> Your statement about the complexity of searching a binary search tree
>> applies only if the tree is balanced. In a degenerate tree, e.g.,
>> where each node has only one son, so that the tree is essentialy a
>> linked list, the complexity of searching is O(n).
>>
>> Dave
>>
>> On Apr 10, 10:56 am, Himanshu Aggarwal
>> wrote:
>> > Hi,
>> >
>> > The book on data structures by Langsam and Tanenbaum gives an alternate
>> > representation of trees as :
>> >
>> > struct treenode {
>> > int data;
>> > struct treenode * son;
>> > struct treenode * sibling;
>> >
>> > };
>> >
>> > Such type of nodes can be used to make trees in which each node can have
>> any
>> > number of siblings.
>> >
>> > I am unable to understand the algorithmic complexity of searching for a
>> node
>> > in such a tree?
>> >
>> > While a simple binary search tree gives search complexity as log_2(n),
>> where
>> > 'n' are the number of nodes in the tree, does such a tree also gives
>> > logarithmic complexity? In case it gives a logarithmic complexity, what
>> > would be the base of logarithm in this case. Would it be 2 or some
>> number
>> > 'k' where 'k' might be dependent on certain factors?
>> >
>> > Also, what might be the exact searching algo in this kind of a tree?
>> Some
>> > pseudo code would be really appreciated.
>> >
>> > Thanks for your help in understanding this problem.
>> >
>> > With Regards,
>> > Himanshu
>>
>> --
>> 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] Divide and Conquer problem
@ ashish .. each team should play the other team at least once. in merging that thing does not happen. On Thu, Apr 8, 2010 at 9:42 AM, Ashish Mishra wrote: > Can it be done in more or less like merge sort way > i.e 1. divide array into half > 2. keep on doing it till u have two element left > 3. arrang match between two and return winner > > > On Wed, Apr 7, 2010 at 12:20 PM, «« ÄÑÜJ »» wrote: > >> Can any one help me with this problem >> >> >> Its a divide and conquer problem where, there are n teams and each >> team plays each opponent only once. And each team plays exactly once >> every day. If n is the power of 2, I need to construct a timetable >> allowing the tournament to finish in n-1 days... >> >> Any help would be appreciated.. thanks >> >> -- >> 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. >> >> > > > -- > How soon 'not now' becomes 'never'... > > -- > 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] Finding youngest common ancestor of two nodes in a binary tree
@atul it is not a BST
On Thu, Apr 8, 2010 at 10:19 AM, atul verma wrote:
> Its very simple to solve this.
>
> Start from root.
>
> Compare the value of current node data value to both nodes.
>
> 1. if both are greater than current node then traverse node->right
> 2. if both are lesser than current node then traverse node->left
> 3. else return current node pointer.
>
> Any comments,
>
> Atul
>
>
> On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi wrote:
>
>> could you please elucidate more??
>>
>>
>> On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal <
>> lkml.himan...@gmail.com> wrote:
>>
>>> For a given binary tree, given the root and two node pointers, how can we
>>> find their youngest common ancestor.
>>>
>>> Say the node is like:
>>>
>>> struct node{
>>>int data;
>>>struct node*left, *right;
>>> };
>>>
>>> i.e the father field is not there.
>>>
>>> Please note that it is not a binary search tree, but just a binary tree.
>>>
>>> Thanks,
>>> Himanshu
>>>
>>> --
>>> 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.
>
--
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] Finding the middle of a singly linked list which has a cycle in it
keep a ptr ( pt1) at the beginning of the list. do increase another pointer ( pt2) by 1 and another pointer(pt3) by 2 while ( pt3 does not point to the same location as pt1) On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf wrote: > how do u define middle when there is a cycle in the list ? > > -Rohit > > > > On Sat, Mar 27, 2010 at 12:11 AM, Sanjana wrote: > >> Hello, >> Can someone help me out with this. How to find the middle of a singly >> linked list which also has a cycle in 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. >> >> > -- > 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] first K digit
we can use modular exponentiation to start with. On Tue, Mar 2, 2010 at 9:38 PM, rajesh patidar wrote: > i wanna to know how to find the kirst k digit of n^n > n can wary from 0 > -- > 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] string ques
explain the question a little further please On Tue, Feb 2, 2010 at 11:03 AM, Algoose Chase wrote: > Hope you meant a pattern is sub-array containing 2 or more UNIQUE chars. > hope based on dfn, "abcd" is also a pattern in the input you have given. > > > On Tue, Feb 2, 2010 at 1:11 AM, ankit mahendru > wrote: > >> Q. Find all the patterns once which are present in the character array >> given. A pattern is a sub-array containing 2 or more chars. >> >> Example: >> >> i/p: aabcdadabc >> >> o/p: ab, abc, bc, da >> >> -- >> 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] Coding Problems
you want it rewarding , go to codechef.com On Tue, Feb 2, 2010 at 6:30 PM, Anurag Bhatia wrote: > www.projecteuler.net has some interesting problems. > > On Tue, Feb 2, 2010 at 6:07 PM, sharad kumar > wrote: > > www.topcoder.com/tc > > www.spoj.pl > > > > On Tue, Feb 2, 2010 at 4:24 PM, Neeraj Singh <17.neera...@gmail.com> > wrote: > >> > >> Hey fellas, > >> > >> I need to seek some advice from you all. > >> > >> I have recently developed strong interest in programming problems. > >> So, What is the best place I should start practicing my skills. > >> > >> It would be great if the effort is rewarding as well. > >> > >> Thanks in advance. > >> > >> TY > >> -- > >> Neeraj > >> Ted Turner - "Sports is like a war without the killing." > >> > >> -- > >> 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. > > -- 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: Merge two BST in O(n) time with O(1)
@meena that is too specific example that you have taken. such a BST2 can be inserted into BST1 in linear time any which way. On Fri, Jan 29, 2010 at 5:10 AM, Ashish Meena wrote: > Hi all, > > Lets say we do following steps to merge two BSTS's. Lets call them BST1 and > BST2. > > 1. Check the value of root of BST2. > 2. In BST1 find a place where root of BST2 can be put. > 3. Remove the children from this place and store them as BST3 and BST4. > 3. Attach BST2's root pointer at this place. > We dont have to do anything more for BST2 as all children of BST2 are > already at their proper place > Now our BST1 has BST2 merged to it but it doesnt have BST3 and BST4. > 4. Do inorder traversal of BST3 and BST4 and insert it to BST1. > > If we know the approximate size of BST1 and BST2 we can choose tree for our > step 1 accordingly. > > This algorithm doesnt need any extra memory and can be almost O(n), if BST3 > and BST4 are very small trees. > > Does anybody see any issues with this approach? > > > Regards, > Ashish > > > On Fri, Jan 29, 2010 at 2:52 PM, vivek bijlwan wrote: > >> @ shingray ... cartesian trees are not BSTs . I guess nirmal's question >> asks for a BST. >> also cartesian trees have extra space requirements. >> >> >> On Fri, Jan 29, 2010 at 12:07 AM, naga vinod kumar < >> vinodkumark...@gmail.com> wrote: >> >>> hi varun ,it cant be in O(n) time ,it can be merged in O(nlogn) time. >>> >>> >>> On Thu, Jan 28, 2010 at 10:37 PM, Varun S V wrote: >>> >>>> Delete the nodes in the second BST in postorder. As and when you delete >>>> this node, insert it into the first BST. >>>> >>>> >>>> >>>> On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan wrote: >>>> >>>>> hey nirmal . i don't get that when you merge the two linked list , >>>>> how do you get the BST? >>>>> making the BST would itself be a O(nlogn) process? >>>>> >>>>> On Jan 28, 5:03 am, Nirmal wrote: >>>>> > Given two binary search trees, how to merge them in O(n) time and >>>>> O(1) >>>>> > space? >>>>> > >>>>> > It can be done using O(n) space as below, >>>>> > >>>>> > 1. covert BST #1 into linked list or sorted array >>>>> > 2. covert BST #2 into linked list or sorted array >>>>> > 3. merge them... >>>>> > >>>>> > but how to do this in place? >>>>> >>>>> -- >>>>> 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. >>> >> >> -- >> 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. >> > > > > -- > Ashish Meena > > -- > 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: Merge two BST in O(n) time with O(1)
@ shingray ... cartesian trees are not BSTs . I guess nirmal's question asks for a BST. also cartesian trees have extra space requirements. On Fri, Jan 29, 2010 at 12:07 AM, naga vinod kumar wrote: > hi varun ,it cant be in O(n) time ,it can be merged in O(nlogn) time. > > > On Thu, Jan 28, 2010 at 10:37 PM, Varun S V wrote: > >> Delete the nodes in the second BST in postorder. As and when you delete >> this node, insert it into the first BST. >> >> >> >> On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan wrote: >> >>> hey nirmal . i don't get that when you merge the two linked list , >>> how do you get the BST? >>> making the BST would itself be a O(nlogn) process? >>> >>> On Jan 28, 5:03 am, Nirmal wrote: >>> > Given two binary search trees, how to merge them in O(n) time and O(1) >>> > space? >>> > >>> > It can be done using O(n) space as below, >>> > >>> > 1. covert BST #1 into linked list or sorted array >>> > 2. covert BST #2 into linked list or sorted array >>> > 3. merge them... >>> > >>> > but how to do this in place? >>> >>> -- >>> 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. > -- 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.
