JS algorithms

algorithms.js

// Remove duplicates from an array
(function() {
  Array.prototype.unique = function() {
    return Array.from(new Set(this));
  };
  console.log([1, 2, 3, 4, 4, 5].unique()); // [1, 2, 3, 4, 5]
})();

// Memoized function
(function() {
  const memoize = fn => {
    const cache = {};
    return (...params) => {
      const key = params.map(p => p.toString()).join("-");
      if (key in cache) {
        console.log(`[cached] ${cache[key]}`);
      } else {
        const result = fn(...params);
        cache[key] = result;
        console.log(`[not cached] ${result}`);
      }
    };
  };
  const add = (...params) => params.reduce((acc, it) => acc + it, 0);
  const multiply = (...params) => params.reduce((acc, it) => acc * it, 1);
  const memoizedAdd = memoize(add);
  const memoizedMultiply = memoize(multiply);
  memoizedAdd(1, 2, 3); // [not cached] 6
  memoizedAdd(1, 2, 3); // [cached] 6
  memoizedMultiply(1, 2, 3); // [not cached] 6
})();

// Count vowels
(function() {
  const countVowels = str => {
    const match = str.match(/[aeiou]/gi);
    return match ? match.length : 0;
  };
  console.log(countVowels("foo")); // 2
  console.log(countVowels("WTF")); // 0
})();

// Factorial
(function() {
  const factorial = n => {
    if (n < 1) {
      return 1;
    }
    return n * factorial(n - 1);
  };
  console.log(factorial(0)); // 1
  console.log(factorial(5)); // 120
})();

// Palindrome
// A palindrome is a word, sentence or other type of character sequence which reads the same backward as forward.
(function() {
  const isPalindrome = str => {
    const strLower = str.toLowerCase();
    return (
      strLower ===
      strLower
        .split("")
        .reverse()
        .join("")
    );
  };
  console.log(isPalindrome("Racecar")); // true
  console.log(isPalindrome("foo")); // false
})();

// FizzBuzz
// console logs the numbers from 1 to n, where n is the integer the function takes as its parameter.
// logs fizz instead of the number for multiples of 3.
// logs buzz instead of the number for multiples of 5.
// logs fizzbuzz for numbers that are multiples of both 3 and 5.
(function() {
  const fizzBuzz = n => {
    for (let i = 1; i <= n; i++) {
      if (i % 5 === 0 && i % 3 === 0) {
        console.log("fizzbuzz");
      } else if (i % 5 === 0) {
        console.log("buzz");
      } else if (i % 3 === 0) {
        console.log("fizz");
      } else {
        console.log(i);
      }
    }
  };
  fizzBuzz(5);
  // 1
  // 2
  // fizz
  // 4
  // buzz
})();

// Anagram
// A word is an anagram of another word if both use the same letters in the same quantity, but arranged differently.
(function() {
  // Regex
  // ^: not contained in set
  // \w: [a-zA-Z0-9_]
  // /g: all matches, it don't return after first match
  // Alternative: /[^a-zA-Z0-9]/g
  const strToWord = str => str.replace(/[^\w]/g, "").toLowerCase();
  const getChars = str =>
    str.split("").reduce(
      (acc, it) => ({
        ...acc,
        [it]: acc[it] ? acc[it] + 1 : 1,
      }),
      {},
    );
  const anagram = (a, b) => {
    const wordA = strToWord(a);
    const wordB = strToWord(b);
    const charsA = getChars(wordA);
    const charsB = getChars(wordB);
    if (Object.keys(charsA).length !== Object.keys(charsB).length) {
      return false;
    }
    for (let char of Object.keys(charsA)) {
      if (charsA[char] !== charsB[char]) {
        return false;
      }
    }
    return true;
  };
  console.log(anagram("finder", "Friend")); // true
  console.log(anagram("foo", "bar")); // false
})();

