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] = 1P = 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
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
Ok 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
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.
Leave a Reply