codility-lesson-2-arrays.md

OddOccurrencesInArray

Algorithmic solution

function solution(A) {
    const oddValues = A.reduce((acc, a) => {
        if (acc.has(a)) {
            acc.delete(a)
        } else {
            acc.set(a, a)
        }
        return acc
    }, new Map)
    
    return oddValues.values().next().value
}

Mathematical solution

// 5 ^ 7 ^ 3 ^ 5 ^ 7 = 3
function solution(A) {
    return A.reduce((result, value) => result ^ value, 0)
}

CyclicRotation

function shiftOnce(A) {
    const result = []
    const len = A.length
    
    for (let i = 1; i <= len; i++) {
        if (i === 1) {
            // move latest item to the first place
            result[0] = A[len - 1]
        } else {
            // shift other items to the right
            result[len - i + 1] = A[len - i]
        }
    }
    
    return result
}

function solution(A, K) {
    let result = A

    for (let i = 0; i < K; i++) {
        result = shiftOnce(result)
    }
    
    return result
}

codility-lesson-3-time-complexity.md

FrogJmp

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

PermMissingElem

Mathematical solution

function solution(A) {
    const maxValue = A.length + 1
    //     1,       2,      3, ..., n - 1,       n
    //     n,   n - 1,  n - 2, ...,     2,       1
    // n + 1,   n + 1,  n + 1, ..., n + 1,   n + 1
    // n * (n + 1) / 2
    const expectedSumOfValues = maxValue * (maxValue + 1) / 2
    const sumOfValues = A.reduce((sum, value) => sum + value, 0)
    const missedValue = expectedSumOfValues - sumOfValues
    return missedValue
}

TapeEquilibrium

function solution(A) {
    const sum = A.reduce((sum, value) => sum + value, 0)
    let sum1 = A[0]
    let sum2 = sum - A[0]
    let minDiff = Math.abs(sum2 - sum1)
    
    // Each sum have to have at least one element
    // that is why we protect latest element of array
    for (let i = 1; i < A.length - 1; i++) {
        sum1 += A[i]
        sum2 -= A[i]
        const diff = Math.abs(sum2 - sum1)
        if (diff < minDiff) {
            minDiff = diff
        }
    }
    return minDiff
}

codility-lesson-4-counting-elements.md

PermCheck

function solution(A) {
    let maxValue = A[0]
    let sum = 0
    let count = []
    
    for (let i = 0; i < A.length; i++) {
        const value = A[i]
        
        // Exit function if some of the values
        // occurs more than once
        if (count[value]) {
            return 0
        } else {
            count[value] = 1
        }
        
        // Find max value in array
        if (value > maxValue) {
            maxValue = value
        }
        
        // Compute sum of all elements of array
        sum += value
    }
    
    const expectedSum = maxValue * (maxValue + 1) / 2
    if (sum !== expectedSum) {
        return 0
    }
    
    return 1
}

FrogRiverOne

function solution(X, A) {
    const filledPositions = []
    let counter = X
    
    for (let i = 0; i < A.length; i++) {
        const position = A[i]
        
        if (filledPositions[position]) {
            continue
        } else {
            filledPositions[position] = true
            counter--
        }
        
        if (counter === 0) {
            return i
        }
    }
    
    return -1
}

MissingInteger

function solution(A) {
    const count = [0]
    
    for (let i = 0; i < A.length; i++) {
        const value = A[i]
        
        if (value <= 0 || count[value]) {
            continue
        } else {
            count[value] = value
        }
    }
    
    for (let i = 1; i < count.length; i++) {
        if (!count[i]) {
            return i
        }
    }
    
    return count.length
}

MaxCounters

function solution(N, A) {
    const {counters, minValue} = A.reduce((acc, a) => {
        let { counters, minValue, maxValue } = acc
        
        if (counters[a - 1] < minValue) {
            counters[a - 1] = minValue
        }
        
        if (a <= N) {
            counters[a - 1] = counters[a - 1] + 1
        } else {
            minValue = maxValue
        }
        
        if (counters[a - 1] > maxValue) {
            maxValue = counters[a - 1]
        }
        
        return { counters, minValue, maxValue}
    }, { counters: new Array(N).fill(0), minValue: 0, maxValue: 0 })
    
    return counters.map(c => c < minValue ? minValue : c)
}

codility-lesson-5-prefix-sums.md

PassingCars

const EAST_CAR = 0
const WEST_CAR = 1

