Algorithms in JavaScript

javascript

Algorithms in JavaScript is a trial on how to build simple algorithms in JavaScript.

SECTION 1 – Introduction

Algorithms make programs run better and faster.

SECTION 2 – FizzBuzz

Introduction
A function that will take a number and log all the numbers from 1 till that given number.
Additionally, if the number to be logged is divisible by 3, then log ‘Fizz’, if divisible by 5, then log ‘Buzz’ and if by both 3 & 5, then log ‘FizzBuzz

Modulus Operator – It returns the remainder of a division.

Code

function fizzBuzz(num) {
   for (var i = 1; i<= num; i++) {
       if (i % 3 === 0 && i % 5 === 0) {
           console.log('FizzBuzz');
       } else if (i % 3 === 0) {
           console.log('Fizz');
       } else if (i % 5 === 0) {
           console.log('Buzz');
       } else {
           console.log(i);
       }
   }
}
fizzBuzz(30);

SECTION 3 – Harmless Ransom Note

Introduction
Time Complexity = O(n) + O(m) = O(n+m) // Due to 2 separate loops of different length

Source Code

function harmlessRansomNote(noteText, magazineText) {
 var noteArr = noteText.split(' ');
 var magazineArr = magazineText.split(' ');
 var magazineObj = {};
 magazineArr.forEach(word => {
   if (!magazineObj[word]) magazineObj[word] = 0;
   magazineObj[word]++;
 });
 var noteIsPossible = true;
 noteArr.forEach(word => {
   if (magazineObj[word]) {
     magazineObj[word]--;
     if (magazineObj[word] < 0) noteIsPossible = false;
   }
   else noteIsPossible = false;
 });
 return noteIsPossible;
}
harmlessRansomNote('this is a secret note for you from a secret admirer', 'puerto rico is a place of great wonder and excitement it has many secret waterfall locatoins that i am an admirer of you must hike quite a distance to find the secret places as they are far from populated areas but it is worth the effort a tip i have for you is to go early in the morning when it is not so hot out also note that you must wear hiking boots this is one of the best places i have ever visited');

SECTION 4 – Is Palindrome

Introduction
Words spelled similarly both forward or backward

Source Code

function isPalindrome(string) {
 string = string.toLowerCase();
 var charactersArr = string.split('');
 var validCharacters = 'abcdefghijklmnopqrstuvwxyz'.split('');
 var lettersArr = [];
 charactersArr.forEach(char => {
   if (validCharacters.indexOf(char) > -1) lettersArr.push(char);
 });
 return lettersArr.join('') === lettersArr.reverse().join('');
}
isPalindrome("Madam, I'm Adam");

SECTION 5 – Caesar Cipher

Introduction
It takes a string and a number and advances every alphabet in the string by the number provided.

apple, 2 => crrng

Source Code

function caesarCipher(str,num) {
 num = num % 26;
 var lowerCaseString = str.toLowerCase();
 var alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('');
 var newString = '';
 for (var i = 0; i < lowerCaseString.length; i++) {
   var currentLetter = lowerCaseString[i];
   if (currentLetter === ' ') {
     newString += currentLetter;
     continue;
   }
   var currentIndex = alphabet.indexOf(currentLetter);
   var newIndex = currentIndex + num;
   if (newIndex > 25) newIndex = newIndex - 26;
   if (newIndex < 0) newIndex = 26 + newIndex;
   if (str[i] === str[i].toUpperCase()) {
     newString += alphabet[newIndex].toUpperCase();
   }
   else newString += alphabet[newIndex];
 };
 return newString;
}
caesarCipher('Zoo Keeper', -2);

SECTION 6 – Reverse Words

Introduction
Reverse the string that is provided
Every word in a string needs to be reversed but not the whole string. Also Array.reverse() should not be used.

Source Code

function reverseWords(string) {
 var wordsArr = string.split(' ');
 var reversedWordsArr = [];
 wordsArr.forEach(word => {
   var reversedWord = '';
   for (var i = word.length - 1; i >= 0; i--) {
     reversedWord += word[i];
   };
   reversedWordsArr.push(reversedWord);
 });
 return reversedWordsArr.join(' ');
}
reverseWords('Coding JavaScript');

