Codility tests

disc.py

#!/usr/bin/env python2
from itertools import combinations

def number_of_disc_intersections(A):
    boundries = list()

    for x, r in enumerate(A):
        boundries.append((x-r, x+r))
    
    r = range(len(A))
    pairs = combinations(r, 2)

    def overlap(k, j):
        k, j = boundries[k], boundries[j]
        if (k[1]>=j[0]):
            return 1
        else:
            return 0

    counts = list()

    for pair in pairs:
        counts.append(overlap(*pair))
    
    return sum(counts)

    
if __name__=='__main__':
    cnt = number_of_disc_intersections(range(2000))
    print "Count is %d" % cnt
    
""" Result was:

    53/100
   
    Time was O**2 :(
    
"""

equi.py

#!/usr/bin/env python2

from collections import defaultdict

def equi(A):
    sums = defaultdict(int)
    s = 0
    for x, a in enumerate(A):
        s += a
        sums[x] = s
    
    sums_r = defaultdict(int)
    s_r = 0
    for x, a in enumerate(A):
        sums_r[x] = s - sums[x] + a
        if sums_r[x] == sums[x]:
            return x
    return -1
            

if __name__=="__main__":
    print equi([-7, 1, 5, 2, -4, 3, 0])

""" Result: 100! :D """

prefix.py

#!/usr/bin/env python2

from collections import defaultdict

def ps(A):
    flags = defaultdict(bool)
    [flags[x] for x in set(A)]
    for p, a in enumerate(A):
        flags[a] = True
        if all(flags.values()):
            return p
    return 0

if __name__=='__main__':
    print ps([2, 2, 1, 0, 1])

""" Score: 92.3

Detected time complexity:
O(N*log(N)) or O(N) or O(N**3)

Failed on 

random_n_10000 
random test 10 000 elements and values. 1.276 s.    TIMEOUT ERROR 
running time: >1.28 sec., time limit: 1.10 sec.

"""