DEV Community: Huy Do

Bit Manipulation

Huy Do — Sun, 29 Nov 2020 23:56:10 +0000

Get Bit

This method shifts the relevant bit to the zeroth position. Then we perform AND operation with one which has bit pattern like 0001. This clears all bits from the original number except the relevant one. If the relevant bit is one, the result is 1, otherwise the result is 0.

Set Bit

This method shifts 1 over by bitPosition bits, creating a value that looks like 00100. Then we perform OR operation that sets specific bit into 1 but it does not affect on other bits of the number.

Clear Bit

This method shifts 1 over by bitPosition bits, creating a value that looks like 00100. Than it inverts this mask to get the number that looks like 11011. Then AND operation is being applied to both the number and the mask. That operation unsets the bit.

Update Bit

This method is a combination of "Clear Bit" and "Set Bit" methods.

isEven

This method determines if the number provided is even. It is based on the fact that odd numbers have their last right bit to be set to 1.

Number: 5 = 0b0101
isEven: false

Number: 4 = 0b0100
isEven: true

isPositive

This method determines if the number is positive. It is based on the fact that all positive numbers have their leftmost bit to be set to 0. However, if the number provided is zero or negative zero, it should still return false.

Number: 1 = 0b0001
isPositive: true

Number: -1 = -0b0001
isPositive: false

Multiply By Two

This method shifts original number by one bit to the left. Thus all binary number components (powers of two) are being multiplying by two and thus the number itself is being multiplied by two.

Before the shift
Number: 0b0101 = 5
Powers of two: 0 + 2^2 + 0 + 2^0

After the shift
Number: 0b1010 = 10
Powers of two: 2^3 + 0 + 2^1 + 0

Divide By Two

This method shifts original number by one bit to the right. Thus all binary number components (powers of two) are being divided by two and thus the number itself is being divided by two without remainder.

Before the shift
Number: 0b0101 = 5
Powers of two: 0 + 2^2 + 0 + 2^0

After the shift
Number: 0b0010 = 2
Powers of two: 0 + 0 + 2^1 + 0

Switch Sign

This method make positive numbers to be negative and backwards. To do so it uses "Twos Complement" approach which does it by inverting all of the bits of the number and adding 1 to it.

Multiply Two Signed Numbers

This method multiplies two signed integer numbers using bitwise operators. This method is based on the following facts:

a * b can be written in the below formats:
  0                     if a is zero or b is zero or both a and b are zeroes
  2a * (b/2)            if b is even
  2a * (b - 1)/2 + a    if b is odd and positive
  2a * (b + 1)/2 - a    if b is odd and negative

The advantage of this approach is that in each recursive step one of the operands reduces to half its original value. Hence, the run time complexity is O(log(b)) where b is the operand that reduces to half on each recursive step.

References

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/bits

Bloom Filter

Huy Do — Mon, 23 Nov 2020 03:14:04 +0000

Bloom Filter

A bloom filter is a space-efficient probabilistic data structure designed to test whether an element is present in a set. It is designed to be blazingly fast and use minimal memory at the cost of potential false positives. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set".

Bloom proposed the technique for applications where the amount of source data would require an impractically large amount of memory if "conventional" error-free hashing techniques were applied.

Algorithm description

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions, generating a uniform random distribution. Typically, k is a constant, much smaller than m, which is proportional to the number of elements to be added; the precise choice of k and the constant of proportionality of m are determined by the intended false positive rate of the filter.

