Algorithms

Question 1

How do you implement a depth-first search?

Answer 1

A depth-first search burrows down to the end of each branch as it moves through the tree.

Tree.prototype.traverseDF = function(callback) {

    // this is a recurse and immediately-invoking function 
    (function recurse(currentNode) {
        // step 2
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // step 3
            recurse(currentNode.children[i]);
        }

        // step 4
        callback(currentNode);

        // step 1
    })(this._root);
};

Question 2

How do you implement a breadth-first search?

Answer 2

A breadth-first search prioritizes operations on nodes higher in the tree. This is useful if information about higher branches might allow you to prune visiting lower branches.

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();

queue.enqueue(this._root);

    // Array.shift() - we want the first item queued, not a stack
    currentNode = queue.dequeue();

    while(currentNode){
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            queue.enqueue(currentNode.children[i]);
        }

    callback(currentNode);
    currentNode = queue.dequeue();
} };

Question 3

How would you implement a binary search?

Answer 3

Performs a binary search on the host array. This method can either be injected into Array.prototype or called with a specified scope like this:
binaryIndexOf.call(someArray, searchElement);

@param {*} searchElement The item to search for within the array.
@return {Number} The index of the element which defaults to -1 when not found.

function binaryIndexOf(searchElement) {
    'use strict';

    var minIndex = 0;
    var maxIndex = this.length - 1;
    var currentIndex;
    var currentElement;

while (minIndex <= maxIndex) {
    currentIndex = Math.floor((minIndex + maxIndex) / 2) | 0;
    currentElement = this[currentIndex];

        if (currentElement < searchElement) {
            minIndex = currentIndex + 1;
        }
        else if (currentElement > searchElement) {
            maxIndex = currentIndex - 1;
        }
        else {
            return currentIndex;
        }
    }

return -1; }

Question 4

What is the time complexity of a binary search?

Answer 4

O(log N)

Question 5

What is the time complexity of indexOf?

Answer 5

O(N)

Question 6

How would you implement a merge sort?

Answer 6

A merge sort recursively divides an array into sub arrays, all the way down to 1 element. Then it uses a merge function that takes sorted arrays and picks the lowest number off the front of each to add to the output array.

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];

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

  var middle = parseInt(arr.length / 2);
  var left   = arr.slice(0, middle);
  var right  = arr.slice(middle, arr.length);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  var result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());

return result;
}

Question 7

What is the time complexity of a merge sort?

Answer 7

O(N log N)

Question 8

What is the space complexity of a merge sort?

Answer 8

O(N)

Question 9

How do you implement a quicksort?

Answer 9

A quick sort takes the last element of a partition as the pivot and it’s “pivot value” is used for comparison. You then run through the partition and take everything lower than the pivot value and put it in a stack at the front of the partition. Finally, you move the pivot over as well onto that stack. You then return this new “pivot index” and do it again on the two new partitions.

function quickSort(arr, left, right){
var len = arr.length,
pivot,
partitionIndex;

if(left < right){
pivot = right;
partitionIndex = partition(arr, pivot, left, right);

//sort left and right
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}

function partition(arr, pivot, left, right){
   var pivotValue = arr[pivot],
       partitionIndex = left;

   for(var i = left; i < right; i++){
    if(arr[i] < pivotValue){
      swap(arr, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(arr, right, partitionIndex);
  return partitionIndex;
}

function swap(arr, i, j){
   var temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
}

Question 10

What is the time complexity of a quick sort?

Answer 10

Average is O(N log N), worst is O(N^2)

Question 11

What is the space complexity of a quick sort?

Answer 11

Average is O(log N), worst is O(N)