Codility efficient algorithm solutions in JavaScript

This post aim is to provide Codility algorithm solutions in JavaScript as there are so many of then available out there. I am not pretending to have the best algorithm possible but at least the following answers scored 100% on Codility test result.

After reading the task description a wise thing to do is to check the expected worst case time complexity. It gives you a hint on how to apprehend the solution. For instance if the worst case time complexity is O(N), you would probably need to use a for loop, if it is O(N*M) a nested for loop might be necessary etc.

big_o

This post in on going, I am adding new solutions often.

Lesson 1: Time Complexity

FrogJmp

Difficulty: PAINLESS

Count minimal number of jumps from position X to Y.

https://codility.com/demo/take-sample-test/frog_jmp

Expected time complexity: worst-case is O(1)

function solution(X, Y, D) {
    return Math.ceil((Y - X)/ D);
}

PermMissingElem

Difficulty: PAINLESS

Find the missing element in a given permutation.

https://codility.com/demo/take-sample-test/perm_missing_elem

Expected time complexity: worst-case is O(N)

function solution(A) {
    var length = A.length;
    var sum = ((length + 1) /2) * (length + 2);
    var sumMinusMissing = 0;
    for (i = 0; i < length; i++) { 
        sumMinusMissing += A[i];
    }
    return sum - sumMinusMissing;
}

TapeEquilibrium

Difficulty: PAINLESSS

Minimize the value |(A[0] + … + A[P-1]) – (A[P] + … + A[N-1])|

https://codility.com/demo/take-sample-test/tape_equilibrium

Expected time complexity: worst-case is O(N)

function solution(A) {
    var sumAfter = sumBefore = 0;
    var minDiff = Number.POSITIVE_INFINITY;
    
    A.forEach(function(value){
        sumAfter += value;
    });
    
    for (var i = 1; i < A.length; i++){
        sumBefore += A[i -1];
        sumAfter = sumAfter - A[i -1];
        minDiffTemp = Math.abs(sumBefore - sumAfter);
        if (minDiffTemp < minDiff){
            minDiff = minDiffTemp;
        }
    }
    return minDiff;
}

Lesson 2: Counting Elements

MaxCounters

Difficulty: RESPECTETABLE

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

https://codility.com/demo/take-sample-test/max_counters

Expected time complexity: worst-case is O(N+M)

function solution(N, A) {
    var counters = [], 
    size = N, 
    max = 0,
    forValue = 0,
    counter = 0,
    lastUpdate = 0;
    // init zeros
    for (var i = 0; i < N; i++){
        counters[i] = 0;
    }
    
    for (var i = 0; i < A.length; i++){
        if (A[i] <= N){
            position = A[i] -1;
            if (counters[position] < lastUpdate){
                counters[position] = lastUpdate + 1;
            } else {
                counters[position] = counters[position]+1;
            }
            if (counters[position] > max) {
                max = counters[position];
            }
        } else {
            lastUpdate = max;
        }
    }
    
    for (var i = 0; i < N; i++){
        if (counters[i] < lastUpdate)
            counters[i] = lastUpdate;
    }
    
    return counters;
}

MissingInteger

Difficulty: RESPECTETABLE

Find the minimal positive integer not occurring in a given sequence.

https://codility.com/demo/take-sample-test/missing_integer

Expected time complexity: worst-case is O(N)

function solution(A) {
    var onlyPositiveInt = [];
    for (var i =0; i < A.length; i++){
        if (A[i] > 0 ){
            onlyPositiveInt[A[i]] = true;
        }
    }
    for (i = 1; i <= onlyPositiveInt.length; i++){
        if (!onlyPositiveInt[i]){
            return i;
        }
    }
    return 1;
}

Lesson 3: Prefix Sums

In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers x0, x1, x2, … is a second sequence of numbers y0, y1, y2, …, the sums of prefixes (running totals) of the input sequence

http://en.wikipedia.org/wiki/Prefix_sum

Material https://codility.com/media/train/3-PrefixSums.pdf

PassingCars

Difficulty: PAINLESS

Count the number of passing cars on the road.

https://codility.com/demo/take-sample-test/passing_cars

Expected time complexity: worst-case is O(N)

function solution(A) {
    var ones = 0, passing = 0;
    for(var i=A.length-1; i>=0; i--) {
	    if (A[i] === 0){
	        passing += ones;
	        if (passing > 1000000000){
	            return -1;
	        }
	    } else {
	       ones ++;
	    }
    }
    return passing;
}

CountDiv

Difficulty: RESPECTETABLE

Compute number of integers divisible by k in range [a..b].