Here is an example of a Bloom filter, representing the set {x, y, z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.

Operations

There are two main operations a bloom filter can perform: insertion and search. Search may result in false positives. Deletion is not possible.

In other words, the filter can take in items. When we go to check if an item has previously been inserted, it can tell us either "no" or "maybe".

Both insertion and search are O(1) operations.

Making the filter

A bloom filter is created by allotting a certain size. In our example, we use 100 as a default length. All locations are initialized to false.

Insertion

During insertion, a number of hash functions, in our case 3 hash functions, are used to create hashes of the input. These hash functions output indexes. At every index received, we simply change the value in our bloom filter to true.

Search

During a search, the same hash functions are called and used to hash the input. We then check if the indexes received all have a value of true inside our bloom filter. If they all have a value of true, we know that the bloom filter may have had the value previously inserted.

However, it's not certain, because it's possible that other values previously inserted flipped the values to true. The values aren't necessarily true due to the item currently being searched for. Absolute certainty is impossible unless only a single item has previously been inserted.

While checking the bloom filter for the indexes returned by our hash functions, if even one of them has a value of false, we definitively know that the item was not previously inserted.

False Positives

The probability of false positives is determined by three factors: the size of the bloom filter, the number of hash functions we use, and the number of items that have been inserted into the filter.

The formula to calculate probablity of a false positive is:

( 1 - e -kn/m ) k

k = number of hash functions

m = filter size

n = number of items inserted

These variables, k, m, and n, should be picked based on how acceptable false positives are. If the values are picked and the resulting probability is too high, the values should be tweaked and the probability re-calculated.

Applications

A bloom filter can be used on a blogging website. If the goal is to show readers only articles that they have never seen before, a bloom filter is perfect. It can store hashed values based on the articles. After a user reads a few articles, they can be inserted into the filter. The next time the user visits the site, those articles can be filtered out of the results.

Some articles will inevitably be filtered out by mistake, but the cost is acceptable. It's ok if a user never sees a few articles as long as they have other, brand new ones to see every time they visit the site.

References

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/bloom-filter

Graph, Disjoint Set

Huy Do — Sun, 15 Nov 2020 22:04:19 +0000

Graph

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory

A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

export default class Graph {
  /**
   * @param {boolean} isDirected
   */
  constructor(isDirected = false) {
    this.vertices = {};
    this.edges = {};
    this.isDirected = isDirected;
  }

  /**
   * @param {GraphVertex} newVertex
   * @returns {Graph}
   */
  addVertex(newVertex) {
    this.vertices[newVertex.getKey()] = newVertex;

    return this;
  }

  /**
   * @param {string} vertexKey
   * @returns GraphVertex
   */
  getVertexByKey(vertexKey) {
    return this.vertices[vertexKey];
  }

  /**
   * @param {GraphVertex} vertex
   * @returns {GraphVertex[]}
   */
  getNeighbors(vertex) {
    return vertex.getNeighbors();
  }

  /**
   * @return {GraphVertex[]}
   */
  getAllVertices() {
    return Object.values(this.vertices);
  }

  /**
   * @return {GraphEdge[]}
   */
  getAllEdges() {
    return Object.values(this.edges);
  }

  /**
   * @param {GraphEdge} edge
   * @returns {Graph}
   */
  addEdge(edge) {
    // Try to find and end start vertices.
    let startVertex = this.getVertexByKey(edge.startVertex.getKey());
    let endVertex = this.getVertexByKey(edge.endVertex.getKey());

    // Insert start vertex if it wasn't inserted.
    if (!startVertex) {
      this.addVertex(edge.startVertex);
      startVertex = this.getVertexByKey(edge.startVertex.getKey());
    }

    // Insert end vertex if it wasn't inserted.
    if (!endVertex) {
      this.addVertex(edge.endVertex);
      endVertex = this.getVertexByKey(edge.endVertex.getKey());
    }

    // Check if edge has been already added.
    if (this.edges[edge.getKey()]) {
      throw new Error('Edge has already been added before');
    } else {
      this.edges[edge.getKey()] = edge;
    }

    // Add edge to the vertices.
    if (this.isDirected) {
      // If graph IS directed then add the edge only to start vertex.
      startVertex.addEdge(edge);
    } else {
      // If graph ISN'T directed then add the edge to both vertices.
      startVertex.addEdge(edge);
      endVertex.addEdge(edge);
    }

    return this;
  }

  /**
   * @param {GraphEdge} edge
   */
  deleteEdge(edge) {
    // Delete edge from the list of edges.
    if (this.edges[edge.getKey()]) {
      delete this.edges[edge.getKey()];
    } else {
      throw new Error('Edge not found in graph');
    }

    // Try to find and end start vertices and delete edge from them.
    const startVertex = this.getVertexByKey(edge.startVertex.getKey());
    const endVertex = this.getVertexByKey(edge.endVertex.getKey());

    startVertex.deleteEdge(edge);
    endVertex.deleteEdge(edge);
  }

  /**
   * @param {GraphVertex} startVertex
   * @param {GraphVertex} endVertex
   * @return {(GraphEdge|null)}
   */
  findEdge(startVertex, endVertex) {
    const vertex = this.getVertexByKey(startVertex.getKey());

    if (!vertex) {
      return null;
    }

    return vertex.findEdge(endVertex);
  }

  /**
   * @return {number}
   */
  getWeight() {
    return this.getAllEdges().reduce((weight, graphEdge) => {
      return weight + graphEdge.weight;
    }, 0);
  }

  /**
   * Reverse all the edges in directed graph.
   * @return {Graph}
   */
  reverse() {
    /** @param {GraphEdge} edge */
    this.getAllEdges().forEach((edge) => {
      // Delete straight edge from graph and from vertices.
      this.deleteEdge(edge);

      // Reverse the edge.
      edge.reverse();

      // Add reversed edge back to the graph and its vertices.
      this.addEdge(edge);
    });

    return this;
  }

  /**
   * @return {object}
   */
  getVerticesIndices() {
    const verticesIndices = {};
    this.getAllVertices().forEach((vertex, index) => {
      verticesIndices[vertex.getKey()] = index;
    });

    return verticesIndices;
  }

  /**
   * @return {*[][]}
   */
  getAdjacencyMatrix() {
    const vertices = this.getAllVertices();
    const verticesIndices = this.getVerticesIndices();

    // Init matrix with infinities meaning that there is no ways of
    // getting from one vertex to another yet.
    const adjacencyMatrix = Array(vertices.length).fill(null).map(() => {
      return Array(vertices.length).fill(Infinity);
    });

    // Fill the columns.
    vertices.forEach((vertex, vertexIndex) => {
      vertex.getNeighbors().forEach((neighbor) => {
        const neighborIndex = verticesIndices[neighbor.getKey()];
        adjacencyMatrix[vertexIndex][neighborIndex] = this.findEdge(vertex, neighbor).weight;
      });
    });

    return adjacencyMatrix;
  }

  /**
   * @return {string}
   */
  toString() {
    return Object.keys(this.vertices).toString();
  }
}

Disjoint Set

Disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

import DisjointSetItem from './DisjointSetItem';

export default class DisjointSet {
  /**
   * @param {function(value: *)} [keyCallback]
   */
  constructor(keyCallback) {
    this.keyCallback = keyCallback;
    this.items = {};
  }

  /**
   * @param {*} itemValue
   * @return {DisjointSet}
   */
  makeSet(itemValue) {
    const disjointSetItem = new DisjointSetItem(itemValue, this.keyCallback);

    if (!this.items[disjointSetItem.getKey()]) {
      // Add new item only in case if it not presented yet.
      this.items[disjointSetItem.getKey()] = disjointSetItem;
    }

    return this;
  }

  /**
   * Find set representation node.
   *
   * @param {*} itemValue
   * @return {(string|null)}
   */
  find(itemValue) {
    const templateDisjointItem = new DisjointSetItem(itemValue, this.keyCallback);

    // Try to find item itself;
    const requiredDisjointItem = this.items[templateDisjointItem.getKey()];

    if (!requiredDisjointItem) {
      return null;
    }

    return requiredDisjointItem.getRoot().getKey();
  }

  /**
   * Union by rank.
   *
   * @param {*} valueA
   * @param {*} valueB
   * @return {DisjointSet}
   */
  union(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error('One or two values are not in sets');
    }

    if (rootKeyA === rootKeyB) {
      // In case if both elements are already in the same set then just return its key.
      return this;
    }

    const rootA = this.items[rootKeyA];
    const rootB = this.items[rootKeyB];

    if (rootA.getRank() < rootB.getRank()) {
      // If rootB's tree is bigger then make rootB to be a new root.
      rootB.addChild(rootA);

      return this;
    }

    // If rootA's tree is bigger then make rootA to be a new root.
    rootA.addChild(rootB);

    return this;
  }

  /**
   * @param {*} valueA
   * @param {*} valueB
   * @return {boolean}
   */
  inSameSet(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error('One or two values are not in sets');
    }

    return rootKeyA === rootKeyB;
  }
}

Refereces

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/graph
https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/disjoint-set

Trie

Huy Do — Mon, 09 Nov 2020 03:02:36 +0000

Trie

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.

import TrieNode from './TrieNode';

// Character that we will use for trie tree root.
const HEAD_CHARACTER = '*';

export default class Trie {
  constructor() {
    this.head = new TrieNode(HEAD_CHARACTER);
  }