function solution(A) {
    const computations = A.reduce((acc, car) => {
        let { cars, pairs, state } = acc
        
        if (pairs === -1 || pairs > 1000000000) {
            return { pairs: -1 }
        }
        
        switch (state) {
            case 'initial':
                if (car === EAST_CAR) {
                    return { ...acc, cars: ++cars, state: 'east' }
                } else {
                    return acc
                }
            case 'east': 
                if (car === EAST_CAR) {
                    return { ...acc, cars: ++cars }
                } else {
                    return { ...acc, pairs: pairs + cars, state: 'west' }
                }
            case 'west':
                if (car === WEST_CAR) {
                    return { ...acc, pairs: pairs + cars }
                } else {
                    return { ...acc, cars: ++cars, state: 'east' }
                }
        }
    }, { cars: 0, pairs: 0, state: 'initial' })
    
    return computations.pairs
}

GenomicRangeQuery

const FACTORS = {
    A: 1,
    C: 2,
    G: 3,
    T: 4
}

function solution(S, P, Q) {
    const prefixSums = [...S].reduce((acc, s, idx) => {
        acc.A[idx + 1] = acc.A[idx] || 0
        acc.C[idx + 1] = acc.C[idx] || 0
        acc.G[idx + 1] = acc.G[idx] || 0
        
        if (['A', 'C', 'G'].includes(s)) {
            acc[s][idx + 1]++
        }
        
        return acc
    }, { A: [0], C: [0], G: [0] })
    
    return P.reduce((result, p, idx) => {
        const q = Q[idx]
        const nucleotide = ['A', 'C', 'G'].find(s => (prefixSums[s][q + 1] - prefixSums[s][p]) > 0)
        result[idx] = nucleotide ? FACTORS[nucleotide] : FACTORS.T
        
        return result
    }, [])
}

MinAvgTwoSlice

// THIS SOLUTION PASSES THE TESTS ONLY
function solution(A) {
    let result = 0
    let minAvg = Number.MAX_VALUE
    
    for (let i = 0; i < A.length - 1; i++) {
        const avg2 = (A[i] + A[i + 1]) / 2
        const avg3 = i === A.length - 2 ? avg2 : (A[i] + A[i + 1] + A[i + 2]) / 3
        const avg = Math.min(avg2, avg3)
        if (avg < minAvg) {
            minAvg = avg
            result = i
        }
    }
    
    return result
}

CountDiv

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

codility-lesson-6-sorting.md

Distinct

function solution(A) {
    let counter = 0
    
    A.reduce((acc, value) => {
        if (acc[value]) {
            return acc
        }
        
        counter++
        acc[value] = true
        return acc
    }, [])

    return counter
}

MaxProductOfThree

function solution(A) {
    const N = A.length
    A.sort((a, b) => a - b)
    const maxValue = A[N - 1]
    const firstTwo = A[0] * A[1]
    const lastTwo = A[N - 2] * A[N - 3]
    
    if (maxValue < 0) {
        return lastTwo * maxValue
    }
    
    if (firstTwo > lastTwo) {
        return firstTwo * maxValue
    } else {
        return lastTwo * maxValue
    }
}

Triangle

function solution(A) {
    // sort descending
    A.sort((a, b) => b - a)
    
    for (let i = 0; i < A.length - 2; i++) {
        if (A[i] < (A[i + 1] + A[i + 2])) {
            return 1
        }
    }
    
    return 0
}

NumberOfDiscIntersections

function solution(A) {
    const N = A.length
    const starts = []
    const ends = []
    
    if (N < 2) {
        return 0
    }
    
    A.forEach((r, idx) => {
        starts.push(idx - r)
        ends.push(idx + r)
    })
    
    starts.sort((a, b) => a - b)
    ends.sort((a, b) => a - b)

    let intersections = 0
    let circles = 0
    let j = 0
    
    for (let i = 0; i < N; i++) {
        while (j < N && starts[j] <= ends[i]) {
            circles++
            j++
        }
        intersections += --circles
        
        if (intersections > 10000000) {
            return -1
        }
    }
    
    return intersections
}

codility-lesson-7-stacks-and-queues.md

Brackets

const PAIRS = {
    ']': '[',
    '}': '{',
    ')': '('
}

const OPENS = Object.values(PAIRS)

function solution(S) {
    const seq = [...S]
    const queue = []

    for (let i = 0; i < seq.length; i++) {
        if (OPENS.includes(seq[i])) {
            queue.push(seq[i])
            continue
        }
        
        if (queue.pop() !== PAIRS[seq[i]]) {
            return 0
        }
    }
    
    if (queue.length > 0) {
        return 0
    }
    
    return 1
}