Re:Online Python Tutor
by tobiasSoftware on Sunday February 19, 2012 @11:25AM
(#3609627)
Actually, both your solution and theirs are not O(1). Theirs is n^2, while yours is n lg n due to the use of a sort function. The best way to do this would simply be to find the largest element, ignore that element and find the largest element again, which is O(n).
[ Parent
| on HN ]
Re:Online Python Tutor
by cmurphycode on Sunday February 19, 2012 @12:01PM
(#3609696)
I do believe the GP's message was that the tutor told him his solution took one "step", which is not equivalent to O(1), because sorted() takes O(nlgn).
In other words, he was pointing out the limitations of the tutor program's analysis.
I'm perfectly aware, but can you take that approach and execute it in 6 "steps" for all data sizes?
Since the whole point of the exercise is "optimizing" maxPairSum so that it runs in 20 "steps" or less, I guess this slower solution is still more "optimized" - which was my whole point, after all. :)
(Please note 6 steps is the bare minimum - one for the function definition, one for preparing input, one for calling the function, one for calling the function, one for assigning function arguments, one for the actual function and one for returning from the function. You can't go shorter than this.)
Indeed, but it won't even accept the following O(n) solution. I get "(stopped after 20 steps to prevent possible infinite loop)" when submitting this:
def maxPairSum(lst):
if lst[0] > lst[1]:
top, top2 = lst[:2]
else:
top2, top = lst[:2]
for i in range(2, len(lst)):
if lst[i] > top:
top, top2 = lst[i], top
elif lst[i] > top2:
top2 = lst[i]
return top+top2