https://codility.com/demo/take-sample-test/count_div

For this one your coding skills won’t help. It is a pure math problem.

Expected time complexity: worst-case is O(1)

function solution(A, B, K) {
    if (A % K === 0)
        return Math.floor((B - A) / K + 1);
    return Math.floor((B - (A - (A % K) )) / K)
}

MinAvgTwoSlice

Difficulty: RESPECTETABLE

Find the minimal average of any slice containing at least two elements.

https://codility.com/demo/take-sample-test/min_avg_two_slice

Expected time complexity: worst-case is O(N)

Still searching for this one. If you have a 100% solution please share 🙂

GenomicRangeQuery

Difficulty: RESPECTETABLE

Find the minimal nucleotide from a range of sequence DNA.

https://codility.com/demo/take-sample-test/genomic_range_query

Expected time complexity: worst-case is O(N+M)

function solution(S, P, Q) {
    var positionOne,
    positionTwo,
    factorPerType = {
        "A":1,
        "C":2,
        "G":3,
        "T":4
    },
    prefix = [[0,0,0,0]],
    Plen = P.length,
    Slen = S.length,
    result =[],
    counterType = [0,0,0,0];

    for(var i = 0; i<Slen; i++) {
        counterType = counterType.concat(); // local copy
        counterType[factorPerType[S[i]] -1]++;
        prefix.push(counterType);
    }
    
    for(i=0; i<Plen; i++) {
	    positionOne = P[i] + 1;
	    positionTwo = Q[i]+ 1;

	    var finalCount =0;
	    for (j = 0; j < 4; j++){
	        finalCount = prefix[positionTwo][j] - prefix[positionOne -1][j];
	        if (finalCount > 0){
	            result.push(j + 1);
	            break;
	        }
	    }
    }
 
    return result;
}

Lesson 4: Sorting

MaxProductOfThree

Difficulty: PAINLESS

Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

https://codility.com/demo/take-sample-test/max_product_of_three

Expected time complexity: worst-case is O(N*log(N))

function solution(A) {
    var N = A.length;

    // Sort ascending
    A.sort(function(a, b){
        return a - b;
    });
    // the max product of three elements is the product of the last three
    // elements in the sorted array or the product of the first two elements
    // and the last element if the first two elements are negatives.    
    return Math.max(A[0] * A[1] * A[N-1], A[N-3] * A[N-2] * A[N-1]);
}

Distinct

Difficulty: PAINLESS

Compute number of distinct values in an array.

https://codility.com/demo/take-sample-test/distinct

Expected time complexity: worst-case is O(N*log(N))

function solution(A) {
    var leng = A.length, counter = 0;

    // Sort ascending
    A.sort(function(a, b){
        return a - b;    
    });
    
    for (var i=1; i <= leng; i++){
        if (A[i] != A[i - 1]){
            counter++;   
        }
    }
    
    return counter;
}

Triangle

Difficulty: PAINLESS

Determine whether a triangle can be built from a given set of edges.

https://codility.com/demo/take-sample-test/triangle

Expected time complexity: worst-case is O(N*log(N))

function solution(A) {
    var len = A.length;
    
    // Sort descending
    A.sort(function(a, b){
        return b - a; 
    });
    
    for(var i=0; i<len - 2; i++) {
        var P = i, Q= i+1, R= i+2;
        var condition1 = A[P] + A[Q] > A[R];
        var condition2 = A[Q] + A[R] > A[P];
        var condition3 = A[R] + A[P] > A[Q];
        if (condition1 && condition2 && condition3){
            return 1;
        }
    }
    return 0;
}

NumberOfDiscIntersections

Difficulty: RESPECTETABLE

Compute intersections between sequence of discs.

https://codility.com/demo/take-sample-test/number_of_disc_intersections/

Expected worst-case time complexity is O(N*log(N));

function solution(A) {
    var len =  A.length,
    tupples = [],
    count =0;
    
    for (var i=0; i < len; i++){
        tupples.push([i - A[i], i + A[i]]);  
    }
    
    // [[5,5], [0,4], [-4, 6]] => [[-4, 6], [0,4], [5,5]]
    tupples.sort(function(a,b){
        return a[0] - b[0];
    });

    for (var j=0; j < len; j++){
        var tupple = tupples[j];
        for (var k=j+1; k < len; k++){
            var comparisonTupple = tupples[k];
            if (comparisonTupple[0] <= tupple[1]){
                count++;
                if (count >10000000){
                    return -1;    
                }
            } else {
                break;    
            }
        } 
    }
    return count;
}