  /**
   * @param {string} word
   * @return {Trie}
   */
  addWord(word) {
    const characters = Array.from(word);
    let currentNode = this.head;

    for (let charIndex = 0; charIndex < characters.length; charIndex += 1) {
      const isComplete = charIndex === characters.length - 1;
      currentNode = currentNode.addChild(characters[charIndex], isComplete);
    }

    return this;
  }

  /**
   * @param {string} word
   * @return {Trie}
   */
  deleteWord(word) {
    const depthFirstDelete = (currentNode, charIndex = 0) => {
      if (charIndex >= word.length) {
        // Return if we're trying to delete the character that is out of word's scope.
        return;
      }

      const character = word[charIndex];
      const nextNode = currentNode.getChild(character);

      if (nextNode == null) {
        // Return if we're trying to delete a word that has not been added to the Trie.
        return;
      }

      // Go deeper.
      depthFirstDelete(nextNode, charIndex + 1);

      // Since we're going to delete a word let's un-mark its last character isCompleteWord flag.
      if (charIndex === (word.length - 1)) {
        nextNode.isCompleteWord = false;
      }

      // childNode is deleted only if:
      // - childNode has NO children
      // - childNode.isCompleteWord === false
      currentNode.removeChild(character);
    };

    // Start depth-first deletion from the head node.
    depthFirstDelete(this.head);

    return this;
  }

  /**
   * @param {string} word
   * @return {string[]}
   */
  suggestNextCharacters(word) {
    const lastCharacter = this.getLastCharacterNode(word);

    if (!lastCharacter) {
      return null;
    }

    return lastCharacter.suggestChildren();
  }

  /**
   * Check if complete word exists in Trie.
   *
   * @param {string} word
   * @return {boolean}
   */
  doesWordExist(word) {
    const lastCharacter = this.getLastCharacterNode(word);

    return !!lastCharacter && lastCharacter.isCompleteWord;
  }

  /**
   * @param {string} word
   * @return {TrieNode}
   */
  getLastCharacterNode(word) {
    const characters = Array.from(word);
    let currentNode = this.head;

    for (let charIndex = 0; charIndex < characters.length; charIndex += 1) {
      if (!currentNode.hasChild(characters[charIndex])) {
        return null;
      }

      currentNode = currentNode.getChild(characters[charIndex]);
    }

    return currentNode;
  }
}

Reference

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/trie

https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/trie/Trie.js

Heap, Priority Queue

Huy Do — Sun, 01 Nov 2020 23:55:52 +0000

Heap (data-structure)

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property described below.

In a min heap, if P is a parent node of C, then the key (the value) of P is less than or equal to the key of C.

In a max heap, the key of P is greater than or equal to the key of C

The node at the "top" of the heap with no parents is called the root node.

import Comparator from '../../utils/comparator/Comparator';

/**
 * Parent class for Min and Max Heaps.
 */
export default class Heap {
  /**
   * @constructs Heap
   * @param {Function} [comparatorFunction]
   */
  constructor(comparatorFunction) {
    if (new.target === Heap) {
      throw new TypeError('Cannot construct Heap instance directly');
    }

    // Array representation of the heap.
    this.heapContainer = [];
    this.compare = new Comparator(comparatorFunction);
  }

  /**
   * @param {number} parentIndex
   * @return {number}
   */
  getLeftChildIndex(parentIndex) {
    return (2 * parentIndex) + 1;
  }

  /**
   * @param {number} parentIndex
   * @return {number}
   */
  getRightChildIndex(parentIndex) {
    return (2 * parentIndex) + 2;
  }

  /**
   * @param {number} childIndex
   * @return {number}
   */
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  /**
   * @param {number} childIndex
   * @return {boolean}
   */
  hasParent(childIndex) {
    return this.getParentIndex(childIndex) >= 0;
  }

  /**
   * @param {number} parentIndex
   * @return {boolean}
   */
  hasLeftChild(parentIndex) {
    return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
  }

  /**
   * @param {number} parentIndex
   * @return {boolean}
   */
  hasRightChild(parentIndex) {
    return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
  }

  /**
   * @param {number} parentIndex
   * @return {*}
   */
  leftChild(parentIndex) {
    return this.heapContainer[this.getLeftChildIndex(parentIndex)];
  }

  /**
   * @param {number} parentIndex
   * @return {*}
   */
  rightChild(parentIndex) {
    return this.heapContainer[this.getRightChildIndex(parentIndex)];
  }

  /**
   * @param {number} childIndex
   * @return {*}
   */
  parent(childIndex) {
    return this.heapContainer[this.getParentIndex(childIndex)];
  }

  /**
   * @param {number} indexOne
   * @param {number} indexTwo
   */
  swap(indexOne, indexTwo) {
    const tmp = this.heapContainer[indexTwo];
    this.heapContainer[indexTwo] = this.heapContainer[indexOne];
    this.heapContainer[indexOne] = tmp;
  }

