Handy Formulas and Algorithms

formulas.js

// Calculate Triangle Possibility From Edges
// given a set of edges from 0 to N calculate if we can make at least one triangle from them
function triangleFromLengths(a) {
  
  // the trick here is to sort the edges into ascending order
  // given a = [10, 2, 5, 1, 8, 20], when sorted, we get [1, 2, 5, 8, 10, 20]
  // ascending order guarantees that every value that suceedes another is either the same size or greater (A[0] <= A[1])
  // this means that if the sum of any two edges preceeding a third is greater than that third (i.e. if 5 + 8 > 10)
  // the triangle inequality theorem will hold true: https://www.wikihow.com/Determine-if-Three-Side-Lengths-Are-a-Triangle
  // since: 5 + 8 > 10 && 8 + 10 > 5 && 5 + 10 > 8
  // ascending order means we can skip the remaining inequality checks since if the smallest two variable sum is greater
  // than the value that succeeds them, any summation of any two values of said triplet MUST be greater than the remaining value
  a.sort();

    for (let i = 0; i < a.length - 2; i++) {
        let P = a[i];
        let Q = a[i+1];
        let R = a[i+2];
        
        if (P >= 0 && P + Q > R) return 1;
    }
  
    return 0;
}

// Codility Brackets Task (Stacks and Queues): https://app.codility.com/demo/results/training69YJH3-HTF/
// A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
//
//        S is empty;
//        S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
//        S has the form "VW" where V and W are properly nested strings.
//
// For example, the string "{[()()]}" is properly nested but "([)()]" is not.

function solution(S) {
    // S is a string that can be properly nested or not
    // S can only consist of (), [], and {} characters
    // S can be between 0 and 200,000 chars long

    // handle empty and 1 length string
    if (S.length <= 1) return 1;
    
    // for every opening bracket, we require a closing bracket of the same type
    // for every properly nested string, only properly nested strings can exist within them

    let temp = [];
    let char = '';

    const isClosingChar = char => ')}]'.includes(char);

    const isCloserMatching = (opener, closer) => {
        if (opener === '(' && closer === ')') return true;
        if (opener === '[' && closer === ']') return true;
        if (opener === '{' && closer === '}') return true;
    }

    // every time we get a closing bracket, we need to check  if the preceding character matches the closing type
    // we also need to handle cases where we have only openers!!

    for (let i = 0; i < S.length; i++) {
        char = S[i];

        if (isClosingChar(char)) {
            if (isCloserMatching(temp[temp.length-1], char)) temp.pop();
            else return 0;
        } else {
            temp.push(char);
        }
    }

    // the only way temp will be populated is if an opener has not met a closer
    if (temp.length > 0) return 0;

    return 1;
}


// Sum Natural Numbers: O(1)
// sums all positive integers up until N in constant time
// sumNatural(4) would output 10 since 1 + 2 + 3 + 4 = 10
function sumNatural(n) {
  return n * (n + 1) / 2;
}

// Sort an array in descending order using a simple comparative arrow function
function sortDescending(a) {
  return a.sort((a, b) => b - a);
}

// Quick Sort: O(log n)
// A logarithmic time sort (partition/pivot sort): this will take an unordered array of data and recursively pivot
// the unorderd data around the value of the first element of the array
function quickSort(a) {
  if (a.length < 2) return a;
  
  let pivot = a[0];
  let left = [];
  let right = [];
  
  // begin at 2nd index
  for (let i = 1; i < a.length; i++) {
     if (a[i] < pivot) left.push(a[i]);
     else right.push(a[i]);
  }

  // recursively call quickSort on the remaining unsorted left and right hand sides of the now correctly positioned pivot
  return [
    ...quickSort(left),
    pivot,
    ...quickSort(right)
  ];
}

// Fibbonaci: O(n)
// see: https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence/360773#360773
// A Fibonacci number is always equal to the 2 numbers within the sequence that preceded it

// Return the Nth place fibonacci number: fibonacci(10) would return 55 (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...)
function fibonacci(n) {
  let fiboSequence = [0, 1];
  
  if (n < 2) return n;
  // starting from the 2nd index we dynamically add each Fibonacci sequence value to the array,
  // ensuring linear time and returning the result
  for (let i = 2; i <= n; i++) {
      fiboSequence[i] = fiboSequence[i-1] + fiboSequence[i-2];
  }
  
  return fiboSequence[n]
}

// Selection Sort: O(n^2)
// A classic sorting algorithm in quadratic time, this is a textbook inefficient sorting method and a good example of 
// why to avoid nested loops.
function selectionSort(a) {
  for (let i = 0; i < a.length; i++) {
    let min = i;
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[min]) min = j;
    }
    [a[i], a[min]] = [a[min], a[i]]; // ES6 destructuring assignment
  }
  
  return a;
}

// Factorial: O(n!)
// This simple function demonstrates factorial growth at worst case complexity which should be avoided at all costs
function factorial(n) {
  if (n === 0) return 1;
  
  let num = n;

  for (let i = 0; i < n; i++) {
    num = n * factorial(n - 1);
  }

  return num;
}