this is how it works list 1 : H1->5->5->5->5->5 list 2 : H2->4->4->4->4->4
now we need to return a list say list 3 as our answer which contains the sum and length at most n+1 (in this case as m=n) step 1 : we spent O(n) to simply conclude they are of same length step 2: list 3: 9<-9<-9<-9<-9<-H3 (we haven't used any extra space simply utilized the space where we store the answer) (not the pointers in lis3 they are in the 'opposite' sense) plus we haven't touched 1 or 2 step 3: list 3: H3->9->9->9->9->9 this is the answer. This is actually a special case. On Tue, Feb 2, 2010 at 10:40 AM, Algoose Chase <[email protected]> wrote: > @saurabh : > so you scanned to find out that both lists are same : O(n) (agreed) > prepare list 3 in time O(n) (agreed) > process list 3 in time O(n) (*HOW ??*) > > can you run through your method and show how you process list 3 in O(n) > using the below lists as input: > > 5->5->5->5->5->5->5->5->5->5 and > 4->4->4->4->4->4->4->4->4->5 > > hope you know the constraints : you cant reverse original list. and you > cant use recursion. and you need to traverse the list LEFT TO RIGHT to > satisfy the first 2 conditions. > > Yes , I agree these lists takes O(n) time: list 1 = 4->7->8->1->6 > > list 2 = > 2->3->4 > but not in all cases. > I agree that for most cases(except the wild ones) the running time must be > O(n) only but you certainly need multiple passes depending upon the input. > > Hope I am clear ! > > > On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta <[email protected]> wrote: > >> the key observation is that your requirement for no space is nullified by >> using the space in the resultant list. >> >> so you scanned to find out that both lists are same : O(n) >> prepare list 3 in time O(n) >> process list 3 in time O(n) >> >> current list 3 is the answer as list 4 is empty >> total time O(n) as k is small >> >> >> >> On Mon, Feb 1, 2010 at 11:19 PM, saurabh gupta <[email protected]> wrote: >> >>> nope, >>> if both lists are of same length list 4 is not required and you save time >>> to deal with list 4 >>> so, you have list 3 only >>> time reqd is O(3n) >>> >>> 3 passes approximately >>> >>> >>> >>> On Mon, Feb 1, 2010 at 11:24 AM, Algoose Chase <[email protected]>wrote: >>> >>>> Thats true ! , The purpose is to add very long integers such that we >>>> cant use premative data types to represent them. >>>> >>>> The point I was trying to prove is : you would need to go through >>>> multiple passes through the list(essentially to propagate carry) when you >>>> have conditions like No Reversing the original lists and no recursion and >>>> no >>>> to any extra memory usage. >>>> >>>> @ saurabh: Hope you have not considered the worst case before >>>> generalizing the running time to 2n+m . >>>> >>>> lets assume the 2 lists are of same size so n = m.This eliminates the >>>> need to find out m or to create list 4 >>>> and lets assume the linked list are 5->5->5->5->5->5->5->5->5->5 and >>>> >>>> 4->4->4->4->4->4->4->4->4->5 >>>> Only thing is you need to create list 3 (as u have mentioned) . Now its >>>> not possible to add the 2 lists through a single pass from left to right . >>>> This would need n passes on a linked list of size n making the running >>>> time >>>> n^2. >>>> >>>> >>>> >>>> On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta <[email protected]>wrote: >>>> >>>>> this defeats the purpose, >>>>> they are stored in linked list because they cannot be stored in a given >>>>> type. >>>>> >>>>> >>>>> >>>>> On Thu, Jan 28, 2010 at 3:25 AM, Deva R <[email protected]> wrote: >>>>> >>>>>> i faced this qn in ********* interview. >>>>>> >>>>>> best soln i could give was: >>>>>> >>>>>> - traverse each list and derive both the numbers.. something like >>>>>> below >>>>>> >>>>>> node = list->head; >>>>>> i=1; value =0; >>>>>> while (node) >>>>>> { value = (node->data)*i +value; >>>>>> i*=10; >>>>>> node = node->next; >>>>>> } >>>>>> >>>>>> - add both the numbers. u can either return the number or form a new >>>>>> list and return. >>>>>> >>>>>> i gave the code.. and its o(m+n), for lists of size m,n. >>>>>> >>>>>> -Deva >>>>>> >>>>>> >>>>>> >>>>>> On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta <[email protected]>wrote: >>>>>> >>>>>>> step 1 is n not m >>>>>>> which makes it O(3n) >>>>>>> >>>>>>> >>>>>>> On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta <[email protected]>wrote: >>>>>>> >>>>>>>> its not exponential >>>>>>>> time to find out m = m >>>>>>>> time to create list 3 = m >>>>>>>> time to create list 4 = n-m >>>>>>>> time to come up with proper added list (list 3 modification) = m >>>>>>>> time to merge list 3 and list 4 = n-m >>>>>>>> >>>>>>>> total time = 2n+m >>>>>>>> >>>>>>>> except step 1 all are reversals with approximately same constant and >>>>>>>> constant for step 1 is smaller >>>>>>>> so one can say >>>>>>>> >>>>>>>> O(2n+m) >>>>>>>> >>>>>>>> >>>>>>>> On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia <[email protected] >>>>>>>> > wrote: >>>>>>>> >>>>>>>>> If that is the representation, then the lists have to be reversed. >>>>>>>>> Otherwise the time goes up exponentially. >>>>>>>>> >>>>>>>>> On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase < >>>>>>>>> [email protected]> wrote: >>>>>>>>> > Condition: >>>>>>>>> > Can we do it keeping the original lists intact ? ie without >>>>>>>>> reversing it. >>>>>>>>> > I mean , No recursion & no Reversing ... is it possible ? >>>>>>>>> > >>>>>>>>> > @kumar : >>>>>>>>> > 15234 is represented as 1->5->2->3->4 >>>>>>>>> > >>>>>>>>> > On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta < >>>>>>>>> [email protected]> wrote: >>>>>>>>> >> >>>>>>>>> >> perhaps you mean, >>>>>>>>> >> reverse each link list O(n+m). >>>>>>>>> >> then sum each node with carryover maintained. >>>>>>>>> >> >>>>>>>>> >> On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia < >>>>>>>>> [email protected]> >>>>>>>>> >> wrote: >>>>>>>>> >>> >>>>>>>>> >>> Let us take an example - >>>>>>>>> >>> >>>>>>>>> >>> Num 1 = 123456 >>>>>>>>> >>> Num 2= 1234 >>>>>>>>> >>> Link-1->Link-2->Link-3->Link-4->Link5->Link6 >>>>>>>>> >>> Link-1->Link-2->Link-3->Link-4 >>>>>>>>> >>> >>>>>>>>> >>> Add nodes into linkedlist 1 till either one of the list is not >>>>>>>>> null. >>>>>>>>> >>> Make sure you process the carry in each iteration. >>>>>>>>> >>> >>>>>>>>> >>> >>>>>>>>> >>> --AB >>>>>>>>> >>> >>>>>>>>> >>> >>>>>>>>> >>> On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase < >>>>>>>>> [email protected]> >>>>>>>>> >>> wrote: >>>>>>>>> >>> > conditions: >>>>>>>>> >>> > NO extra memory (@ stack or Heap) at all. No recursion. >>>>>>>>> >>> > >>>>>>>>> >>> > Any body has got any hint about how to get this done ? >>>>>>>>> >>> > >>>>>>>>> >>> > >>>>>>>>> >>> > >>>>>>>>> >>> > -- >>>>>>>>> >>> > You received this message because you are subscribed to the >>>>>>>>> Google >>>>>>>>> >>> > Groups >>>>>>>>> >>> > "Algorithm Geeks" group. >>>>>>>>> >>> > To post to this group, send email to >>>>>>>>> [email protected]. >>>>>>>>> >>> > To unsubscribe from this group, send email to >>>>>>>>> >>> > [email protected]<algogeeks%[email protected]> >>>>>>>>> . >>>>>>>>> >>> > 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 >>>>>>>>> [email protected]. >>>>>>>>> >>> To unsubscribe from this group, send email to >>>>>>>>> >>> [email protected]<algogeeks%[email protected]> >>>>>>>>> . >>>>>>>>> >>> 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 [email protected] >>>>>>>>> . >>>>>>>>> >> To unsubscribe from this group, send email to >>>>>>>>> >> [email protected]<algogeeks%[email protected]> >>>>>>>>> . >>>>>>>>> >> 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 [email protected]. >>>>>>>>> > To unsubscribe from this group, send email to >>>>>>>>> > [email protected]<algogeeks%[email protected]> >>>>>>>>> . >>>>>>>>> > 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 [email protected]. >>>>>>>>> To unsubscribe from this group, send email to >>>>>>>>> [email protected]<algogeeks%[email protected]> >>>>>>>>> . >>>>>>>>> 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 [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]<algogeeks%[email protected]> >>>>>>> . >>>>>>> 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 [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]<algogeeks%[email protected]> >>>>>> . >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]<algogeeks%[email protected]> >>>>> . >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[email protected]> >>>> . >>>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
