This post aim is to provide Codility algorithm solutions in JavaScript as there are so many of them 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.
I created this article to prepare for Toptal interview process. If you wish to apply to Toptal, here is a referral link that will link your account to mine if you are successful!
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.
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 https://codility.com/media/train/7-MaxSlice.pdf
MaxProfit
Difficulty: PAINLESS
Given a log of stock prices compute the maximum possible earning.
https://codility.com/demo/take-sample-test/max_profit/
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).