3
\$\begingroup\$

I did a sample on Codility and finished the test task.

The problem description is very short:

The 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$$

(The sum of zero elements is zero) \$7\$ is not an equilibrium index - because it is not a valid index of sequence A. If you still have doubts, here is a precise definition: The integer \$k\$ is an equilibrium index of a sequence \$A[0],A[1]\dots,A[n-1]\$ if and only if \$0\le k\$ and \$\sum(A[0\dots(k-1)])=\sum(A[(k+1)\dots(n-1)])\$. Assume the sum of zero elements is equal to zero.

The code I wrote gives the correct result, but, I only scored 8% on correctness and a 54% on performance. Here is my code:

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {


    // write your code in JavaScript (Node.js 4.0.0
    var arrLen = A.length;

    var i = 0;



    for(i = 0; i < arrLen; i++){

        //console.log("i: " + i);

         var firstSum = 0;
        var secSum = 0;

        var currIndex = i + 1;

        //get first chunk
        var j = 0;
        var lenJ = currIndex;

        for(j = 0; j < lenJ; j++){

            //console.log("firstChink: " + j);
            firstSum += A[j];

        }


        //get second chunk
        j = currIndex + 1;
        lenJ = arrLen;

        for(j; j < lenJ; j++){

            //console.log("secChunk: " + j);
            secSum += A[j];

        }

        if(firstSum == secSum){

            return currIndex;

        }



    }


    return arrLen;

}

Can somebody explain why my code scored so low? And what to do to improve?

\$\endgroup\$
0

3 Answers 3

5
\$\begingroup\$

I'm piggy backing on @jonah's answer. The first code snippet returns what Codility is asking for: any equilibrium index. Second code snippet returns all answers like in @jonah's suggestion. I also added two accumulating arrays for side by side comparison. You can add a breakpoint at the end of the function to compare the two arrays.

var A = [-1, 3, -4, 5, 1, -6, 2, 1];

function solution(A) {        
    var rightSum = A.reduce((acc, val) => acc + val, 0), leftSum = 0;
    
    for (var i = 0; i < A.length; i++) {
        
        rightSum -= A[i];

        // Codility is asking for any, so return first found
        if (rightSum === leftSum) return i; 
        
        leftSum += A[i];
    }
    
    return -1;
}

solution(A);

var A = [-1,3,-4,5,1,-6,2,1];

function solution(A) {
    
    var rightSum = A.reduce((acc, val) => acc + val, 0), leftSum = 0, rightSums = [], leftSums = [], answers = [];
    
    for (var i = 0; i < A.length; i++) {
        
        rightSum -= A[i];
        
        // You can keep track of answers for comparison/debugging
        rightSums.push(rightSum);
        leftSums.push(leftSum);
        
        if (rightSum === leftSum) answers.push(i);
        
        leftSum += A[i];
        
    }
    
    return answers;
}

solution(A);

\$\endgroup\$
4
\$\begingroup\$

Correctness:

Your code has a few syntax points that are bad form, and your indentation and spacing is incorrect in more than a few places (for example, the massive amount of extraneous lines)

You should consider using a code cleaner, like JSFiddle's TidyUp to tidy your code up, and you can inspect the changes made to learn to improve, but a few major ones are as follows:

for loop:

var arrLen = A.length;

var i = 0;



