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 algogeeks@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.
