http://www.careercup.com/question?id=14099679

import random
import time
import collections
import sys



def solve(A):
    INT_MAX = sys.maxint

    MAX_TABLE = 3
    HASHTABLE = collections.defaultdict(int)

    N = len(A)

    for i in range(0, N):
        if len(HASHTABLE) >= MAX_TABLE:
            break
        HASHTABLE[A[i]] += 1

    for i in range(i, N):
        if A[i] in HASHTABLE:
            HASHTABLE[A[i]]+=1

        elif len(HASHTABLE) < MAX_TABLE:
            HASHTABLE[A[i]] = 1

        else:
            # make some room for new element

            # first, find the least frequent
            min_element = None
            min_count = INT_MAX
            for element,count in HASHTABLE.iteritems():
                if count < min_count:
                    min_element, min_count = element, count

            HASHTABLE[min_element] -= 1
            if HASHTABLE[min_element] <= 1:
                del HASHTABLE[min_element]
                HASHTABLE[A[i]] = 1

    #print HASHTABLE, N, N/3

    ret = {}
    for element, count in HASHTABLE.iteritems():
        ret[element] = "%.2f%%" % (float(count)/ N)

    return ret

def main(N):

    N3 = N / 3 + 1


    A = [1] * N3
    #A.extend([2] * N3)
    #A.extend([3] * (N - len(A))) # int(N3 * 0.5)

    L = len(A)
    garbage_size = N - L
    A.extend([random.randint(3,4) for i in range(garbage_size)])

    S = solve(A)
    print S

    random.shuffle(A)
    S = solve(A)
    print S


if __name__=='__main__':

    MAX_TESTS = 6 if len(sys.argv) == 1 else int(sys.argv[1])

    SCALE = 10e6

    N = 10
    for t in range(0, MAX_TESTS):
        begin = time.clock()
        main(N)
        end = time.clock()
        T = end - begin
        print "test#%d: array_size: %d speed factor:%f" % (t, N, SCALE * (end - begin)/N )
        N *= 10