Carlos shared a pretty cool link with me this morning. Codility is a platform to help recruiters and contractors to test developers before hiring them. Both the idea and the execution are beautiful. They’ve done a stunning job.
As part of my visit to the page I gave a try to the demo test. As it was fun to solve it, I’m sharing my solution here. The problem was quite easy. It reads like this:
Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:
A=-7 A=1 A=5 A=2 A=-4 A=3 A=0
3 is an equilibrium index, because:
6 is also an equilibrium index, because:
(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A.
Assume the sum of zero elements is equal zero. Write a function int equi(int A); that given a sequence, returns its equilibrium index (any) or -1 if no equilibrium indexes exist. Assume that the sequence may be very long.
They gave me 30 minutes to design, code and test my solution. Here it is (tests omitted):
import operator def equi(A): if A is None or len(A) == 0: return -1 lsum = index = 0 rsum = reduce(operator.add, A[1:], 0) while True: if lsum == rsum: return index index += 1 if index == len(A): return -1 else: lsum += A[index-1] rsum -= A[index]
It scores 100/100 and runs in linear time (that’s tricky because O(n2) algorithms will cause performance tests to fail) :)