FE Algorithms

bfs.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

export function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
export function sortedArrayToBST(nums) {
    return convert(0, nums.length - 1)
    /**
     * @param {number} i
     * @param {number} j
     * @return {TreeNode}
     */
    function convert(i, j) {
        if (i > j) return null;
        const mid = parseInt((i+j)/2);
        const node = new TreeNode(nums[mid]);
        node.left = convert(i, mid - 1);
        node.right = convert(mid + 1, j);
        return node;
    }
};

const tree = sortedArrayToBST([5, 4, -1, 0, 2, 1, 3]) // ?

function traverseBFS(root, cb) {
  let depth = 0;
  const queue = [[root, 0, 'root']];
  while(queue.length) {
    let [curr, depth, hand] = queue.shift();
    cb(curr.val, depth++, hand);
    if (curr.left) queue.push([curr.left, depth, 'left']);
    if (curr.right) queue.push([curr.right, depth, 'right']);
  }
}

traverseBFS(tree, (val, depth, hand) => {
  console.log(val)
  console.log({val, depth, hand})
})

binary-search.js

let binarySearch = function (arr, x) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    if (arr[mid] === x) {
      return true;
    } else if (arr[mid] < x) {
      start = mid + 1;
    } else { 
      end = mid - 1;
    }
  }

  return false;
}

dfs.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

export function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
export function sortedArrayToBST(nums) {
    return convert(0, nums.length - 1)
    /**
     * @param {number} i
     * @param {number} j
     * @return {TreeNode}
     */
    function convert(i, j) {
        if (i > j) return null;
        const mid = parseInt((i+j)/2);
        const node = new TreeNode(nums[mid]);
        node.left = convert(i, mid - 1);
        node.right = convert(mid + 1, j);
        return node;
    }
};

const tree = sortedArrayToBST([5, 4, -1, 0, 2, 1, 3]) // ?

function traverseDFS(root, cb) {
  let depth = 0;
  let stack = [[root, 0, 'root']];
  while(stack.length) {
    let [curr, depth, hand] = stack.shift();
    cb(curr.val, depth++, hand);
    if (curr.left) stack.unshift([curr.left, depth, 'left'])
    if (curr.right) stack.unshift([curr.right, depth, 'right'])
  }
}

traverseDFS(tree, (val, depth, hand) => {
  console.log(val)
  console.log({ val, depth, hand })
})

max-heap-sort.js

function swap(arr, a, b) {
  [arr[a], arr[b]] = [arr[b], arr[a]];
}

function maxHeap(arr, parentIndex, heapSize) {
  const lIndex = 2 * parentIndex + 1; 
  const rIndex = 2 * parentIndex + 2;
  let largestIndex = parentIndex;

  // if left child is larger than parent set largestIndex for future swap with parent
  if (lIndex < heapSize && arr[lIndex] > arr[largestIndex]) {
    largestIndex = lIndex
  }

  // if right child is larger than parent set largestIndex for future swap with parent
  if (rIndex < heapSize && arr[rIndex] > arr[largestIndex]) {
    largestIndex = rIndex;
  }

  // if the largest index is not the parent index then we need to swap largest with parent;
  if (largestIndex !== parentIndex) {
    // swap largestIndex and parentIndex
    swap(arr, parentIndex, largestIndex);
    // recurse starting at the largestIndex which is our current position in the heap.
    maxHeap(arr, largestIndex, heapSize); 
  }
}

function buildMaxHeap(arr) {
  for (i = Math.floor(arr.length / 2); i >= 0; i--) {
    maxHeap(arr, i, arr.length);
  }
  return arr;
}

function heapSort(arr) {
  let length = arr.length;
  const size = length - 1;
  buildMaxHeap(arr);
  for (var i = size; i > 0; i--) {
    swap(arr, 0, i);
    length--;
    maxHeap(arr, 0, length);
  }
  return arr;
}

heapSort([2, 5, 1, 0, 4]) // ?

merge-sort.js

function merge(arrA, arrB) {
  const merged = [];
  const mergeA = () => merged.push(arrA.shift());
  const mergeB = () => merged.push(arrB.shift());

  while(arrA.length && arrB.length) arrA[0] < arrB[0] ? mergeA() : mergeB();
  while(arrA.length) mergeA();
  while(arrB.length) mergeB();

  return merged;
}

function mergeSort(arr) {
  if(arr.length < 2) return arr;

  const midIndex = Math.floor(arr.length/2);
  const left = mergeSort(arr.slice(0, midIndex));
  const right = mergeSort(arr.slice(midIndex, arr.length));

  return merge(left, right);
}

quick-sort.js

function quickSort(arr) {
  if(arr.length < 2) return arr;
  const pivot = arr[0];
  const left = [];
  const right = [];

  for(i=1;i<arr.length;i++){
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }

  return [...quickSort(left), pivot, ...quickSort(right)]
}