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