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