  /**
   * @return {*}
   */
  peek() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    return this.heapContainer[0];
  }

  /**
   * @return {*}
   */
  poll() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    if (this.heapContainer.length === 1) {
      return this.heapContainer.pop();
    }

    const item = this.heapContainer[0];

    // Move the last element from the end to the head.
    this.heapContainer[0] = this.heapContainer.pop();
    this.heapifyDown();

    return item;
  }

  /**
   * @param {*} item
   * @return {Heap}
   */
  add(item) {
    this.heapContainer.push(item);
    this.heapifyUp();
    return this;
  }

  /**
   * @param {*} item
   * @param {Comparator} [comparator]
   * @return {Heap}
   */
  remove(item, comparator = this.compare) {
    // Find number of items to remove.
    const numberOfItemsToRemove = this.find(item, comparator).length;

    for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
      // We need to find item index to remove each time after removal since
      // indices are being changed after each heapify process.
      const indexToRemove = this.find(item, comparator).pop();

      // If we need to remove last child in the heap then just remove it.
      // There is no need to heapify the heap afterwards.
      if (indexToRemove === (this.heapContainer.length - 1)) {
        this.heapContainer.pop();
      } else {
        // Move last element in heap to the vacant (removed) position.
        this.heapContainer[indexToRemove] = this.heapContainer.pop();

        // Get parent.
        const parentItem = this.parent(indexToRemove);

        // If there is no parent or parent is in correct order with the node
        // we're going to delete then heapify down. Otherwise heapify up.
        if (
          this.hasLeftChild(indexToRemove)
          && (
            !parentItem
            || this.pairIsInCorrectOrder(parentItem, this.heapContainer[indexToRemove])
          )
        ) {
          this.heapifyDown(indexToRemove);
        } else {
          this.heapifyUp(indexToRemove);
        }
      }
    }

    return this;
  }

  /**
   * @param {*} item
   * @param {Comparator} [comparator]
   * @return {Number[]}
   */
  find(item, comparator = this.compare) {
    const foundItemIndices = [];

    for (let itemIndex = 0; itemIndex < this.heapContainer.length; itemIndex += 1) {
      if (comparator.equal(item, this.heapContainer[itemIndex])) {
        foundItemIndices.push(itemIndex);
      }
    }

    return foundItemIndices;
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.heapContainer.length;
  }

  /**
   * @return {string}
   */
  toString() {
    return this.heapContainer.toString();
  }

  /**
   * @param {number} [customStartIndex]
   */
  heapifyUp(customStartIndex) {
    // Take the last element (last in array or the bottom left in a tree)
    // in the heap container and lift it up until it is in the correct
    // order with respect to its parent element.
    let currentIndex = customStartIndex || this.heapContainer.length - 1;

    while (
      this.hasParent(currentIndex)
      && !this.pairIsInCorrectOrder(this.parent(currentIndex), this.heapContainer[currentIndex])
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  /**
   * @param {number} [customStartIndex]
   */
  heapifyDown(customStartIndex = 0) {
    // Compare the parent element to its children and swap parent with the appropriate
    // child (smallest child for MinHeap, largest child for MaxHeap).
    // Do the same for next children after swap.
    let currentIndex = customStartIndex;
    let nextIndex = null;

    while (this.hasLeftChild(currentIndex)) {
      if (
        this.hasRightChild(currentIndex)
        && this.pairIsInCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))
      ) {
        nextIndex = this.getRightChildIndex(currentIndex);
      } else {
        nextIndex = this.getLeftChildIndex(currentIndex);
      }

      if (this.pairIsInCorrectOrder(
        this.heapContainer[currentIndex],
        this.heapContainer[nextIndex],
      )) {
        break;
      }

      this.swap(currentIndex, nextIndex);
      currentIndex = nextIndex;
    }
  }

  /**
   * Checks if pair of heap elements is in correct order.
   * For MinHeap the first element must be always smaller or equal.
   * For MaxHeap the first element must be always bigger or equal.
   *
   * @param {*} firstElement
   * @param {*} secondElement
   * @return {boolean}
   */
  /* istanbul ignore next */
  pairIsInCorrectOrder(firstElement, secondElement) {
    throw new Error(`
      You have to implement heap pair comparision method
      for ${firstElement} and ${secondElement} values.
    `);
  }
}

Priority Queue

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.


import MinHeap from '../heap/MinHeap';
import Comparator from '../../utils/comparator/Comparator';

// It is the same as min heap except that when comparing two elements
// we take into account its priority instead of the element's value.
export default class PriorityQueue extends MinHeap {
  constructor() {
    // Call MinHip constructor first.
    super();

    // Setup priorities map.
    this.priorities = new Map();

    // Use custom comparator for heap elements that will take element priority
    // instead of element value into account.
    this.compare = new Comparator(this.comparePriority.bind(this));
  }

  /**
   * Add item to the priority queue.
   * @param {*} item - item we're going to add to the queue.
   * @param {number} [priority] - items priority.
   * @return {PriorityQueue}
   */
  add(item, priority = 0) {
    this.priorities.set(item, priority);
    super.add(item);
    return this;
  }

  /**
   * Remove item from priority queue.
   * @param {*} item - item we're going to remove.
   * @param {Comparator} [customFindingComparator] - custom function for finding the item to remove
   * @return {PriorityQueue}
   */
  remove(item, customFindingComparator) {
    super.remove(item, customFindingComparator);
    this.priorities.delete(item);
    return this;
  }

  /**
   * Change priority of the item in a queue.
   * @param {*} item - item we're going to re-prioritize.
   * @param {number} priority - new item's priority.
   * @return {PriorityQueue}
   */
  changePriority(item, priority) {
    this.remove(item, new Comparator(this.compareValue));
    this.add(item, priority);
    return this;
  }

  /**
   * Find item by ite value.
   * @param {*} item
   * @return {Number[]}
   */
  findByValue(item) {
    return this.find(item, new Comparator(this.compareValue));
  }

  /**
   * Check if item already exists in a queue.
   * @param {*} item
   * @return {boolean}
   */
  hasValue(item) {
    return this.findByValue(item).length > 0;
  }

  /**
   * Compares priorities of two items.
   * @param {*} a
   * @param {*} b
   * @return {number}
   */
  comparePriority(a, b) {
    if (this.priorities.get(a) === this.priorities.get(b)) {
      return 0;
    }
    return this.priorities.get(a) < this.priorities.get(b) ? -1 : 1;
  }

  /**
   * Compares values of two items.
   * @param {*} a
   * @param {*} b
   * @return {number}
   */
  compareValue(a, b) {
    if (a === b) {
      return 0;
    }
    return a < b ? -1 : 1;
  }
}

References
https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/heap
https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/priority-queue

Queue, Stack, Double Linked List

Huy Do — Mon, 26 Oct 2020 00:29:27 +0000

Queue

In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.

Representation of a FIFO (first in, first out) queue

Stack

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations:

push, which adds an element to the collection, and
pop, which removes the most recently added element that was not yet removed.

The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out). Additionally, a peek operation may give access to the top without modifying the stack. The name "stack" for this type of structure comes from the analogy to a set of physical items stacked on top of each other, which makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first.

Double Linked List

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.

Referenes:

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/queue

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/stack

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/doubly-linked-list

Trees

Huy Do — Sun, 18 Oct 2020 20:17:38 +0000

Depth-First Search (DFS)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

/**
 * @typedef {Object} TraversalCallbacks
 *
 * @property {function(node: BinaryTreeNode, child: BinaryTreeNode): boolean} allowTraversal
 * - Determines whether DFS should traverse from the node to its child.
 *
 * @property {function(node: BinaryTreeNode)} enterNode - Called when DFS enters the node.
 *
 * @property {function(node: BinaryTreeNode)} leaveNode - Called when DFS leaves the node.
 */