// Anagram: Given two strings,  and , that may or may not be of the same length, determine the minimum number of character deletions required to make  and  anagrams.
(function() {
  const makeAnagram = (a, b) => {
    let freqs = {};
    freqs = a.split("").reduce((acc, it) => ({ ...acc, [it]: (acc[it] || 0) + 1 }), freqs);
    freqs = b.split("").reduce((acc, it) => ({ ...acc, [it]: (acc[it] || 0) - 1 }), freqs);
    return Object.keys(freqs).reduce((sum, key) => sum + Math.abs(freqs[key]), 0);
  };
  console.log(makeAnagram("abc", "cde")); // 4
})();

// Fibonacci: Sum of the 2 previous values
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

// Fibonacci: Recursive approach
(function() {
  const fibonacci = n => {
    if (n < 2) {
      return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
  };
  // O(2^n)
  console.log(fibonacci(0)); // 0
  console.log(fibonacci(5)); // 5
  console.log(fibonacci(10)); // 55
})();

// Fibonacci: Memoized recursive approach
(function() {
  const fibonacci = n => {
    let memo = {};
    const _fib = n => {
      if (typeof memo[n] !== "undefined") {
        console.log(`[cached] fibonacci(${n}) = ${memo[n]}`);
        return memo[n];
      }
      if (n < 2) {
        memo[n] = n;
      } else {
        memo[n] = _fib(n - 1) + _fib(n - 2);
      }
      return memo[n];
    };
    return _fib(n);
  };
  // O(2n)
  console.log(fibonacci(0)); // 0
  console.log(fibonacci(5)); // 5
  console.log(fibonacci(10)); // 55
})();

// Intersection of strings
(function() {
  const intersection = (...input) => {
    const [firstList, secondList] = input.map(s => s.split(", "));
    const firstMap = firstList.reduce(
      (acc, it) => ({
        ...acc,
        [it]: true,
      }),
      {},
    );
    const intersection = [];
    for (let i of secondList) {
      if (firstMap[i]) {
        intersection.push(i);
      }
    }
    return intersection.join(",");
  };
  console.log(intersection("1, 2, 3", "2, 3, 4")); // 2,3
  console.log(intersection("1, 2, 3", "4, 5, 6")); //
})();

// Mising minimum positive integer
(function() {
  const missingInteger = A => {
    A = A.filter(it => it > 0).sort((a, b) => a - b);
    let x = 1;
    for (let i = 0; i < A.length; i++) {
      if (x < A[i]) {
        return x;
      }
      x = A[i] + 1;
    }
    return x;
  };
  console.log(missingInteger([1, 2, 3])); // 4
  console.log(missingInteger([4, 5, 1, 2])); // 3
  console.log(missingInteger([-1, -2])); // 1
})();

// Binary search: Iterative approach
(function() {
  // Precondition: array is sorted ascendingly
  const binarySearch = (arr, x) => {
    let startIndex = 0;
    const endIndex = arr.length - 1;
    while (startIndex <= endIndex) {
      const middleIndex = Math.floor((startIndex + endIndex) / 2);
      const currentValue = arr[middleIndex];
      if (currentValue === x) {
        return middleIndex;
      }
      if (currentValue < x) {
        startIndex++;
      } else {
        startIndex--;
      }
    }
    return -1;
  };
  // O(log n)
  const arr = [1, 2, 2, 3, 4, 5];
  console.log(binarySearch(arr, 1)); // 0
  console.log(binarySearch(arr, 2)); // 2
  console.log(binarySearch(arr, 6)); // -1
})();

// Binary search: Recursive approach
(function() {
  // Precondition: array is sorted ascendingly
  const binarySearch = (arr, x, startIndex = 0, endIndex = arr.length - 1) => {
    if (startIndex > endIndex) {
      return -1;
    }
    const middleIndex = Math.floor((startIndex + endIndex) / 2);
    const currentValue = arr[middleIndex];
    if (currentValue === x) {
      return middleIndex;
    }
    if (currentValue < x) {
      return binarySearch(arr, x, startIndex + 1, endIndex);
    } else {
      return binarySearch(arr, x, startIndex - 1, endIndex);
    }
  };
  // O(log n)
  const arr = [1, 2, 2, 3, 4, 5];
  console.log(binarySearch(arr, 1)); // 0
  console.log(binarySearch(arr, 2)); // 2
  console.log(binarySearch(arr, 6)); // -1
})();

// Bubble sort
(function() {
  // O(1)
  const swap = (arr, i, j) => {
    const tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  };
  const bubbleSort = arr => {
    let swapped;
    // O(n)
    do {
      swapped = false;
      // O(n)
      for (let i = 0; i < arr.length; i++) {
        // O(1)
        if (arr[i] > arr[i + 1]) {
          swap(arr, i, i + 1);
          swapped = true;
        }
      }
    } while (swapped);
    return arr;
  };
  // O(n ^ 2)
  console.log(bubbleSort([2, 7, 7, 8, 3, 5, 4, 1, 3]));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
})();

// Insertion sort
(function() {
  const swap = (arr, i, j) => {
    const [element] = arr.splice(i, 1);
    arr.splice(j, 0, element);
  };
  const insertionSort = arr => {
    // O(n)
    for (let i = 1; i < arr.length; i++) {
      // O(n)
      for (let j = 0; j < i; j++) {
        if (arr[i] < arr[j]) {
          swap(arr, i, j);
        }
      }
    }
    return arr;
  };
  // O(n ^ 2)
  console.log(insertionSort([2, 7, 7, 8, 3, 5, 4, 1, 3]));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
})();

// Selection sort
(function() {
  // O(1)
  const swap = (arr, i, j) => {
    const tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  };
  const selectionSort = arr => {
    // O(n)
    for (let i = 0; i < arr.length; i++) {
      let minIndex = i;
      // O(n)
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }
      if (i !== minIndex) {
        swap(arr, i, minIndex);
      }
    }
    // O(n ^ 2)
    return arr;
  };
  console.log(selectionSort([2, 7, 7, 8, 3, 5, 4, 1, 3]));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
})();

