it doesn't matter
in that case
list 3 becomes: (step 2)
9<-9<-9<-9<-10<-H3
after processing it becomes (step 3)
H3->1->0->0->0->0->0
On Tue, Feb 2, 2010 at 3:42 PM, Harish U <harishs...@gmail.com> wrote:
> saurabh pleeeeeeeeeeease look at the list that i have mentioned carefully
> .. second list must be H2->4->4->4->4->5 and not H2->4->4->4->4->4.
>
> Its straight forward to do the job with the list you have done with so far.
>
> On Tue, Feb 2, 2010 at 12:22 PM, saurabh gupta <sgup...@gmail.com> wrote:
>
>> 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 <harishp...@gmail.com>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 <sgup...@gmail.com>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 <sgup...@gmail.com>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
>>>>> <harishp...@gmail.com>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 <sgup...@gmail.com>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 <r.deva...@gmail.com> 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
>>>>>>>> <sgup...@gmail.com>wrote:
>>>>>>>>
>>>>>>>>> step 1 is n not m
>>>>>>>>> which makes it O(3n)
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta
>>>>>>>>> <sgup...@gmail.com>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 <
>>>>>>>>>> abhati...@gmail.com> 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 <
>>>>>>>>>>> harishp...@gmail.com> 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 <
>>>>>>>>>>> sgup...@gmail.com> 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 <
>>>>>>>>>>> abhati...@gmail.com>
>>>>>>>>>>> >> 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 <
>>>>>>>>>>> harishp...@gmail.com>
>>>>>>>>>>> >>> 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
>>>>>>>>>>> algoge...@googlegroups.com.
>>>>>>>>>>> >>> > To unsubscribe from this group, send email to
>>>>>>>>>>> >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>> .
>>>>>>>>>>> >>> > For more options, visit this group at
>>>>>>>>>>> >>> > http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>>>> >>> >
>>>>>>>>>>> >>>
>>>>>>>>>>> >>> --
>>>>>>>>>>> >>> You received this message because you are subscribed to the
>>>>>>>>>>> Google Groups
>>>>>>>>>>> >>> "Algorithm Geeks" group.
>>>>>>>>>>> >>> To post to this group, send email to
>>>>>>>>>>> algoge...@googlegroups.com.
>>>>>>>>>>> >>> To unsubscribe from this group, send email to
>>>>>>>>>>> >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>> .
>>>>>>>>>>> >>> For more options, visit this group at
>>>>>>>>>>> >>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>>>> >>>
>>>>>>>>>>> >>
>>>>>>>>>>> >> --
>>>>>>>>>>> >> You received this message because you are subscribed to the
>>>>>>>>>>> Google Groups
>>>>>>>>>>> >> "Algorithm Geeks" group.
>>>>>>>>>>> >> To post to this group, send email to
>>>>>>>>>>> algoge...@googlegroups.com.
>>>>>>>>>>> >> To unsubscribe from this group, send email to
>>>>>>>>>>> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>> .
>>>>>>>>>>> >> For more options, visit this group at
>>>>>>>>>>> >> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>>>> >
>>>>>>>>>>> > --
>>>>>>>>>>> > You received this message because you are subscribed to the
>>>>>>>>>>> Google Groups
>>>>>>>>>>> > "Algorithm Geeks" group.
>>>>>>>>>>> > To post to this group, send email to
>>>>>>>>>>> algoge...@googlegroups.com.
>>>>>>>>>>> > To unsubscribe from this group, send email to
>>>>>>>>>>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>> .
>>>>>>>>>>> > For more options, visit this group at
>>>>>>>>>>> > http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>>>> >
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> You received this message because you are subscribed to the
>>>>>>>>>>> Google Groups "Algorithm Geeks" group.
>>>>>>>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>> .
>>>>>>>>>>> For more options, visit this group at
>>>>>>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> You received this message because you are subscribed to the Google
>>>>>>>>> Groups "Algorithm Geeks" group.
>>>>>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>> .
>>>>>>>>> For more options, visit this group at
>>>>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> You received this message because you are subscribed to the Google
>>>>>>>> Groups "Algorithm Geeks" group.
>>>>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>> .
>>>>>>>> For more options, visit this group at
>>>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> You received this message because you are subscribed to the Google
>>>>>>> Groups "Algorithm Geeks" group.
>>>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>>>> To unsubscribe from this group, send email to
>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>> .
>>>>>>> For more options, visit this group at
>>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>> .
>>>>>> For more options, visit this group at
>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>
>>>>>
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>> .
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