SECTION 7 – Reverse Array in Place

Introduction
Reverse the array that is passed in rather than in a new array.

function reverseArrayInPlace(arr) {
 for (var i = 0; i < arr.length / 2; i++) {
   var tempVar = arr[i];
   arr[i] = arr[arr.length - 1 - i];
   arr[arr.length - 1 - i] = tempVar;
 }
 return arr;
}
reverseArrayInPlace([1, 2, 3, 4, 5, 6, 7]);

SECTION 8 – Mean Median Mode

Introduction
Return the Mean, the Median and the Mode of a given array.

Mean = Total Sum / Number of elements
Median = Sorted array => Middle element
Mode = Which number(s) appear multiple times

Source Code

function meanMedianMode(array) {
 return {
   mean: getMean(array),
   median: getMedian(array),
   mode: getMode(array)
 }
}
function getMean(array) {
 var sum = 0;
 array.forEach(num => {
   sum += num;
 });
 var mean = sum / array.length;
 return mean;
}
function getMedian(array) {
 array.sort(function(a, b){return a-b});
 var median;
 if (array.length % 2 !== 0) {
   median = array[Math.floor(array.length / 2)];
 } else {
   var mid1 = array[(array.length / 2) - 1];
   var mid2 = array[array.length / 2];
   median = (mid1 + mid2) / 2;
 }
 return median;
}
function getMode(array) {
 var modeObj = {};
 // create modeObj
 array.forEach(num => {
   if (!modeObj[num]) modeObj[num] = 0;
   modeObj[num]++;
 });
 // create array of mode/s
 var maxFrequency = 0;
 var modes = [];
 for (var num in modeObj) {
   if (modeObj[num] > maxFrequency) {
     modes = [num];
     maxFrequency = modeObj[num];
   }
   else if (modeObj[num] === maxFrequency) modes.push(num);
 }
 // if every value appears same amount of times
 if (modes.length === Object.keys(modeObj).length) modes = [];
 return modes;
}
meanMedianMode([9,10,23,10,23,9]);

SECTION 9 – Two Sum

Introduction
Will take two parameters, one a number array and another parameter called sum and the algorithm should return all the pairs of numbers that add up to the ‘sum’ variable
– Result should be an array of arrays
– A number can be used multiple pairs

Code

function twoSum(numArray, sum) {
var pairs = [];
var hashtable = [];
for (var i=0; i < numArray.length; i++) {
var curNum = numArray[i];
var counterPart = sum - curNum;
if (hashtable.indexOf(counterPart) !=== -1) {
pairs.push([curNum, counterPart]);
}
hashtable.push(curNum);
}
return pairs;
}
twoSum([1,6,4,5,3,3], 7); // [[6,1], [3,4], [3,4]]

Source Code

--

SECTION 10 – Binary Search

Introduction
Searches for a given value inside an array, with a time complexity of  O(log n) runtime which is very performant
Use recursion to achieve the purpose.
To do a binary search, the array provided in should be sorted by value;

Source Code

function binarySearch(numArray, key) {
   var middleIdx = Math.floor(numArray.length / 2);
   var middleElem = numArray[middleIdx];
   if (middleElem === key) return true;
   else if (middleElem < key && numArray.length > 1) {
       return binarySearch(numArray.splice(middleIdx, numArray.length), key);
   }
   else if (middleElem > key && numArray.length > 1) {
       return binarySearch(numArray.splice(0, middleIdx), key);
   }
   else return false;
}
binarySearch([5, 7, 12, 16, 36, 39, 42, 56, 71], 56);

SECTION 11 – Fibonacci

Introduction
The sequence – 1, 1, 2, 3, 5, 8, 13, 21, 34, …
We need to provide a ‘position’ argument to the function and get the number at the position in the Fibonacci sequence.

The following code using recursion to find the Fibonacci series has a time complexity of 2^n, and can be done by running the series for the 50th position which would probably hang the browser.

Source Code

