@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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
