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