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.