thewhitefox

# JS Algorithms

2022 January 11th Written by theWhiteFox

## Algorithms written in JS:

Vinilla JavaScript (JS) Algorithms are repeatable? The following are some Algorithms I wrote in JS.

1. Two Sum
2. Fibonacci - learn recursion
3. Fizzbuzz - little fun test
4. Dijkstra - shortest path between nodes
5. Harmless Ransom Note use Big O notation
6. Palindrome - String & array manipulation - String and array methods
7. Caesar's Cipher - encryption
8. Reverse string

## Write Algorithms & write them in JS:

I love to cook delicious food while figuring out new recipes. Algorithms for me are like programming recipes. As with recipes I Read, Cook, Eat, Tweak & Repeat this concept I follow with algoritms Read, Write, Run, Tweak & Repeat.

In my humble opinion, a good way to improve one's cooking skills is to take recipes and create your own either by tweaking or taking the concepts of what one has learned and applying them to different ingredients, in this post different programming languages.

As with my cooking, my programming and problem solving I hopw will improve by learning algorithms, these are some JavaScript (JS) algorithms that I will understand, not just do. JS(ES6)

In this post I chose JS as the language to learn the below algorithms because it's modern, fun, always evleving and most importantly the language of the web.

### Using Big O Notation

A way to test time & space of an algorithm.

"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity." Wikipedia

### Two Sum

Check an array for the sum of two values using Big O notation looping through the array twice to find a pair.

The first algorithm will be a JS `function twoSumBrute` that takes two parameters, a numbers array `arr` and a sum value `sum`. `twoSumBrute` returns a of pair indices from `arr` that add up to the `sum` value, function parameter.

The first attempt will use brute force O(n2). The arr passed in has already been defined within the JS code as `const arr = [3, 7, 11, 15];`.

`1// Brute Two Sum return indices O(n)22// returns a of pair indices from `arr`3// that add up to the `sum` parameter4const arr = [3, 7, 11, 15];5const sum = 10;67const twoSumBrute = (arr, sum) => {8  const sums = [];910  // check first element in arr11  for (let firstElement = 0; firstElement < arr.length; firstElement++) {12    // check second element in arr13    for (let secondElement = 0; secondElement < arr.length; secondElement++) {14      if (arr[firstElement] + arr[secondElement] === sum) {15        sums.push(arr[firstElement] + arr[secondElement]);16      }17    }18  }19  return sums;20};2122twoSumBrute(arr, sum);`

A faster solution would be linear time using using a Hash table instead of the brute force algorithm above ☝️.

`1// faster Two Sum using hashTable2const arr = [3, 7, 11, 15];3const sum = 10;45const twoSumHash = (arr, sum) => {6  const sums = [];7  const hashTable = {};89  // check first element in arr10  for (let firstElement = 0; firstElement < arr.length; firstElement++) {11    const sumMinusElement = sum - firstElement[i];12    // check second element in arr13    for (let secondElement = 0; secondElement < arr.length; secondElement++) {14      if (hashTable[sumMinusElement.toString] !== undefined) {15        sums.push(arr[firstElement], sumMinusElement);16      }1718      // add the current number to the hash table19      hashTable[arr[i].toString()] = arr[i];20    }21  }22  return sums;23};2425twoSumHash(arr, sum);`

### Fibonacci

Fibonacci was a mathematician who developed the Fibonacci sequence, such that each number is the sum of the two preceding ones. The Fibonacci Sequence is found all throughout nature, too. It is a naturally occurring pattern. My first learning of Fibonacci was in nature as part of my art studies, I drew a Nautilus shell.

Fibonacci using while loops, recursion O(2^n) Memoization

`1(function () {2  // Big O3  // 1, 1, 2, 3, 5, 8, 114  function fibonacci(num) {5    var a = 1,6      b = 0,7      temp2;89    while (num > 0) {10      temp2 = a;11      a = a + b;12      b = temp2;13      num--;14      console.log(temp2);15    }16    return b;17  }18  fibonacci(7);1920  const basicFib = () => {21    let first = 1,22      second = 0,23      answer = first + second;2425    while (answer < 10) {26      console.log(answer);27      second = first;28      first = answer;29      answer = first + second;30    }31    basicFib();32  };33})();`

### Fizzbuzz

An algorithm sometimes used as a basic interview test.

`1// FizzBuzz2// modulus operator3console.log("modulus operator: 7 % 3 = " + (7 % 3));45function fizzBuzz(num) {6  for (var i = 1; i <= num; i++) {7    if (i % 15 === 0) console.log("FizzBuzz");8    else if (i % 5 === 0) console.log("fizz");9    else if (i % 3 === 0) console.log("Buzz");10    else console.log(i);11  }12}1314fizzBuzz(20);1516// Dijkstra’s Algorithm17const problem = {18  start: { A: 5, B: 2 },19  A: { C: 4, D: 2 },20  B: { A: 8, D: 7 },21  C: { D: 6, finish: 3 },22  D: { finish: 1 },23  finish: {},24};`

### Dijkstra

Dijkstra an algorithm for finding the shortest paths between nodes in a graph.

`1// Dijkstra’s Algorithm2const problem = {3  start: { A: 5, B: 2 },4  A: { C: 4, D: 2 },5  B: { A: 8, D: 7 },6  C: { D: 6, finish: 3 },7  D: { finish: 1 },8  finish: {},9};1011// implementing the algorithm12const lowestCostNode = (costs, processed) => {13  return Object.keys(costs).reduce((lowest, node) => {14    if (lowest === null || costs[node] < costs[lowest]) {15      if (!processed.includes(node)) {16        lowest = node;17      }18    }19    return lowest;20  }, null);21};2223// func that returns the min cost and path to reach finish24const dijkstra = (graph) => {25  // track lowest cost to reach each node26  const costs = Object.assign({ finish: Infinity }, graph.start);2728  // track paths29  const parents = { finish: null };3031  // add children of the start node32  for (let child in graph.start) {33    parents[child] = "start";34  }3536  // track nodes that have already been processed37  const processed = [];3839  // get the cost of the current node40  let node = lowestCostNode(costs, processed);4142  // get all the children of the current43  while (node) {44    let cost = costs[node];45    let children = graph[node];46    // loop through each of the children47    for (let n in children) {48      let newCost = cost + children[n];49      if (!cost[n]) {50        costs[n] = newCost;51        parents[n] = node;52      }53      if (costs[n] > newCost) {54        costs[n] = newCost;55        parents[n] = node;56      }57    }58    // push to processed data structure59    processed.push(node);60    node = lowestCostNode(costs, processed);61  }6263  let optimalPath = ["finish"];64  let parent = parents.finish;6566  while (parent) {67    optimalPath.push(parent);68    parent = parents[parent];69  }7071  optimalPath.reverse(); // reverse array to get order7273  const results = {74    distance: costs.finish,75    path: optimalPath,76  };77  return results;78};7980console.log(dijkstra(problem));8182// Object { distance: 12, path: […] }83// distance: 1284// path: […]​85// 0: "parent"86// 1: "parent"87// 2: "parent"88// 3: "finish"89// length: 4`
APIsLearn React