List2 exercises

[Elma Luv]

PROBLEM E.:  Given two lists sorted in increasing order, create and return a merged

 list of all the elements in sorted order. You may modify the passed in lists.

 Ideally, the solution should work in "linear" time, making a single

 pass of both lists.

GIVEN SOLUTION:

def linear_merge(list1, list2):

 

  result = []

  while len(list1) and len(list2):

    if list1[0] < list2[0]:

      result.append(list1.pop(0))

    else:

      result.append(list2.pop(0))

  result.extend(list1)

  result.extend(list2)

  return result

MY SOLUTION:

def linear_merge(list1, list2):

    list1.extend(list2)

    return sorted(list1)

I try to work out the problem first before confirming with the provided solution.  This is what I came up with after reading this exercise problem.  It sounded too simple, so I looked at their solution and became confused.  BUT, no matter how many times I test it, I always get the correct answer, same as theirs.  My question is, maybe I'm testing too simple examples (although I tried to mix it up), could this be right? And what would ultimately trip me into bad answer or error?  Thanks. 

[Mike Wang]

I believe the reason they don't use your solution is that they ask for it to be done in linear time and the sorted() function doesn't run in linear time. Look at the source I provided below. If you are not familiar with what "linear time" references, it is something you would learn in a Logic and Discrete Math course, or at least that's where I learned about it. It deals with estimating an upper limit/bounds of how long a function will take, but I imagine it might be above the range of knowledge of the average person that completes Google's python course, since it is an introductory computer science course, though I might be underestimating the average participant. 

Linear merging for lists in Python

[Elma Luv]

Mike,

thank you very much for that explanation.  I had a hunch it was something to do with that, but still couldn't see where my solution wouldn't work.  Thank you!  

ps.  Did you post that questions on Stackoverflow, or did someone have the identical problem/question/solution as I?  I'll be studying it, replies, and linear time concept. 

[Robert Mandić]

If we ignore the fact that this is for your school: Never do it the first way.

The second solution is also more readable and pythonic.

​Almost every tutorial/book has taught me that I should never modify a list that I'm iterating through.

​

--
You received this message because you are subscribed to the Google Groups "Python GCU Forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python-gcu-for...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Lp, Robert