Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer
    
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? – mirzahat Oct 21 '15 at 13:41
    
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. – Quill Oct 21 '15 at 13:45
    
@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. – Jonah Oct 21 '15 at 13:47

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;
    },[]);
}
share|improve this answer
    
thanks, please check the commend on Quills answer...what do you think? – mirzahat Oct 21 '15 at 13:42
    
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. – Jonah Oct 21 '15 at 13:49
    
what is a big-O performance? – mirzahat Oct 22 '15 at 5:44
    
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. – Jonah Oct 22 '15 at 14:24

Just my 2 cents. I got the pseudocode for this from http://www.geeksforgeeks.org/equilibrium-index-of-an-array/.

The concept is to first get the total sum of the array, then run a loop. For each iteration of the loop, we first subtract the element at that index from the total sum (or right sum), then we compare with the value of the left sum. If there's a match we push that index position onto an output array. If no match, we increment the left sum by the value of the array element at the current index and run the loop again.

Of course we test for edge cases where the input array is a null array or single element array. The following solution whic followed the concept above scored 100%.

function equil(A) {
  var
    output = [],
    len = A.length,
    i;
  if(A.length === 0) {
    return -1;
  }
  if(A.length === 1) {
    return 0;
  }
  var
    rSum = A.reduce(function (i,j) {
      return i + j;
    }),
    lSum = 0;
  for(i = 0; i < len; i++) {
    rSum -= A[i];
    if(lSum === rSum) {
      output.push(i)
    }
    lSum += A[i];
  }
  if(output.length === 0) {
    return -1
  }
  return output[0];
}

My initial 'naive attempt' scored 54% i believe...

function solution(A) {
    // write your code in JavaScript (Node.js 4.0.0)
  if(A.length === 0) {
    return -1;
  }
  if(A.length === 1) {
    return 0;
  }
  else {
      var raw = A.map(function (el, indx, arr) {
        var
          sumL = 0,
          sumH = 0,
          len = arr.length,
          candidate = arr[indx];
        for(i = 0; i < indx; i++) {
          sumL += arr[i];
        }
        for(i = (indx + 1); i < len; i++) {
          sumH += arr[i];
        }
        if(sumL === sumH) {
          return indx;
        }
      }).filter(function (el) {
          return el;
        });
      if(raw.length === 0) {
        return -1;
      }
    return raw[0];
  }
}
share|improve this answer
1  
This code doesn't appear to review the code given in the question. – Mast Nov 30 '15 at 9:17
1  
Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. – SuperBiasedMan Nov 30 '15 at 9:22
    
"Just my 2 cents" is not a code review. An alternative solution can be acceptable if you can contrast it with the code in the question. Explain what the original is doing wrong. Highlight the specific points where your alternative is better. If you don't want to do that, then it would be better to delete this. (As it stands, your answer would be better as a question, subject to code review.) – janos Nov 30 '15 at 9:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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