function fibonacci(position) {
 if (position < 3) return 1;
 else return fibonacci(position - 1) + fibonacci(position - 2);
}
fibonacci(6);

Memoized Fibonacci
Here we keep the already calculated index in a cache and use it for any future calls.

Source Code

function fibMemo(index, cache) {
 cache = cache || [];
 if (cache[index]) return cache[index];
 else {
   if (index < 3) return 1;
   else {
     cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
   }
 }
 return cache[index];
}
fibMemo(500);

SECTION 13 – Sieve of Eratosthenes

Introduction
Find all the prime numbers to the given value.

sieveOfEratosthenes(20) => [2,3,5,7,11,13,17,19]

Create an array of length ‘n+1’ marking every item as true signifying all as prime numbers. Here we are going to use the index as the number itself.
An optimization is to stop the prime checking at the square-root of the number passed, because by the time we reach the square rot value, all the non-prime numbers would have been marked false.

Source Code

function sieveOfEratosthenes(n) {
 var primes = [];
 for (var i = 0; i <= n; i++) {
   primes[i] = true;
 }
 primes[0] = false;
 primes[1] = false;
 for (var i = 2; i <= Math.sqrt(n); i++) {
   for (j = 2; i * j <= n; j++) {
     primes[i * j] = false;
   }
 }
 var result = [];
 for (var i = 0; i < primes.length; i++) {
   if (primes[i]) result.push(i);
 }
 return result;
}
sieveOfEratosthenes(49);

SECTION 14 – Bubble Sort

Introduction
We make a pass through the array everytime, switching the elements if the left number is alrger than the right one.
It takes n-1 passes through the array to completely sort an array.

function bubbleSort(array) {
   for (var i = array.length; i > 0; i--) {
     for (var j = 0; j < i; j++) {
       if (array[j] > array[j + 1]) {
         var temp = array[j];
         array[j] = array[j + 1];
         array[j + 1] = temp;
       }
     }
   }
   return array;
}
bubbleSort([6000, 34, 203, 3, 746, 200, 984, 198, 764, 9, 1]);

SECTION 15 – Merge Sort

Introduction
It includes dividing the array to 2 sorted arrays and then merging it. This can be achieved by continuously dividing the arrays until we reach array of individual elements, then start combining them in a sorted manner, till we reach the final array of sorted elements.

Can have a visual explanation of what’s happening during the recursion.

Source Code

function mergeSort (arr) {
   if (arr.length < 2) return arr;
   var middleIndex = Math.floor(arr.length / 2);
   var firstHalf = arr.slice(0, middleIndex);
   var secondHalf = arr.slice(middleIndex);
   return merge(mergeSort(firstHalf), mergeSort(secondHalf));
}
function merge (array1, array2) {
   var result = [];
   while (array1.length && array2.length) {
     var minElem;
     if (array1[0] < array2[0]) minElem = array1.shift();
     else minElem = array2.shift();
     result.push(minElem);
   }
   if (array1.length) result = result.concat(array1);
   else result =result.concat(array2);
   return result;
}
mergeSort([6000, 34, 203, 3, 746, 200, 984, 198, 764, 1, 9, 1]);

SECTION 16 – Max Stock Profit

Introduction
This will take an array of prices of a stock in a day and determine the maximum profit that could have been made, if you buy and sell the stock from the list of prices available.

Source Code

function maxStockProfit (pricesArr) {
  var maxProfit = -1;
  var buyPrice = 0;
  var sellPrice = 0;
  var changeBuyPrice = true;
  for (var i = 0; i < pricesArr.length; i++) {
    if (changeBuyPrice) buyPrice = pricesArr[i];
    sellPrice = pricesArr[i + 1];
    if (sellPrice < buyPrice) {
      changeBuyPrice = true;
    } else {
      var tempProfit = sellPrice - buyPrice;
      if (tempProfit > maxProfit) maxProfit = tempProfit;
      changeBuyPrice = false;
    }
  }
  return maxProfit;
}
maxStockProfit([10, 18, 4, 5, 9, 6, 16, 12]);

You can learn more on JavaScript here.

Leave a Reply

Your email address will not be published. Required fields are marked *