fill in the gaps exercise - return second biggest element in list (7)

1 Name: #!/usr/bin/anonymous : 2011-03-28 13:48 ID:MHSY0ABv

I apologize if you find this problem trivial, but we were all beginners once.

Right I found this question: http://pastebin.com/qJ1fpswn

But I couldn't do it. This is what I have so far:

def second_biggest(mylist):

second_biggest=-5
biggest=-1
for element in mylist:
if element>biggest:
second_biggest=
biggest=element
elif element>second_biggest:
second_biggest=
return second_biggest
'''
for any item in the list if an element is greater than the previous element then
it should be assigned to the variable biggest'''

'''
if the element is greater than second_biggest, then second_biggest should equal...'''


And my own solution: http://pastebin.com/qWacEGzL

2 Name: #!/usr/bin/anonymous : 2011-03-29 02:33 ID:Heaven

Do your own homework

3 Name: #!/usr/bin/anonymous : 2011-03-29 08:02 ID:Heaven

it's not my homework I'm doing it from MIT's open course wear.

4 Name: #!/usr/bin/anonymous : 2011-03-30 05:46 ID:fmRJhWdJ

It's trivial. All you need is to maintain a sorted queue of the two biggest numbers found so far, where the queue is represented by the variables biggest and second_biggest. So if you find something bigger than biggest, you shift the whole queue and if you find something bigger than just the second record in the queue, you just replace this record.
General algorithms for N-th number out of M are way more tricky.

5 Name: #!/usr/bin/anonymous : 2011-04-02 03:52 ID:Heaven

> way more tricky

I disagree. It still lends itself easily to a straightforward constant-space algorithm. The only complexity is that the code no longer can be done with ad-hoc variables, so it pretty much forces you to handle the top-n subset of your input data as a sorted array. (Which, pedagogically speaking, is a very good thing. Variables like "fifth_biggest" give me nervous tics.)

You're basically sorting the input, and pruning the sorted list as you go along. The queue is never going to exceed n items, and after the input is exhausted, you pluck the bottom (nth) item from the queue. You could do a modified insert/merge-sort algorithm with a "falling-off" effect. It involves, instead of manually handling the individual elements, making a separate array to store the top N elements of your incoming data.

6 Name: #!/usr/bin/anonymous : 2011-04-04 00:23 ID:BSO72EOy

>>5
You should be putting your highest m numbers in a binary search tree. Then for each number: 1. you insert it in the BST. and 2. remove the (m+1)th smallest element in the tree.

So you would get a O(n log m) algorithm instead of a O(nm) algorithm, where n is the number of elements in the array, and m is from the mth largest element that you want.

7 Name: #!/usr/bin/anonymous : 2011-04-04 00:30 ID:BSO72EOy

>>6
Oh lawdy. It only now occurred to me that this is the selection problem, which is O(n). You can look it up in wikipedia or something.

Return Entire thread Last 50 posts
This thread has been closed. You cannot post in this thread any longer.