Lesson 5: Stacks and Queues

Brackets

Difficulty: PAINLESS

Determine whether given string of parentheses is properly nested.

https://codility.com/demo/take-sample-test/brackets/

Expected worst-case time complexity is O(N)

function solution(S) {
    var len = S.length;
    
    if (!len){
        return 1;
    }
    
    var stack = [],
    matches = {
        "{" : "}",  
        "(" : ")", 
        "[" : "]"   
    };
    
    for (i=0; i < len; i++){
        var currentCharacter = S[i];
        if (matches[currentCharacter]){
            stack.push(currentCharacter);
        } else {
            if (!stack.length){
                return 0;
            }   
            var previousCharacter = stack.pop();
            if (matches[previousCharacter] !== currentCharacter){
                return 0;
            }   
        }   
    }        
    
    return (stack.length)? 0 : 1;
}

Nesting

Difficulty: PAINLESS

Determine whether given string of parentheses is properly nested.

https://codility.com/demo/take-sample-test/nesting/

Expected worst-case time complexity is O(N)

function solution(S) {
    var len = S.length;
    
    if (!len){
        return 1;
    }
    
    var stack = [],
    matches = {
        "(" : ")" 
    };
    
    for (i=0; i < len; i++){
        var currentCharacter = S[i];
        if (matches[currentCharacter]){
            stack.push(currentCharacter);
        } else {
            if (!stack.length){
                return 0;
            }   
            var previousCharacter = stack.pop();
            if (matches[previousCharacter] !== currentCharacter){
                return 0;
            }   
        }   
    }        
    
    return (stack.length)? 0 : 1;
}

Fish

Difficulty: PAINLESS

N voracious fish are moving along a river. Calculate how many fish are alive.

https://codility.com/demo/take-sample-test/fish/

Expected worst-case time complexity is O(N)

function solution(A, B) {
    var len = A.length,
    count = parseInt(len),
    stackDownstreamFishes = [];
    
    for (var i = 0; i < len; i++){
        var direction = B[i] ? 'downstream' : 'upstream';
        if (direction === 'downstream'){
            stackDownstreamFishes.push(A[i]);    
        } else {            
            // Going backward through all downstream fishes
            for(var j= stackDownstreamFishes.length-1; j>=0; j--) {
                var lastDownstreamFishSize = stackDownstreamFishes[j];
                if (lastDownstreamFishSize > A[i]){
                    count--;
                    break;
                } else if (lastDownstreamFishSize < A[i]){
                    count--;
                    stackDownstreamFishes.pop();
                }
            }
        }
    }
    return count;
}

StoneWall

Difficulty: PAINLESS

Cover “Manhattan skyline” using the minimum number of rectangles.

https://codility.com/demo/take-sample-test/stone_wall/

Expected worst-case time complexity is O(N)

function solution(H) {
    var len = H.length,
        stack = [H[0]],
        result = 1;
    if (!len) {
        return 0;
    }
    for (var i = 1; i < len; i++) {
        var currentHeight = H[i];
        while (stack.length && stack[stack.length - 1] >= currentHeight) {
            if (currentHeight == stack[stack.length - 1]) {
                result--;
            }
            stack.pop();
        }
        stack.push(currentHeight);
        result++;
    }
    return result;
}

I started with a backward for loop:

for (var j = stack.length - 1; j >= 0; j--) {
    if (stack[j] < currentHeight) {
        break;
    }
    if (stack[j] == currentHeight) {
        result--;
    }
    stack.pop();
}

But a while loop is faster: https://jsperf.com/compare-while-loop-vs-for-loop/4


Lesson 6: Leader

Material https://codility.com/media/train/6-Leader.pdf

EquiLeader

Difficulty: PAINLESS

Find the index S such that the leaders of the sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N – 1] are the same.

https://codility.com/demo/take-sample-test/equi_leader/

Expected worst-case time complexity is O(N)

function solution(A) {
    var len = A.length,
        i = 0,
        j = 0,
        k = 0,
        size = 0,
        indexCount = 0,
        candidateCount = 0,
        leader,
        leaderCount = 0,
        candidate = null;

    // First find the leader within A
    for (; i < len; i++) {
        if (size === 0) {
            size++;
            candidate = A[i];
        } else {
            (candidate === A[i]) ? size++ : size--;
        }
    }

    for (; j < len; j++) {
        if (A[j] === candidate) {
            candidateCount++;
        }
    }

    if (candidateCount <= len / 2) { // Our candidate failed 🙁
        return 0;
    } else { // we have a winner!
        leader = candidate;
        leaderCount = candidateCount;
    }

    var leaderLeftCount = 0;
    for (; k < len - 1; k++) {
        var lenLeft = (k + 1);
        var lenRight = len - lenLeft;
        if (A[k] === leader) {
            leaderCount--;
            leaderLeftCount++;
        }
        if (leaderLeftCount > (lenLeft / 2) && leaderCount > (lenRight / 2)) {
            indexCount++;
        }
    }
    return indexCount;
}