/**
 * Extend missing traversal callbacks with default callbacks.
 *
 * @param {TraversalCallbacks} [callbacks] - The object that contains traversal callbacks.
 * @returns {TraversalCallbacks} - Traversal callbacks extended with defaults callbacks.
 */
function initCallbacks(callbacks = {}) {
  // Init empty callbacks object.
  const initiatedCallbacks = {};

  // Empty callback that we will use in case if user didn't provide real callback function.
  const stubCallback = () => {};
  // By default we will allow traversal of every node
  // in case if user didn't provide a callback for that.
  const defaultAllowTraversalCallback = () => true;

  // Copy original callbacks to our initiatedCallbacks object or use default callbacks instead.
  initiatedCallbacks.allowTraversal = callbacks.allowTraversal || defaultAllowTraversalCallback;
  initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback;
  initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback;

  // Returned processed list of callbacks.
  return initiatedCallbacks;
}

/**
 * Recursive depth-first-search traversal for binary.
 *
 * @param {BinaryTreeNode} node - binary tree node that we will start traversal from.
 * @param {TraversalCallbacks} callbacks - the object that contains traversal callbacks.
 */
export function depthFirstSearchRecursive(node, callbacks) {
  // Call the "enterNode" callback to notify that the node is going to be entered.
  callbacks.enterNode(node);

  // Traverse left branch only if case if traversal of the left node is allowed.
  if (node.left && callbacks.allowTraversal(node, node.left)) {
    depthFirstSearchRecursive(node.left, callbacks);
  }

  // Traverse right branch only if case if traversal of the right node is allowed.
  if (node.right && callbacks.allowTraversal(node, node.right)) {
    depthFirstSearchRecursive(node.right, callbacks);
  }

  // Call the "leaveNode" callback to notify that traversal
  // of the current node and its children is finished.
  callbacks.leaveNode(node);
}

/**
 * Perform depth-first-search traversal of the rootNode.
 * For every traversal step call "allowTraversal", "enterNode" and "leaveNode" callbacks.
 * See TraversalCallbacks type definition for more details about the shape of callbacks object.
 *
 * @param {BinaryTreeNode} rootNode - The node from which we start traversing.
 * @param {TraversalCallbacks} [callbacks] - Traversal callbacks.
 */
export default function depthFirstSearch(rootNode, callbacks) {
  // In case if user didn't provide some callback we need to replace them with default ones.
  const processedCallbacks = initCallbacks(callbacks);

  // Now, when we have all necessary callbacks we may proceed to recursive traversal.
  depthFirstSearchRecursive(rootNode, processedCallbacks);
}

Breadth-First Search (BFS)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.

import Queue from '../../../data-structures/queue/Queue';

/**
 * @typedef {Object} Callbacks
 * @property {function(node: BinaryTreeNode, child: BinaryTreeNode): boolean} allowTraversal -
 *   Determines whether DFS should traverse from the node to its child.
 * @property {function(node: BinaryTreeNode)} enterNode - Called when DFS enters the node.
 * @property {function(node: BinaryTreeNode)} leaveNode - Called when DFS leaves the node.
 */

/**
 * @param {Callbacks} [callbacks]
 * @returns {Callbacks}
 */
function initCallbacks(callbacks = {}) {
  const initiatedCallback = callbacks;

  const stubCallback = () => {};
  const defaultAllowTraversal = () => true;

  initiatedCallback.allowTraversal = callbacks.allowTraversal || defaultAllowTraversal;
  initiatedCallback.enterNode = callbacks.enterNode || stubCallback;
  initiatedCallback.leaveNode = callbacks.leaveNode || stubCallback;

  return initiatedCallback;
}

/**
 * @param {BinaryTreeNode} rootNode
 * @param {Callbacks} [originalCallbacks]
 */
export default function breadthFirstSearch(rootNode, originalCallbacks) {
  const callbacks = initCallbacks(originalCallbacks);
  const nodeQueue = new Queue();

  // Do initial queue setup.
  nodeQueue.enqueue(rootNode);

  while (!nodeQueue.isEmpty()) {
    const currentNode = nodeQueue.dequeue();

    callbacks.enterNode(currentNode);

    // Add all children to the queue for future traversals.

    // Traverse left branch.
    if (currentNode.left && callbacks.allowTraversal(currentNode, currentNode.left)) {
      nodeQueue.enqueue(currentNode.left);
    }

    // Traverse right branch.
    if (currentNode.right && callbacks.allowTraversal(currentNode, currentNode.right)) {
      nodeQueue.enqueue(currentNode.right);
    }

    callbacks.leaveNode(currentNode);
  }
}

Refereneces:

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search

Trees and Searches

Huy Do — Sun, 11 Oct 2020 20:12:57 +0000

Depth-First Search (DFS)

Breadth-First Search (BFS)

Linear Search

In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list.

Complexity
Time Complexity: O(n) - since in worst case we're checking each element exactly once.

Jump Search

Like Binary Search, Jump Search (or Block Search) is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

For example, suppose we have an array arr[] of size n and block (to be jumped) of size m. Then we search at the indexes arr[0], arr[m], arr[2 * m], ..., arr[k * m] and so on. Once we find the interval arr[k * m] < x < arr[(k+1) * m], we perform a linear search operation from the index k * m to find the element x.

What is the optimal block size to be skipped? In the worst case, we have to do n/m jumps and if the last checked value is greater than the element to be searched for, we perform m - 1 comparisons more for linear search. Therefore the total number of comparisons in the worst case will be ((n/m) + m - 1). The value of the function ((n/m) + m - 1) will be minimum when m = √n. Therefore, the best step size is m = √n.

Complexity
Time complexity: O(√n) - because we do search by blocks of size √n.

Binary Search

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

Complexity
Time Complexity: O(log(n)) - since we split search area by two for every next iteration.

Interpolation Search

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values).

For example we have a sorted array of n uniformly distributed values arr[], and we need to write a function to search for a particular element x in the array.

Linear Search finds the element in O(n) time, Jump Search takes O(√ n) time and Binary Search take O(Log n) time.

The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.

To find the position to be searched, it uses following formula:

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))
arr[] - Array where elements need to be searched
x - Element to be searched
lo - Starting index in arr[]
hi - Ending index in arr[]

