Median solving from Interview street in Python

Question

Any suggestions to improve the performance of the following code? This code is exceeding the time limit for the last four cases. This is a solution to the problem https://www.interviewstreet.com/challenges/dashboard/#problem/4fcf919f11817

def main():
    N = int(raw_input())
    if(0<=N<=100000):
        x = []
        ans=[]
        l=[]
        m=[]
        for i in xrange(0, N):
            tmp = raw_input()
            a, b = [xx for xx in tmp.split(' ')]
            l.append(a)
            m.append(int(b))  

        for i in xrange(0, N):
            if l[i]=='r':
                if len(x)<1 or m[i] not in x:
                        ans.append('Wrong!')
                elif m[i] in x:
                    x.remove(m[i])
                    q=len(x)
                    if q%2==1:
                        ans.append(x[(q/2)])
                    elif q%2==0:
                        if q==0:
                            ans.append('Wrong!')
                        else:
                            k=x[q/2]+x[(q/2)-1]
                            if k%2==0:
                                ans.append(int(k)/2)
                            else:
                                ans.append(k/2.0)
            elif l[i]=='a':
                x.append(m[i])
                x=sorted(x)
                p=len(x)
                if p%2==1:
                    ans.append(x[(p/2)])
                else:
                    k=x[p/2]+x[(p/2)-1]
                    if k%2==0:
                        ans.append(int(k)/2)
                    else:
                        ans.append(k/2.0)

        for i in ans:
            print i

if __name__ == "__main__":
    main()

---

from sys import stdin,stdout
from bisect import bisect,insort
def main():
    N = int(raw_input())
    x = []
    ans = []
    append = x.append
    ans_append = ans.append
    remove = x.remove
    read = stdin.readline
    for i in xrange(0, N):
        tmp = read()
        a, b = tmp.split(' ')
        b = int(b)
        if a == 'r':
            search_result = search(x,b)
            if len(x) < 1 or not(search_result):
                ans_append('Wrong!') 
            else:
                remove(b)
                ans_append(median(x))                   
        else:
            insort(x, b)
            ans_append(median(x))
    for i in ans:
        print i

def median(arr):
    q = len(arr)
    if q==0:
        return 'Wrong!'
    if q%2 == 1:
        return arr[(q/2)]
    else:
        k = arr[q/2] + arr[(q/2)-1]
        if k%2 == 0:
            return int(k)/2
        else:
            return k/2.0

def search(arr,element):
    position = bisect(arr, element)
    if len(arr) >= position and len(arr)!=0:
        if arr[position-1] == element:
            return True
        else:
            return False
    else:
        return False

if __name__ == "__main__":
    main()

Answer 1

def main():
    N = int(raw_input())
    if(0<=N<=100000):

There really isn't much point in checking this. Your code works regardless of the value, and you don't need to worry about whether the contest will feed you larger values

        x = []
        ans=[]
        l=[]
        m=[]

I suggest using longer names even in a contest scenario

        for i in xrange(0, N):
            tmp = raw_input()
            a, b = [xx for xx in tmp.split(' ')]

Actually this line is the same as a, b = tmp.split(' ') The list comphrension just wastes processing power. Since there isn't going to be any unusual whitespcae, you can skip the parameter to split as well

            l.append(a)
            m.append(int(b))  

Its not clear why you store this in a list. Just perform the operation as soon as you read it. No need to store things into the lists just to read them in another loop.

        for i in xrange(0, N):

Here you should have used something like for action, number in zip(l,m):

            if l[i]=='r':
                if len(x)<1 or m[i] not in x:

There isn't really a point to checking for len < 1, since the second condition will fail in that case anyways

                        ans.append('Wrong!')

Just print out the output, don't store it up

                elif m[i] in x:

You should be able to just make this an else

                    x.remove(m[i])

This is going to be slow. The checks for m[i] in x and the call to remove have to scan over the whole list to find the elements. But the list is sorted, which means you should be able to find elements faster. Check out the bisect module which enables provides binary search to make finding elements faster in sorted lists.

                    q=len(x)
                    if q%2==1:
                        ans.append(x[(q/2)])
                    elif q%2==0:
                        if q==0:
                            ans.append('Wrong!')

This case is somewhat odd here, it'd make more sense to check for this on level out, before checking for odd and even

                        else:
                            k=x[q/2]+x[(q/2)-1]
                            if k%2==0:
                                ans.append(int(k)/2)
                            else:
                                ans.append(k/2.0)
            elif l[i]=='a':
                x.append(m[i])
                x=sorted(x)

This is better written as x.sort() so as to sort in place. However, its going to be slow constantly resorting the list. Before adding the element, the list is almost sorted, so you can use that to your advantage. The bisect module has operations to make that easy

                p=len(x)
                if p%2==1:
                    ans.append(x[(p/2)])
                else:
                    k=x[p/2]+x[(p/2)-1]
                    if k%2==0:
                        ans.append(int(k)/2)
                    else:
                        ans.append(k/2.0)

Ok, you're doing this again. You should have put this in a function or something

        for i in ans:
            print i

if __name__ == "__main__":
    main()

Maintaining a sorted list is too expensive. Everytime you insert or remove elements, the computer has to shift the whole array in memory. Knowing this the contest site will devise questions to give you the worst case scenario. You are going to have to do something else.

One possibility to explore would be to use a binary tree. Binary trees have faster insertion/removal times, and a reasonably fast way to calculate the median. Their disadvantage here is the complexity required to implement it. A binary tree itself isn't that complicated, but the problem is in a balancing strategy.

A second possibility is to try and use heaps implemented in the heapq module. The idea would be that at any point in time, you maintain two heaps. One has the element less then the median and the other has the elements greater then the median. There is some trickiness there in how you would handle deletions, but I think it could be done.