Dominator

Difficulty: PAINLESS

Find an index of an array such that its value occurs at more than half of indices in the array.

https://codility.com/demo/take-sample-test/dominator/

Expected worst-case time complexity is O(N)

function solution(A) {
    var len = A.length,
    i = 0,
    j = 0,
    leaderCount = 0,
    latestIndex = -1,
    size = 0,
    candidate = null,
    value = null;
    
    for (; i < len; i++){
        if (size === 0){
            size++;
            value = A[i];
        } else {
            value !== A[i] ?  size-- : size++;
        }
    }
    
    candidate = value;
    for (; j < len; j++){
        if (candidate === A[j]){
            leaderCount++;
        }
        if (leaderCount > len / 2){
            latestIndex = j;
            break;
        }
    }
    return latestIndex;
}

## Lesson 7: Maximum slice problem

Material

### MaxProfit

Difficulty: PAINLESS

Given a log of stock prices compute the maximum possible earning.

Expected worst-case time complexity is O(N)

At first I could not find a better solution the following:

function solution(A) {
    var len = A.length,
    i= len-1,
    max = 0;
    
    for(; i>=0; i--) {
    	var stockShare = A[i];
    	for(j = i-1; j>=0; j--) {
    	   var diff = stockShare - A[j];
    	   if (diff > max){
    	       max = diff;
    	   }
    	}
    }
    return max;
}

The time complexity is quadratic O(N^2) which is terrible.

Then I spent a little more time thinking about it and I ended up writing the following which has the correct time complexity: O(N).


Changing apache2 document root in ubuntu 14.x

Having the default Apache document root to /etc/www can be sometimes annoying because of permissions. I strongly recommend to use a folder into your home folder.

For the sake of this post, I will use the folder Sites (that I created under my personal folder /home/shprink/Sites/).

PS: The Apache version used for this post is: 2.4.10 (Ubuntu), you can see yours using apache2 -v command.

Changing apache2 document root

The default document root is set in the 000-default.conf file that is under /etc/apache2/sites-available folder.

$ cd /etc/apache2/sites-available
$ sudo nano 000-default.conf

While the file is opened change DocumentRoot /var/www/ with your new folder e.g DocumentRoot /home/shprink/Sites/

Set the right Apache configuration

The configuration of the /etc/www folder is under /etc/apache2/apache2.conf. Edit this file to add the configuration of your new document root.

$ sudo nano /etc/apache2/apache2.conf

Copy the following:

<Directory /var/www/>
       Options Indexes FollowSymLinks
       AllowOverride None
       Require all granted
</Directory>

and change the directory path:

<Directory /home/shprink/Sites/>
       Options Indexes FollowSymLinks
       AllowOverride None
       Require all granted
</Directory>

Restart Apache

$ sudo service apache2 restart

Set the right permission

All of your document root parent folders must be executable by everyone. To know if it is the case you can use the utility namei that list the permissions along each component of the path:

$ namei -m /home/shprink/Sites/
f: /home/shprink/Sites/
 drwxr-xr-x /
 drwxr-xr-x home
 drwx------ shprink
 drwx------ Sites

Here as you can see that shprink and Sites permissions are not set properly.

Open http://localhost/ in your browser, you should get the following message:

Forbidden
You don’t have permission to access / on this server.

Open the apache error log to see the exact error code e.g AH00035. It might help you to get more information.

$ sudo tail -f /var/log/apache2/error.log
[Mon Apr 06 09:04:26.518260 2015] [core:error] [pid 22139] (13)Permission denied: [client 127.0.0.1:45121] AH00035: access to / denied (filesystem path '/home/shprink/Sites') because search permissions are missing on a component of the path

To fix the permission problem for good, using chmod +755 should be enough.

$ chmod +755 /home/shprink/
$ chmod +755 /home/shprink/Sites/

Re run namei to make sure everything is ok.

$ namei -m ~/Sites/
f: /home/shprink/Sites/
 drwxr-xr-x /
 drwxr-xr-x home
 drwxr-xr-x shprink
 drwxr-xr-x Sites

Now opening http://localhost/ should work as expected. If you are having trouble please leave a comment.