Complexity
Time complexity: O(log(log(n))

References
https://github.com/trekhleb/javascript-algorithms
https://www.bigocheatsheet.com/

Algorithms - Sorting

Huy Do — Sun, 04 Oct 2020 21:03:33 +0000

I will cover several popular sorting algorithms such as Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Merge Sort, Quicksort, Shellsort, Counting Sort, Radix Sort.

Bubble Sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order (ascending or descending arrangement). The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Selectin Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Heap Sort

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Merge Sort

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

Quick Sort

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays

Shellsort

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange

Counting Sort

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.

Because counting sort uses key values as indexes into an array, it is not a comparison sort, and the Ω(n log n) lower bound for comparison sorting does not apply to it. Bucket sort may be used for many of the same tasks as counting sort, with a similar time analysis; however, compared to counting sort, bucket sort requires linked lists, dynamic arrays or a large amount of preallocated memory to hold the sets of items within each bucket, whereas counting sort instead stores a single number (the count of items) per bucket.

Counting sorting works best when the range of numbers for each array element is very small.

Radix Sort

In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers.

Where does the name come from?

In mathematical numeral systems, the radix or base is the number of unique digits, including the digit zero, used to represent numbers in a positional numeral system. For example, a binary system (using numbers 0 and 1) has a radix of 2 and a decimal system (using numbers 0 to 9) has a radix of 10.

References:
https://github.com/trekhleb/javascript-algorithms
https://www.bigocheatsheet.com/

Hash Tables

Huy Do — Sun, 27 Sep 2020 21:15:29 +0000

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found

Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions must be accommodated in some way.

Hash collision resolved by separate chaining.

Crucial Terms

Key: A unique identifier for each value.
Value: The information we want to access (generally)
Note: You don't have to worry about the following terms to simply use a hash table, but you do need to know them to implement one (or to answer interview questions about how they're implemented!).
Bucket: Depending on the implementation, this is either where the value data is stored, or a pointer to the value data is stored.
Sparseness: The property that the number of actual keys used is much smaller than the possible keys used. (e.g. there is an infinite number of strings that could be email addresses and only a finite number in use.)
Hash or hash-function: A function h(key) that takes the key and returns an index for the "bucket" containing the information that we want. The number of buckets is much smaller than the number of possible keys. Note this means that multiple keys are assigned to the same bucket. If there are K possible keys and B buckets, the average number of possible keys assigned to a given bucket is K/B.
Collision: When two keys k1 and k2 have the same hash (i.e. h(k1) == h(k2)) we say the keys collide, so they are assigned to the same bucket. There are different ways of storing different elements whose keys have the same hash.
Good hash: A good hash is a hash function that provides few collisions. Unfortunately, there is no universally good hash; the hash function has to be good for the distribution of keys that actually occur in your problem.

Strengths & Weaknesses

Hash tables combine random access ability with quick insertion and deletion, which makes it an extremely flexible and useful data structure. If you’re doing something other than storing keys and values, or if you need to sort elements or iterate efficiently through them, though, you should use a different data structure.

Strengths

Note: These features assume the hashtable is sparse.

Hash tables have extremely fast lookup by key (O(1)).
Insertion and deletion of data is also quick (O(1)).
In a hash table, you can use the keys as the data, and use that to check if we've seen an element before. A hash table used this way is usually called a set.

Weaknesses

Hash tables have no notion of order.
Hash tables cannot match "nearby" keys or keys that share the same prefix. So a hash table wouldn't be a good choice for checking for words that began with a certain prefix (a trie would be a better choice in that case).
Lookup by value (instead of by key) is O(n).
A hash table loses its strengths when the amount of data in a single bucket becomes large. Lookup becomes O(B), where B is the number of things in the bucket.

In Interviews, Use Hash Tables When...

