~Nacho/blog

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[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(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(n²) algorithms will cause performance tests to fail) :)