// Heap sort
(function() {
  const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
  const heapify = (arr, length, parent) => {
    let largest = parent;
    let left = parent * 2 + 1;
    let right = left + 1;
    if (left < length && arr[left] > arr[largest]) {
      largest = left;
    }
    if (right < length && arr[right] > arr[largest]) {
      largest = right;
    }
    if (largest !== parent) {
      swap(arr, largest, parent);
      heapify(arr, length, largest);
    }
    return arr;
  };
  const heapSort = arr => {
    let length = arr.length;
    let lastParent = Math.floor(length / 2 - 1);
    let lastChild = length - 1;
    while (lastParent >= 0) {
      heapify(arr, length, lastParent);
      lastParent--;
    }
    while (lastChild >= 0) {
      swap(arr, lastChild, 0);
      heapify(arr, lastChild, 0);
      lastChild--;
    }
    return arr;
  };
  // O(n * log n)
  console.log(heapSort([2, 7, 7, 8, 3, 5, 4, 1, 3]));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
})();

// Merge sort
(function() {
  // O(log n)
  const merge = (left, right) => {
    const sorted = [];
    while (left.length > 0 && right.length > 0) {
      const [lefEl] = left;
      const [rightEl] = right;
      if (rightEl < lefEl) {
        sorted.push(rightEl);
        right.shift();
      } else {
        sorted.push(lefEl);
        left.shift();
      }
    }
    while (left.length > 0) {
      const leftEl = left.shift();
      sorted.push(leftEl);
    }
    while (right.length > 0) {
      const rightEl = right.shift();
      sorted.push(rightEl);
    }
    return sorted;
  };
  const mergeSort = arr => {
    if (arr.length < 2) {
      return arr;
    }
    const middleIndex = Math.floor(arr.length / 2);
    const left = arr.slice(0, middleIndex);
    const right = arr.slice(middleIndex, arr.length);
    // mergeSort(left): O(log n) * n reursive times = O(n * log n)
    // mergeSort(right): O(log n) * n reursive times = O(n * log n)
    // O(n * log n + n * log n) = O(n * log n)
    // Why log n? Each recursive call will discard half of the elements on average following a logarithmic fashion.
    return merge(mergeSort(left), mergeSort(right));
  };
  console.log(mergeSort([2, 7, 7, 8, 3, 5, 4, 1, 3]));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
})();

// Quick sort
(function() {
  const first = arr => arr.shift();
  const middle = arr => {
    const index = Math.floor(arr.length - 1 / 2);
    const [pivot] = arr.splice(index, 1);
    return pivot;
  };
  const last = arr => arr.pop();
  const quickSort = (arr, pivotFn) => {
    // O(1)
    if (arr.length < 2) {
      return arr;
    }
    // O(1)
    const pivot = pivotFn(arr);
    const left = [];
    const right = [];
    // O(n)
    arr.forEach(it => (it < pivot ? left.push(it) : right.push(it)));
    // quickSort(left): O(log n) * n reursive times = O(n * log n)
    // quickSort(right): O(log n) * n reursive times = O(n * log n)
    // O(n * log n + n * log n) = O(n * log n)
    // Why log n? Each recursive call will discard half of the elements on average following a logarithmic fashion.
    return [...quickSort(left, pivotFn), pivot, ...quickSort(right, pivotFn)];
  };
  // O(1 + 1 + n + n * log n) = O(n + n * log n) = O(n * log n)
  console.log(quickSort([2, 7, 7, 8, 3, 5, 4, 1, 3], first));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
  console.log(quickSort([2, 7, 7, 8, 3, 5, 4, 1, 3], middle));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
  console.log(quickSort([2, 7, 7, 8, 3, 5, 4, 1, 3], last));
  // [1, 2, 3, 3, 4, 5, 7, 7, 8]
})();

// Implement a Stack using Queues
(function() {
  class Stack {
    constructor() {
      this.items = [];
    }
    push(item) {
      this.items.push(item);
    }
    pop() {
      if (this.isEmpty()) {
        throw new Error("Empty Stack");
      }
      return this.items.pop();
    }
    peek() {
      if (this.isEmpty()) {
        throw new Error("Empty Stack");
      }
      return this.items[this.items.length - 1];
    }
    isEmpty() {
      return this.items.length === 0;
    }
  }
  class Queue {
    constructor() {
      this.items = [];
    }
    enqueue(item) {
      this.items.push(item);
    }
    dequeue() {
      if (this.isEmpty()) {
        throw new Error("Empty Queue");
      }
      return this.items.shift();
    }
    front() {
      if (this.isEmpty()) {
        throw new Error("Empty Queue");
      }
      return this.items[0];
    }
    isEmpty() {
      return this.items.length === 0;
    }
  }
  class CustomStack {
    constructor() {
      this.q1 = new Queue();
      this.q2 = new Queue();
    }
    _swapQueues() {
      const tmp = this.q1;
      this.q1 = this.q2;
      this.q2 = tmp;
    }
    push(item) {
      this.q2.enqueue(item);
      while (!this.q1.isEmpty()) {
        this.q2.enqueue(this.q1.dequeue());
      }
      this._swapQueues();
    }
    pop() {
      if (this.q1.isEmpty()) {
        throw new Error("Empty CustomStack");
      }
      this.q1.dequeue();
    }
    peek() {
      if (this.q1.isEmpty()) {
        throw new Error("Empty CustomStack");
      }
      return this.q1.front();
    }
    isEmpty() {
      return this.q1.isEmpty();
    }
  }
  const stack = new Stack();
  const customStack = new CustomStack();
  const stacks = [stack, customStack];
  stacks.forEach(s => {
    for (let i = 0; i < 5; i++) {
      s.push(i);
    }
    s.pop();
    s.pop();
    s.push(9);
  });
  console.log("Stack vs CustomStack");
  while (!stack.isEmpty() && !customStack.isEmpty()) {
    console.log(`${stack.peek()} || ${customStack.peek()}`);
    stack.pop();
    customStack.pop();
  }
  // Stack vs CustomStack
  // 9 || 9
  // 2 || 2
  // 1 || 1
  // 0 || 0
})();