for(i = 0; i < arrLen; i++){

A for loop has the built-in feature to define variables, and not just more than one, in which case, this can be converted to the following: (Additionally, you shouldn't sacrifice readability for a few characters, arrLen is fine as arrayLen or arrayLength)

for(var i = 0, length = A.length; i < length; i++){

Clarity of variables:

function solution

solution is unclear, consider improving that with something like: equiSolution or equi. secSum is a bit ugly unclear, and for sakes of readability, a few characters won't hurt.

Getting Chunks:

Similarly to the for loop point above: you shouldn't need to define lenJ, or manually define j:

for (var j = 0, length = i + 1; j < length; j++){
    firstSum += A[j];
}

for(var j = i + 2, length = A.length; j < length; j++){
    secondSum += A[j];
}

console.log:

Instead of blind commented-out logs everywhere, use a debug variable with a helper function:

function log(string){
    var debug = true;
    if (debug) console.log(string);
}

// ...
log("firstChink: " + j); //<-- also spelling mistake here

With that helper function in place you can just change the debug variable if you want them not to be logged. Ideally, you would keep that debug variable as a constant at the top of the program, but for a small script like this, probably not necessary.

Returning -1:

In the case that there is no equilibrium in the array, -1 is supposed to be returned, however, instead you're returning arrLen (the length of the array). Returning the array length will cause test failure in those cases.


Performance:

\$O(n^2)\$ solution:

Your solution is currently \$O(n^2)\$, meaning the operation is processed however many elements there are squared, while the Codility page explains how an \$O(n)\$ solution can be attained:

Instead of using a solution where you check the sums of both sides relative, use the following rule:

\$S_R\$ = sum of right side, \$S_L\$ = sum of left side, \$S_T\$ = total sum, \$A[i]\$ = the current element

$$S_R = S_T - S_L - A[i]$$ $$S_L = S_T - S_R - A[i]$$

So, simply use sums alongside the following algorithm, which has actually been supplied by Codility in their Equi blog post, you'll be able to achieve \$O(n)\$:

long long sum_left = 0;    
for(i=0;i<n;i++) {
    long long sum_right = sum - sum_left - (long long) arr[i];
    if (sum_left == sum_right) return i;
    sum_left += (long long) arr[i];
}

One major downside:

JavaScript is not made to handle the long or long long types, so arrays with larger sums will not be able to handle this as well.

This is a language feature; however third party libraries can supply the type, if you so wish. See this Stack Overflow answer for more information on the subject.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the extensive answer I will check it more carefully, but: you mentioned for(var i = 0, length = A.length; i < length; i++){, I heard its bad to put the var into the for loop because it wastes the CPU...also....always cehcking the length of the array in every iteration is baaaad...why simply not store the length in one variable. This way we dont need to recalculate the array length each time? \$\endgroup\$
    – mirzahat
    Oct 21, 2015 at 13:41
  • \$\begingroup\$ Actually, declaring the variable in the loop is better because the variable is deallocated after the loop is processed, and the length isn't checked every time the loop is processed, that's why the length variable is assigned before the first loop. \$\endgroup\$
    – Quill
    Oct 21, 2015 at 13:45
  • \$\begingroup\$ @mirzahat, you should definitely not be thinking about micro-optimizations like that. Additionally, where you put the var in js won't matter -- it gets hoisted to the top of the function anyway. If you really want to test this stuff (and again, this should be low on your priority list), you can do so here: jsperf.com. You should be able to prove to yourself that these things optimizations have little to no effect. \$\endgroup\$
    – Jonah
    Oct 21, 2015 at 13:47
0
\$\begingroup\$

Quill's answer does a good job explaining the performance problems of your approach.

I thought I'd add a working javascript solution that is fairly concise, with explanations inline as comments. Note that this function returns an array of all equilibrium indexes, or the empty array if none are found:

function eqIndexes(arr) {
    // start the right hand sum as the sum of the whole array
    var rightSum = arr.reduce(function(m,c) { return m+c }, 0),
        leftSum = 0,
        isEndPoint;

    // Here we use reduce to build up an array of all
    // indexes which have an equilibrium
    return arr.reduce(function(answer,cur,i) {
        rightSum -= cur;
        isEndPoint = i == 0 || i == arr.size -1
        // If we're at the beginning or the end of the array,
        // just return the answer we already have.  This will 
        // be the empty array we started with when i == 0, and 
        // it will be our final answer when we're at the last elm.
        if (isEndPoint) return answer;

        leftSum += arr[i-1];
        if (leftSum == rightSum) answer.push(i);
        return answer;
    },[]);
}
\$\endgroup\$
4
  • \$\begingroup\$ thanks, please check the commend on Quills answer...what do you think? \$\endgroup\$
    – mirzahat
    Oct 21, 2015 at 13:42
  • \$\begingroup\$ I replied there. I'll add here that focusing on algorithm correctness, big-O performance, and readability of your code is far more important than those things. \$\endgroup\$
    – Jonah
    Oct 21, 2015 at 13:49
  • \$\begingroup\$ what is a big-O performance? \$\endgroup\$
    – mirzahat
    Oct 22, 2015 at 5:44
  • \$\begingroup\$ A central (perhaps the central) concept in algorithm analysis. This video from Skiena, the author of The Algorithm Design Manual, is a good slow-paced intro: youtube.com/watch?v=gSyDMtdPNpU. But you can find tons of other resources on google, too. \$\endgroup\$
    – Jonah
    Oct 22, 2015 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.