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 % 3 === 0 && i % 5 === 0) {
        console.log("fizzbuzz");
        continue;
      }
      if (i % 3 === 0) {
        console.log("fizz");
        continue;
      }
      if (i % 5 === 0) {
        console.log("buzz");
        continue;
      }
      console.log(i);
    }
  };
  fizzBuzz(15);
  // 1
  // 2
  // fizz
  // 4
  // buzz
  // fizz
  // 7
  // 8
  // fizz
  // buzz
  // 11
  // fizz
  // 13
  // 14
  // fizzbuzz
})();

// 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 toArray = (s) => s.split(", ");
  const toIndex = (arr) => arr.reduce((acc, it) => ({ ...acc, [it]: true }), {});
  const intersection = (s1, s2) => {
    const idx1 = toIndex(toArray(s1));
    const idx2 = toIndex(toArray(s2));
    let result = [];
    for (let key of Object.keys(idx1)) {
      if (idx2[key]) {
        result.push(key);
      }
    }
    return result.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) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
  const insertionSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; 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:
// - Stack
// - Queue
// - Stack using Queues
// - Queue using Stacks
(function () {
  class Stack {
    constructor() {
      this.items = [];
    }
    push(it) {
      this.items.push(it);
    }
    pop() {
      return this.items.pop();
    }
    peek() {
      return this.items[this.items.length - 1];
    }
    isEmpty() {
      return this.items.length === 0;
    }
  }
  const s = new Stack();
  for (let i = 0; i < 5; i++) {
    s.push(i);
  }
  s.pop();
  s.pop();
  s.push(9);
  console.log("Stack");
  while (!s.isEmpty()) {
    console.log(s.peek());
    s.pop();
  }
  // Stack
  // 9
  // 2
  // 1
  // 0

  class Queue {
    constructor() {
      this.items = [];
    }
    enqueue(it) {
      this.items.push(it);
    }
    dequeue() {
      return this.items.shift();
    }
    front() {
      return this.items[0];
    }
    isEmpty() {
      return this.items.length === 0;
    }
  }
  const q = new Queue();
  for (let i = 0; i < 5; i++) {
    q.enqueue(i);
  }
  q.dequeue();
  q.dequeue();
  q.enqueue(9);
  console.log("Queue");
  while (!q.isEmpty()) {
    console.log(q.front());
    q.dequeue();
  }
  // Queue
  // 2
  // 3
  // 4
  // 9

  class CustomStack {
    constructor() {
      this.q = new Queue();
      this.aux = new Queue();
    }
    _swapQueues() {
      [this.q, this.aux] = [this.aux, this.q];
    }
    push(it) {
      this.aux.enqueue(it);
      while (!this.q.isEmpty()) {
        this.aux.enqueue(this.q.dequeue());
      }
      this._swapQueues();
    }
    pop() {
      return this.q.dequeue();
    }
    peek() {
      return this.q.front();
    }
    isEmpty() {
      return this.q.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

  class CustomQueue {
    constructor() {
      this.s = new Stack();
      this.aux = new Stack();
    }
    enqueue(it) {
      while (!this.s.isEmpty()) {
        this.aux.push(this.s.pop());
      }
      this.s.push(it);
      while (!this.aux.isEmpty()) {
        this.s.push(this.aux.pop());
      }
    }
    dequeue() {
      return this.s.pop();
    }
    front() {
      return this.s.peek();
    }
    isEmpty() {
      return this.s.isEmpty();
    }
  }
  console.log("Queue vs CustomQueue");
  const queue = new Queue();
  const customQueue = new CustomQueue();
  const queues = [queue, customQueue];
  queues.forEach((s) => {
    for (let i = 0; i < 5; i++) {
      s.enqueue(i);
    }
    s.dequeue();
    s.dequeue();
    s.enqueue(9);
  });
  while (!queue.isEmpty() && !customQueue.isEmpty()) {
    console.log(`${queue.front()} || ${customQueue.front()}`);
    queue.dequeue();
    customQueue.dequeue();
  }
  // Queue vs CustomQueue
  // 2 || 2
  // 3 || 3
  // 4 || 4
  // 9 || 0
})();