Skip to content

Instantly share code, notes, and snippets.

@eriksjaastad
Last active October 4, 2015 00:41
Show Gist options
  • Save eriksjaastad/ae9f95a9fa5a44c11ddd to your computer and use it in GitHub Desktop.
Save eriksjaastad/ae9f95a9fa5a44c11ddd to your computer and use it in GitHub Desktop.
Codility algorithm solutions in JavaScript with better examples of the questions

###Time Complexity O(1) is constant time, no matter how much data there is, it will take the same amount of time to find the answer
O(log n) is cutting the search area in half each time
O(n) is looping through each item once
O(n2) is looping through twice
0(nn) is looping through each value and having to do something with each value based on how many values came before it
####TapeEquilibrium rewrite
A is an Array = [3,1,2,4,3]
N is the length of A
P is any integer between 0 and N
The total sum of A is 13
If P is 1, then P is the first index in the array and is equal to 3

Example solution

function solution(A) {
    var sumAfter = 0;
    var sumBefore = 0;
    //sets the number to positive
    var minDiff = Number.POSITIVE_INFINITY;
    //add up the numbers in the array
    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;
}

####FrogJmp

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

####PermMissingElem

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

###Counting Elements ####FrogRiverOne

function solution(X, A) {
    var count = {};
    var countI = 0;
    var index = 0;
    for(var i = 0; i < A.length; i++) {
        index = A[i] -1;
        if(A[i] <= X && !count[index]) {
            count[index] = true;
            countI++;
            if(countI === X) return i;
        }
    }
    return -1;
}

####PermCheck

function solution(A) {
    var sum = 0;
    var numbers = {};
    for(var i = 0; i < A.length; i++) {
        var a = A[i];
        sum += a;
        if(numbers[a] === 1) {
            return 0;
        } else {
            numbers[a] = 1;
        }
    }
    var n = A.length;
    var sum_n = (n * (n + 1)) / 2;
    var difference = sum_n - sum;
    if(difference !== 0) return 0;
    return 1;
}

####MissingInteger

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

####MaxCounters time complexity: O(N + M)

// N number of counters
// function increase(X) increases a counter by 1
// function max_counter all counters are set to maximum value of one counter
// A is a 0 indexted array
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N, A) {
//set len to array length
    var len = A.length;
//set lastBase to 0
    var lastBase = 0;
//set max to 0
    var max = 0;
//make an empty array for counters
    var counters = [];
//n1 is the number or counters plus 1
    var n1 = N+1;
//set i to 0 and increment i by 1 untill it's 1 less than the number of counters
    for(var i = 0; i < N; i++){
//counters array looks like counters[0] = 0 at the beginning
        counters[i] = 0;
    }
//set i back to 0, increment i by 1 untill it's 1 less than the array length
    for(i = 0; i < len; i++){
//if Array at index i is less than the number of counters +1
        if(A[i] < n1){
//if counters array index at Array index i -1 is less than lastBase(which starts at 0)
            if(counters[A[i]-1] < lastBase) {
//counters array index is set to the value of lastBase
                counters[A[i]-1] = lastBase;
            }
//if counters array index is greater than lastBase value, counters array index is incremented by 1
            counters[A[i]-1] += 1;
//if max is less than the counters array index
            if(max < counters[A[i]-1]) {
//max is set to the value of the counters array index
                max = counters[A[i]-1];
            }
        } else {
//if Array at index i is greater than the number of counters +1 lastBase is set to the value of max
            lastBase = max;
        }
    }
//i is set to 0 and incremented by one untill i is equal to the number of counters
    for(i = 0; i < N; i++){
//if counters index is less than lastBase
        if(counters[i] < lastBase) {
//counters indext is set to the value of lastBase
            counters[i] = lastBase;
        }
    }
    return counters;
}

####Find Digits

input:
2
12
1012
expected output: 
2
3

solution

function processData(input) {
    var a = input.split('\n'); // returns ['2', '12', '1012']
    var b = a.map(Number); // returns [2, 12, 1012]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment