algorithms

fibonacci.js

/**
 * Recursively computes the nth fibonachi #. This method is super slow because
 * there is a tonnn of duplicated work.
 *
 * runtime: O(n*(n-1)(n-2) + n(n-2)) = O(n^2)
 *
 * @param {number} n
 * @return {number}
 */
function naiveFibonacci(n) {
  if (n <= 1) {
    return n;
  }

  return naiveFibonacci(n - 1) + naiveFibonacci(n - 2);
}

/**
 * memoized naive fibonacci is much better but still overly complicated
 *
 * runtime: O(n)
 *
 * @param {number} n
 * @return {number}
 */
function memoizedNaiveFibonacci(n) {
  fibonacci.visited = fibonacci.visited || new Array(n);

  if (n <= 1) {
    fibonacci.visited[n] = n;

    return n;
  } else if (fibonacci.visited[n]) {
    return fibonacci.visited[n];
  }

  fibonacci.visited[n] = fibonacci(n - 1) + fibonacci(n - 2);

  return fibonacci.visited[n];
}

/**
 * operations: ~ 6n + 4
 *
 * runtime: O(n^2)
 * loop is O(n) but addition of large #s is proportional to length n
 * so for each loop it's safer to say O(n)*O(n)
 *
 * @param {number} n
 * @return {number}
 */
function fastSimpleFibonacci(n) {
  if (n <= 1) {
    return n;
  }

  const sequence = new Array(n);    // ~ 1 operation (1x assignment)
  sequence[0] = 0;                  // ~ 1 operation (1x assignment)
  sequence[1] = 1;                  // ~ 1 operation (1x assignment)

  for (let i = 2; i <= n; i++) {                  // ~ 2 operations (1x guard, 1x increment)
    sequence[i] = sequence[i-1] + sequence[i-2];  // ~ 4 operations (1x assignment, 2x access, 1x addition)
  }                                               // caveat: the addition will be a non-trivial operation at very high values

  return sequence[n];               // ~ 1 operation (1x access)
}

greated_common_divisor.js

/**
 * Uses euclid's algorithm:
 * https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid's_algorithm
 *
 * Finds the largest common divisor of 2 numbers.
 *
 * runtime: O(log(min(a,b)))
 *
 * @param {number} a
 * @param {number} b (where b is less than a)
 */
function euclidGCD(a, b) {
  if (b === 0) {
    return a;
  )
  if (a > b) {    
    const remainder = a % b;
    
    return euclidGCD(b, remainder);
  } else {
    const remainder = b % a;
    
    return euclidGCD(a, remainder);
  }
}

maximum_pairwise_product.js

/**
 * (Max time used: 0.41/5.00s, max memory used: 40431616/536870912)
 *
 * runtime: O(???)
 *
 * @param {number[]} numbers
 * @return {number}
 */
function doPairWise(numbers) {
  let maxVal1 = -1;
  let maxIdx1 = -1;
  let maxVal2 = -1;

  // first pass finds the global maximum
  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i] > maxVal1) {
      maxVal1 = numbers[i];
      maxIdx1 = i;
    }
  }

  // 2nd pass looks for the 2nd highest global maximum
  // but also ignores the index for the 1st global maximum
  for (let i = 0; i < numbers.length; i++) {
    if (i === maxIdx1) {
      continue;
    }

    if (numbers[i] > maxVal2) {
      maxVal2 = numbers[i];
    }
  }

  // multiply the 2 highest maximums gives the maximum pairwise product from a list of numbers
  return maxVal1 * maxVal2;
}