Coding test at codility.com

Some one sent me an invitation to take a programming test at codility.com. Before taking the real test, I want to know how codility.com work, therefore I decided to take the demo test first.

Here the demo test question:

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 = 7 elements:

A[0] = -7 A[1] = 1 A[2] = 5
A[3] = 2 A[4] = -4 A[5] = 3
A[6] = 0
P = 3 is an equilibrium index of this array, because:

A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
P = 6 is also an equilibrium index, because:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 0
and there are no elements with indices greater than 6.

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

Write a function

function equi($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.

Assume that:

N is an integer within the range [0..10,000,000];
each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].
For example, given array A such that

A[0] = -7 A[1] = 1 A[2] = 5
A[3] = 2 A[4] = -4 A[5] = 3
A[6] = 0
the function may return 3 or 6, as explained above.

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.

And here my answer:


<?php

$test = array(
 0 => -7,
 1 => 1,
 2 => 5,
 3 => 2,
 4 => -4,
 5 => 3,
 6 => 0,
 );

function equi($A) {
 for ($i = 0; $i < count($A); $i++) {

$sum_left = 0;
 $sum_right = 0;

if ($i > 0) {
 //sum left
 for ($h = $i - 1; $h >= 0; $h--) {
 $sum_left += $A[$h];
 }
 }

// sum right
 for ($j = $i + 1; $j < count($A); $j++) {
 $sum_right += $A[$j];
 }

$eq = -1;

if ($sum_left == $sum_right) {
 $eq = $i;
 break;
 }
 }

return $eq;
 }

echo equi($test);
 ?>

You can take the demo test here:

http://codility.com/demo/take-sample-test/

Share

One thought on “Coding test at codility.com

  1. Thank you for your effort but this code has complexity of O(N2) and the lowest complexity for the result should be O(N) .

Leave a Reply

Your email address will not be published. Required fields are marked *