Background: I was sent a coding challenge via Codility, and before diving into the (timed) test, I spent some time working on the demo. I won’t be sharing the actual code challenge, but the demo is fair game to discuss, it’s featured in a public blog post. It took me a few tries, but in a nutshell, I went from 17 points out of 100 (incorrect answer) to 64 points (mostly correct answers, complexity too high), to … well, I’m going to make you read all the way through to find out.

Here’s the problem domain:

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.

A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 8 elements:

A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1

P = 1 is an equilibrium index of this array, because:

  • A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]

P = 3 is an equilibrium index of this array, because:

  • A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]

P = 7 is also an equilibrium index, because:

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

and there are no elements with indices greater than 7.

P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

Write a function:

def solution(a)

that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

Assume that:

  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

FIRST ATTEMPT:

def solution(a)  
  a.length.times do |index|  
    if index == 0   
      return index if a[1..-1].reduce(:+) == 0  
    elsif a[0...index].reduce(:+) == a[index+1..-1].reduce(:+)   
      return index  
    else  
      return -1  
    end  
  end 
end

Screen Shot 2015-11-03 at 5.07.41 PM

Ouch. Yeah, some major problems here:

  • I could see it was failing on my tests, but I ran out of time (30 minutes) and had to submit.
  • The return -1 is in the wrong place, it’s getting activated here for any scenario that isn’t index 0 or index is an equilibrium index (without cycling through the whole array).
  • It’s wrong most of the time, including failing to account for equilibrium at the last (or -1) index of an array. I can fix that though!!

TAKE TWO:

def solution(a)  
  a.length.times do |index|  
    if index == 0   
      return index if a[1..-1].reduce(:+) == 0  
    elsif index == a.length-1  
      return index if a[0...index].reduce(:+) == 0  
    elsif a[0...index].reduce(:+) == a[index+1..-1].reduce(:+)   
      return index  
    end  
  end  
  return -1 
end

Screen Shot 2015-11-03 at 5.14.34 PMOk now we’re cooking with fire! This passed all the tests I could muster up and fixes the -1 index problem, but now I’m looking at one more small correctness fix and a big efficiency problem:

  • It’s still failing on single element arrays. Dammit. I can fix that!
  • My algorithm efficiency here is an O(n**2) — eeeeeek, that means that every time through the loop, the computer has to do something to every element in the loop the length of the array times. To clarify: let’s say the array has 8 numbers in it. I’m saying “go through the loop 8 times” (n = 8). Each time through the loop, add all the elements of the array together to see if they meet the index equality condition (so, add 8 numbers together, and do this 8 times, = 64 or 8^2).
  • Rather than calculating the array sum each time, multiple times, I can bump up the efficiency by keeping a running total for left and right and adding/subtracting numbers to it as we walk through the array. So how about a little each_with_index?

ONCE MORE INTO THE FRAY:

def solution(a)  
  left = 0  
  right = a.reduce(:+)  
  a.each_with_index do |value, index|  
    if index == 0  
      right -= value  
      return index if a.length == 1 || right == 0  
    elsif index == a.length-1  
      left += a[index-1]  
      return index if left == 0  
    else  
      left += a[index-1]  
      right -= value  
      return index if left == right  
    end  
  end  
  return -1 
end

 

Screen Shot 2015-11-03 at 6.57.21 PM

YESSSS! This is so satisfying, y’all, I can’t even tell you. It is now about 3 hours after I started the challenge, so it *clearly* took me longer than the allotted 30 minutes (6 times as long, to be exact, though I also cooked dinner and wrote the first part of this blog in that time), but I’m proud that I was able to reach a correct, O(N) efficient solution, on my own, by the end of it.

Tomorrow morning I’ll do the real challenge. I’m a bit nervous but feeling a lot more confident than I was after seeing that first 17% score, so I hope this exercise was at least as fun to read as it is useful for me to write.