There is a unique identifier that you use for lookup.
Examples:
Caller ID: Phone numbers are unique and can be used as a key to quickly retrieve a person. Note that we would not use a hash table that found a phone number given a person's name, since many people have the same name.
Car owner information: Using the license plate as a key, you can look up the owner of the car (the value).
You need to quickly determine if an element belongs to a collection. In these cases, you can represent the collection as a hash table with the elements as keys.
Example:
A Scrabble checker: If we want to determine if word is allowed, we could create a hash table valid_words where the keys were the words. We would set valid_words[w] = 1 for all valid words, so checking if word in valid_words is an O(1) operation.
You're dealing with problems about invariants.
Example:
To see if a word has an anagram, we can sort the letters of the string, and use it as a key in a hash table. (This method yields the same key for any two words that are anagrams of one another). The value can be a dummy value (if you're interested in the "yes/no" question of whether a word has an anagram) or an array of strings with the same key (if you are looking for the actual words).

Operation/ Descritpion /Time complexity /Mutates strutures
hash[key] = value : Add a new (key,value) pair to has table: O(1) : Yes
del hash[key] : Remove (key, value) from hash table: O(1) : Yes
key in hash: Lookup whenther key is in has table: O(1) : Yes

Note: Lookup by value is not supported directly in a hash table. Instead, you'd iterate through all the keys and check for the value you were looking for (an O(n) procedure).

References:
Hash Table
Hash Tables

JavaScript Algorithms and Data Structures

Huy Do — Sun, 20 Sep 2020 19:39:22 +0000

Data Structures

A data structure is a particular way of organizing and sorting data in a computer so that it can be accessed and modified efficiently. It's a collection of data values, the relationship between them, and function and operations that can be applied to the data. Here is the list. Each algorithm and data structure has its own separate README with related explanations and JavaScript based examples.
B: Beginner; A: Advanced. For example: B Linked List.

B Linked List
B Doubly Linked List
B Queue
B Stack
B Hash Table
B Heap - max and min heap versions
B Priority Queue
A Trie
A Tree: A Binary Search Tree, A AVL Tree, A Red-Black Tree, A Segment Tree - with min/max/sum range queries examples, A Fenwick Tree (Binary Indexed Tree)
A Graph (both directed and undirected)
A Disjoint Set
A Bloom Filter

Algorithms

An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.
Here are the list: B = Beginner; A = Advanced

Math

B Bit Manipulation - set/get/update/clear bits, multiplication/division by two, make negative etc.
B Factorial
B Fibonacci Number - classic and closed-form versions
B Primality Test (trial division method)
B Euclidean Algorithm - calculate the Greatest Common Divisor (GCD)
B Least Common Multiple (LCM)
B Sieve of Eratosthenes - finding all prime numbers up to any given limit
B Is Power of Two - check if the number is power of two (naive and bitwise algorithms)
B Pascal's Triangle
B Complex Number - complex numbers and basic operations with them
B Radian & Degree - radians to degree and backwards conversion
B Fast Powering
A Integer Partition
A Square Root - Newton's method
A Liu Hui π Algorithm - approximate π calculations based on N-gons
A Discrete Fourier Transform - decompose a function of time (a signal) into the frequencies that make it up

Sets

B Cartesian Product - product of multiple sets
B Fisher–Yates Shuffle - random permutation of a finite sequence
A Power Set - all subsets of a set (bitwise and backtracking solutions)
A Permutations (with and without repetitions)
A Combinations (with and without repetitions)
A Longest Common Subsequence (LCS)
A Longest Increasing Subsequence
A Shortest Common Supersequence (SCS)
A Knapsack Problem - "0/1" and "Unbound" ones
A Maximum Subarray - "Brute Force" and "Dynamic Programming" (Kadane's) versions
A Combination Sum - find all combinations that form specific sum

Strings

B Hamming Distance - number of positions at which the symbols are different A Levenshtein Distance - minimum edit distance between two sequences
A Knuth–Morris–Pratt Algorithm (KMP Algorithm) - substring search (pattern matching)
A Z Algorithm - substring search (pattern matching)
A Rabin Karp Algorithm - substring search
A Longest Common Substring
A Regular Expression Matching

Searches

B Linear Search
B Jump Search (or Block Search) - search in sorted array
B Binary Search - search in sorted array
B Interpolation Search - search in uniformly distributed sorted array

Sorting

B Bubble Sort
B Selection Sort
B Insertion Sort
B Heap Sort
B Merge Sort
B Quicksort - in-place and non-in-place implementations
B Shellsort
B Counting Sort
B Radix Sort

Linked Lists

B Straight Traversal
B Reverse Traversal

Trees

B Depth-First Search (DFS)
B Breadth-First Search (BFS)

Graphs

B Depth-First Search (DFS)
B Breadth-First Search (BFS)
B Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
A Dijkstra Algorithm - finding shortest paths to all graph vertices from single vertex
A Bellman-Ford Algorithm - finding shortest paths to all graph vertices from single vertex
A Floyd-Warshall Algorithm - find shortest paths between all pairs of vertices
A Detect Cycle - for both directed and undirected graphs (DFS and Disjoint Set based versions)
A Prim’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
A Topological Sorting - DFS method
A Articulation Points - Tarjan's algorithm (DFS based)
A Bridges - DFS based algorithm
A Eulerian Path and Eulerian Circuit - Fleury's algorithm - Visit every edge exactly once
A Hamiltonian Cycle - Visit every vertex exactly once
A Strongly Connected Components - Kosaraju's algorithm
A Travelling Salesman Problem - shortest possible route that visits each city and returns to the origin city

Cryptography

B Polynomial Hash - rolling hash function based on polynomial
B Caesar Cipher - simple substitution cipher

Machine Learning

B NanoNeuron - 7 simple JS functions that illustrate how machines can actually learn (forward/backward propagation)

Uncategorized

B Tower of Hanoi
B Square Matrix Rotation - in-place algorithm
B Jump Game - backtracking, dynamic programming (top-down + bottom-up) and greedy examples
B Unique Paths - backtracking, dynamic programming and Pascal's Triangle based examples
B Rain Terraces - trapping rain water problem (dynamic programming and brute force versions)
B Recursive Staircase - count the number of ways to reach to the top (4 solutions)
A N-Queens Problem
A Knight's Tour

Algorithms by Paradigm

An algorithmic paradigm is a generic method or approach which underlies the design of a class of algorithms. It is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.

Brute Force - look at all the possibilities and selects the best solution

B Linear Search
B Rain Terraces - trapping rain water problem
B Recursive Staircase - count the number of ways to reach to the top
A Maximum Subarray
A Travelling Salesman Problem - shortest possible route that visits each city and returns to the origin city
A Discrete Fourier Transform - decompose a function of time (a signal) into the frequencies that make it up

Greedy - choose the best option at the current time, without any consideration for the future

B Jump Game
A Unbound Knapsack Problem
A Dijkstra Algorithm - finding shortest path to all graph vertices
A Prim’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
A Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph

Divide and Conquer - divide the problem into smaller parts and then solve those parts

B Binary Search
B Tower of Hanoi
B Pascal's Triangle
B Euclidean Algorithm - calculate the Greatest Common Divisor (GCD)
B Merge Sort
B Quicksort
B Tree Depth-First Search (DFS)
B Graph Depth-First Search (DFS)
B Jump Game
B Fast Powering
A Permutations (with and without repetitions)
A Combinations (with and without repetitions)

Dynamic Programming - build up a solution using previously found sub-solutions

B Fibonacci Number
B Jump Game
B Unique Paths
B Rain Terraces - trapping rain water problem
B Recursive Staircase - count the number of ways to reach to the top
A Levenshtein Distance - minimum edit distance between two sequences
A Longest Common Subsequence (LCS)
A Longest Common Substring
A Longest Increasing Subsequence
A Shortest Common Supersequence
A 0/1 Knapsack Problem
A Integer Partition
A Maximum Subarray
A Bellman-Ford Algorithm - finding shortest path to all graph vertices
A Floyd-Warshall Algorithm - find shortest paths between all pairs of vertices
A Regular Expression Matching

Backtracking

Similarly to brute force, try to generate all possible solutions, but each time you generate next solution you test if it satisfies all conditions, and only then continue generating subsequent solutions. Otherwise, backtrack, and go on a different path of finding a solution. Normally the DFS traversal of state-space is being used.

B Jump Game
B Unique Paths
B Power Set - all subsets of a set
A Hamiltonian Cycle - Visit every vertex exactly once
A N-Queens Problem
A Knight's Tour
A Combination Sum - find all combinations that form specific sum

Branch and Bound

Remember the lowest-cost solution found at each stage of the backtracking search, and use the cost of the lowest-cost solution found so far as a lower bound on the cost of a least-cost solution to the problem, in order to discard partial solutions with costs larger than the lowest-cost solution found so far. Normally BFS traversal in combination with DFS traversal of state-space tree is being used.

References:
JavaScript Algorithms and Data Structures
trekhleb/javascript-algorithms

Linked List

Huy Do — Tue, 15 Sep 2020 00:32:27 +0000

Linked List

A linked list is an ordered collection of data elements. A data element can be represented as a node in a linked list. Each node consists of two parts: data & pointer to the next node.
Unlike arrays, data elements are not stored at contiguous locations. The data elements or nodes are linked using pointers, hence called a linked list.

Linked List Properties

Successive nodes are connected by pointers.
The last node points to null.
A head pointer is maintained which points to the first node of the list.
A linked list can grow and shrink in size during execution of the program.
It can be made just as long as required.
It allocates memory as the list grows. Unlike arrays, which have a fixed size. Therefore, the upper limit on the number of elements must be known in advance.
In contrast to an array, which stores data contiguously in memory, a linked list can easily insert or remove nodes from the list without reorganization of the entire data structure.
Random access of data elements is not allowed. Nodes must be accessed sequentially starting from the first one. Therefore, search operation is slow on a linked list.
It uses more memory than arrays because of the storage used by their pointers.

Types of Linked List

The popular types: singly, doubly and circular.

Single Linked list

A singly linked list is collection of nodes wherein each node has 2 parts: data and a pointer to the next node. The list terminates with a node pointing at null.
Main operations on a linked list are: insert and delete.

Define Node Class

class Node{
    constructor(data, next = null){
        this.data = data,
        this.next = next
    }
}

The instance of the Node class is formed, the constructor function will be called to initialize the object with two properties, data, and a pointer named next. The pointer next is initialized with a default value of null, in case no value is passed as an argument.

The linked list class which maintains the head pointer of the list.

class LinkedList{
    constructor(){
        this.head = null;
    }
}

A LinkedList class is defined. When an instance of the LinkedList class is formed, the constructor function will be called to initialize the object with a property, head. The head pointer is assigned a value of null because when a linked list object is initially created it does not contain any nodes. It is when we add our first node to the linked list, we will assign it to the head pointer.

Create an instance of the LinkedList class

// A list object is created with a property head, currently pointing at null

let list = new LinkedList();

Insert operation on a singly linked list

An insert operation will insert a node into the list. There can be three cases for the insert operation.

Inserting a new node before the head (at the beginning of the list).
Inserting a new node after the tail (i.e. at the end of the list).
Inserting a new node in the middle of the list (at a given random position).

Inserting a node at the beginning of the singly linked list.

In this case, a new node is added before the current head node. To fulfill this operation we will first create a node. The newly created node will be having two properties as defined in the constructor function of the Node class, data and next.

LinkedList.prototype.insertAtBeginning = function(data){
// A newNode object is created with property data and next = null
    let newNode = new Node(data);
// The pointer next is assigned head pointer so that both pointers now point at the same node.
    newNode.next = this.head;
// As we are inserting at the beginning the head pointer needs to now point at the newNode. 

    this.head = newNode;
    return this.head;
}

Inserting a node at the end of the singly linked list.

In this case, a new node is added at the end of the list. To implement this operation we will have to traverse through the list to find the tail node and modify the tail’s next pointer to point to the newly created node instead of null.
Initially, the list is empty and the head points to null.

LinkedList.prototype.insertAtEnd = function(data){
// A newNode object is created with property data and next=null

    let newNode = new Node(data);
// When head = null i.e. the list is empty, then head itself will point to the newNode.
    if(!this.head){
        this.head = newNode;
        return this.head;
    }
// Else, traverse the list to find the tail (the tail node will initially be pointing at null), and update the tail's next pointer.
   let tail = this.head;
   while(tail.next !== null){
        tail = tail.next;
   }
   tail.next = newNode;
   return this.head;
}

Inserting a node at given random position in a singly linked list

To implement this operation we will have to traverse the list until we reach the desired position node. We will then assign the newNode’s next pointer to the next node to the position node. The position node’s next pointer can then be updated to point to the newNode.

// A helper function getAt() is defined to get to the desired position. This function can also be later used for performing delete operation from a given position.
    LinkedList.prototype.getAt = function(index){
        let counter = 0;
        let node = this.head;
        while (node) {
            if (counter === index) {
               return node;
            }
            counter++;
            node = node.next;
        }
        return null;
    }
// The insertAt() function contains the steps to insert a node at a given index.
    LinkedList.prototype.insertAt = function(data, index){
// if the list is empty i.e. head = null
        if (!this.head) {
            this.head = new Node(data);
            return;
        }
// if new node needs to be inserted at the front of the list i.e. before the head. 
        if (index === 0) {
           this.head = new Node(data, this.head);
           return;
        }
// else, use getAt() to find the previous node.
        const previous = this.getAt(index - 1);
        let newNode = new Node(data);
        newNode.next = previous.next;
        previous.next = newNode;       

        return this.head
   }

Delete operation on a singly linked list

A delete operation will delete a node from the list. There can be three cases for the delete operation.

Deleting the first node.
Deleting the last node.
Deleting a node from the middle of the list (at a given random position).

Deleting the first node in a singly linked list

The first node in a linked list is pointed by the head pointer. To perform a delete operation at the beginning of the list, we will have to make the next node to the head node as the new head.

LinkedList.prototype.deleteFirstNode = function(){
    if(!this.head){
        return;
    }
    this.head = this.head.next;
    return this.head;
}

Deleting the last node in a singly linked list

To remove the last node from the list, we will first have to traverse the list to find the last node and at the same time maintain an extra pointer to point at the node before the last node. To delete the last node, we will then set the next pointer of the node before the last node to null.

LinkedList.prototype.deleteLastNode = function(){
    if(!this.head){
        return null;
    }
    // if only one node in the list
    if(!this.head.next){
        this.head = null;
        return;
    }
   let previous = this.head;
   let tail = this.head.next;

   while(tail.next !== null){
       previous = tail;
       tail = tail.next;
   }

   previous.next = null;
   return this.head;
}

Deleting a node from given random position in a singly linked list

Similar to the above case, we will first have to traverse the list to find the desired node to be deleted and at the same time maintain an extra pointer to point at the node before the desired node.

LinkedList.prototype.deleteAt = function(index){
// when list is empty i.e. head = null
    if (!this.head) {
         this.head = new Node(data);
         return;
     }
// node needs to be deleted from the front of the list i.e. before the head.
    if (index === 0) {
        this.head = this.head.next;
        return;
    }
// else, use getAt() to find the previous node.
    const previous = this.getAt(index - 1);

    if (!previous || !previous.next) {
        return;
    }

    previous.next = previous.next.next;     
    return this.head
}

Deleting the singly linked list

Now, lets delete the complete linked list. This can be done by just one single line of code.

LinkedList.prototype.deleteList = function(){
    this.head = null;
}

References:
Linked Lists in JavaScript (ES6 code)
What's a Linked List, Anyway?[Part 1]