Preparing for a Technical Interview: Algorithms, Data Structures, and Computer Science

Introduction

Whether you’re a new graduate with a fresh computer science degree or an experienced software development professional, sometimes it’s good to get a refresh of basic computer science fundamentals. This is especially important when comparing yourself with other software developers, preparing for algorithmic intensive work, or practicing your performance in preparation for a technical interview.

In this article, we’re going to walk through some of the fundamental building blocks of basic algorithmic computer science topics. Just as a warning - this is a long post!

We’ll run through descriptions and examples of a vast array of topics, including algorithm complexity analysis (also called, big-O notation), comparing and contrasting sorting methods such as quicksort, mergesort, and other sorting techniques. We’ll discuss speeding up applications through the use of hash tables. We’ll also walk through combinatorics by creating combinations, permutations, and seeing how to generate all possible pairs from an array. Next, we’ll cover iterative versus recursive functions, including examples of the popular fibonacci and factorial functions.

We’ll also take a look at trees, including classic trees, binary trees, min/max heaps. We’ll learn about traversal techniques such as breadth-first search, depth-first-search, and the A* algorithm. Finally, we’ll look at some Javascript subtleties, such as closures and object-oriented class design.

Now, this is quite a range of topics. However, they’re most certainly important for software developers to understand when designing complex software. Let’s take a look at each topic, starting with the fundamental one, complexity analysis.

Topics

Below is a complete list of topics covered in this article:

• Complexity analysis and big-O notation (for-loop examples)
• Sorting. Examples: Quicksort, Mergesort, Insertion Sort, Selection Sort
• Hash tables. Example: Letter occurrences in a string
• Combinations and permutations. Examples: Calculate number of pairs, Find pairs with target product
• Iterative vs recursive functions. Examples: Fibonacci, Factorial
• Binary search and divide and conquer. Example: Searching within a sorted array
• Linked Lists. Examples: Creating a linked list, Reversing a linked list
• Trees. Examples: Creating a tree, Traversing a tree with DFS and BFS
• Breadth-First Search, Depth-First Search, A* Search
• Binary Trees. Example: Inserting, Checking if a value exists, Preorder, Inorder, Postorder traversal. Finding the max depth.
• Binary Heaps: Min-heap, Max-heap
• Javascript class
• Javascript closure

Complexity Analysis (Big-O Notation)

Complexity analysis, also called Big-O notation, is a method for determining the runtime complexity for a particular algorithm. It’s commonly used to gauge the speed or storage requirements for an algorithm. Analyzing complexity can be quite useful, especially when an algorithm requires iterating over many rows of data, possibly performing multiple iterations over child elements and subsets of child elements. The more embedded looping that occurs within an algorithm, the more CPU time that is required for processing the data. As such, an algorithm can slow down dramatically in average or worst-case scenarios, potentially bringing software applications to a crawl.

The reliance on CPU processing time is what makes complexity analysis so important for algorithmic design. Code that operates efficiently and optimally can run far quicker than less optimal implementations. In addition, many of the algorithms and data structures that we’ll cover throughout this article rely on understand complexity analysis to describe the reasons that we use them.

Let’s take a look at the basics behind complexity analysis for various code samples. This will give a general understanding of what we’re looking for when designing algorithms to be efficient and also cover the ground-work for the other topics in this article.

Accessing a Single Array Element: O(1)

Let’s start with the simplest case for complexity. We’ll simply retrieve the value for a single element within an array or hash.

var arr = [1, 2, 3, 4, 5];
arr[0];

In the above code, we have an array of 5 elements. Of course, it could also be 5 million elements, but the act of retrieving a single element from it is a very simple and quick operation. We can simply access the value at the particular index within the array. We can perform the same operation with a hash, as well.

The complexity for accessing an array or hash is considered to be O(1).

We describe complexity of an algorithm using the letter ‘O’ followed by a description of the number of iterations. In the case accessing an element within an array or hash, it takes 1 operation to perform. Thus, we can describe the complexity as O(1) for this code example. This is about as good as it gets for algorithm complexity. Of course, while O(1) runtime code is quite fast, it may often come at the expense of storage. This is due to requiring an array, hash, or other storage object for immediately retrieving the key/value pair for a particular piece of data.

A Single For-Loop: O(n)

Next, let’s look at code that implements a single for-loop.

var arr = [1, 2, 3, 4, 5];
for (var i=0; i<arr.length; i++) {
   arr[i] = arr[i] + 1;
}

The code example above contains a simple loop over an array of data. While the array only contains 5 elements, imagine that it could contain 5 million elements. Regardless of the actual size, we can still analyze the complexity to understand how long it can take to run.

In this simple example, we’re iterating over the array a single time and incrementing each value. Since the array contains 5 elements, it will take 5 iterations to complete.

A single for-loop, such as this, runs in O(n) time complexity.

In the simple case of a single for-loop, there are (at worst) 5 iterations. We can simply refer to this as n-iterations. We know the code will always complete after n-iterations, so we can describe the complexity of this code as O(n).

A Nested For-Loop: O(n^2)

Let’s take a look at a more complex example.

var arr = [1, 2, 3, 4, 5];
for (var i=0; i<arr.length; i++) {
   for (var j=0; j<arr.length; j++) {
      arr[i]++;
   }
}

In the above example, we’re now iterating across the array with a nested loop. This is actually a method for retrieving all permutations (including duplicates) of pairings of the data in the array. For example, the nested loop will access elements [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], …, etc.

The complexity for this code is considered O(n^2).

Since the code has a nested loop, it raises the complexity by an order of magnitude. In this case, it will be 5^2, which equals 25 iterations or 25 elements paired together. You can see how increasing the size of the array can drastically increase the processing time for looping through the data.

Naturally, the more nested for-loops that exist, the higher magnitude the time complexity becomes.

A Triple Nested For-Loop: O(n^3)

As you can imagine, the deeper you go in nested looping, the more complex an algorithm runtime becomes. Consider the example below.

var arr = [1, 2, 3, 4, 5];
for (var i=0; i<arr.length; i++) {
   for (var j=0; j<arr.length; j++) {
      for (var k=0; k<arr.length; k++) {
         // Do something.
      }
   }
}

In the above code, we’ve gone one level deeper in complexity. The complexity for this code is considered O(n^3).

The more nested for-loops that an algorithm contains, the longer the runtime becomes, thus the longer it takes to complete a run of the software. You can see how runtime complexity can become particularly important when designing complex algorithms for software.

There are a large variety of algorithms and data structures that are used specifically for handling certain runtime complexity issues. It’s a good idea to learn about the various options available to you when designing solutions.

Sorting

Now that we’ve described the basics behind algorithm complexity analysis, let’s take a look at some of the more popular algorithms that keep runtime complexity in mind. In particular, let’s look at the more popular sorting techniques of Quicksort, Mergesort, Insertion Sort, and Selection Sort.

Quicksort: O(n * log(n))

We’ll start with Quicksort, which is one of the most popular sorting techniques used by developers. It’s not only one of the more optimal methods for sorting data, running (on average) in O(n * log(n)) runtime, but it’s also used in many software development libraries as the default sorting technique (for example, .NET and Java both use Quicksort). This is because Quicksort has an added advantage of being efficiently implemented on many architectures. (As an aside, .NET actually uses a customized form of Introspective sort, combining Quicksort, Heapsort, and Insertion sort depending on the data size. See the MSDN page on Array.Sort for details.)

While quicksort might sound complicated, it’s actually pretty easy to implement. The algorithm works through a divide and conquer approach. An array to be sorted is broken in half, and each half is then sorted. Here is a description of the algorithm:

1. Select a random value from the array (such as the first one).
2. Put all values less than the value in an array named “left”.
3. Put all values greater than the value in an array named “right”.
4. If array “left” or array “right” has more than one value, repeat the above steps on it.
5. The sorted result is array “left” + selected value + array “right”.

Let’s see how to implement this in a code example.

var quickSort = function(arr) {
  var sorted = [];
  var left = [];
  var right = [];

  if (arr && arr.length > 1) {
    // 1. Select a random element.
    var mid = arr[0];

    // 2. Place all numbers less in the left array, greater in the right array.
    for (var i=1; i<arr.length; i++) {
      if (arr[i] < mid) {
        left.push(arr[i]);
      }
      else {
        right.push(arr[i]);
      }
    }

    // 3. If left or right have more than 1 item, repeat above steps.
    left = quickSort(left);
    right = quickSort(right);

    // 4. Finally, combine left + mid + right.
    left.push(mid);
    sorted = left.concat(right);
  }
  else if (arr[0] !== undefined) {
    // One or no numbers, just return it.
    sorted.push(arr[0]);
  }

  return sorted;
}

console.log(quickSort([1,7,5,23,9,34,12,100,2,6,0,-5,25]));
// [-5, 0, 1, 2, 5, 6, 7, 9, 12, 23, 25, 34, 100]

The above code uses recursion to repeatedly sort the left and right halves, until they contain just a single element to be combined together. This is how the divide and conquer approach works to help optimize the solution.

The above implementation is a basic example of quicksort and you can find many different implementations online. Let’s take a look at the next sorting technique, mergesort.

Mergesort: O(n * log(n))

Mergesort is another popular sorting technique that is used in many software applications and frameworks. Java actually uses mergesort, along with quicksort, when sorting arrays of data (depending on the type). This is due to mergesort being more effective on certain types of data. Both quicksort and mergesort run in an average case of O(n * log(n)) runtime complexity.

Similar to quicksort, the mergesort algorithm is also straight-forward to understand and implement, operating on a divide and conquer approach. The algorithm is, as follows:

1. Separate each item to be sorted into its own group of 1 (one element is effectively sorted, by default). Do this by repeatedly dividing the array in half until each half contains just 1 element each.
2. Combine adjacent groups by pushing each element onto its own stack (stack 1 and stack 2). The stack will be in sorted order, with the smallest at the top.
3. Take the smallest value from either the top of stack 1 or stack 2 and add to the front of a new group. If no more elements exist in a stack, take the remaining stack and add to the new group.
4. Repeat until no more values exist in the stacks.
5. If more than 1 group remains, repeat steps 2-5.

Let’s take a look at a code example to implement mergesort.

function mergeSort(arr) {
  var result = [];

  // Calculate mid point to split array.
  var mid = Math.floor(arr.length / 2);
  var left = arr.slice(0, mid);
  var right = arr.slice(mid, arr.length);

  // If more than one element, split the array again, until we get to a single element (implicitly sorted).
  if (left.length > 1) {
    left = mergeSort(left);
  }

  if (right.length > 1) {
    right = mergeSort(right);
  }

  // Merge the left and right parts together, until either part is exhausted.
  while (left.length > 0 && right.length > 0) {
    var value;

    // Sort the values while merging.
    if (left[0] < right[0]) {
      value = left.splice(0, 1)[0];
    }
    else {
      value = right.splice(0, 1)[0];
    }

    result.push(value);
  }

  // Add in the remaining values from the left-over group.
  if (left.length > 0) {
    result = result.concat(left);
  }
  else if (right.length > 0) {
    result = result.concat(right);
  }

  return result;
}

var arr = [3,2,1,12,62,7,5,4,100,88,97,39];
console.log('Sorting: ' + arr);
console.log(mergeSort(arr));

// "Sorting: 3,2,1,12,62,7,5,4,100,88,97,39"
// [1, 2, 3, 4, 5, 7, 12, 39, 62, 88, 97, 100]

As you can see in the above code, we first calculate the midpoint of the array. We then split the array into a left and right portion. Next, we use recursion to split the left and right sides again, repeating until only a single element remains in each side.

Once we’ve narrowed the splits down to single elements, we begin the merging process. We step through each half and take the smallest value from the front of each array (i.e., the top of the stack) and add them to a merged result. If we run out of values in either list, we just append the remaining list to our result. This effectively combines the two sides together in sorted order, which gets returned back to the recursive process, merging with the other halves, until all halves have been merged together.

Insertion Sort: O(n^2)

Now that we’ve covered two O(n * log(n)) sorting algorithms, let’s take a look at two simpler, but typically less efficient sorting algorithms. We’ll start with insertion sort.

The insertion sort algorithm takes a simplified approach to sorting a list of numbers. The method compares the first value in a list with each subsequent value, until one that is less is found. It then shifts all of the other values up a position, making room to insert the smallest value into position. The steps are highlighted below.

1. Starting with the first value in the list, compare the next value with the prior.
2. If the prior value is larger, shift it up a position.
3. Repeat shifting all values to the left of the smaller element up a position until the value is no longer smaller.
4. Insert the smaller element into the newly made position.

While insertion sort is simple to implement and efficient for small, mostly sorted, data sets, the core problem with this method is its overall runtime inefficiency. By design, it uses a nested while loop to iterate over the elements at each iteration of the array to be sorted. It does this in order to locate the correct position to insert the smaller value. In doing so, insertion sort is a time complexity of O(n^2).

A code example for insertion sort is shown below.

var insertionSort = function(arr) {
  if (arr && arr.length) {
    for (var i=1; i<arr.length; i++) {
      var temp = arr[i];
      var j = i - 1;

      while (j >= 0 && arr[j] > temp) {
        // Swap positions, bumping the values up.
        arr[j+1] = arr[j];
        j--;
      }

      // Insert the value into position.
      arr[j+1] = temp;
    }
  }

  return arr;
}

var arr = [3,2,1,12,62,7,5,4,100,88,97,39];
console.log('Sorting ' + arr);
console.log(insertionSort(arr));

// "Sorting 3,2,1,12,62,7,5,4,100,88,97,39"
// [1, 2, 3, 4, 5, 7, 12, 39, 62, 88, 97, 100]

Notice in the above code how there is a nested while loop within the for loop. It’s this double looping that causes insertion sort to be O(n^2) in runtime complexity.

Selection Sort: O(n^2)

Let’s review one final sorting method that is similarly simple to insertion sort, but suffers from the same efficiency problem of having an O(n^2) runtime complexity.

Selection sort follows another simple sorting pattern, as shown below.

1. Starting with the first value in the list, find the smallest element.
2. If the smallest element is not the current position, swap it with the value at the current position.
3. Move to the next value in the list and repeat steps 1-3, until you reach the end of the list.

Below is a code example for implementing selection sort.

var selectionSort = function(arr) {
  if (arr && arr.length) {
    for (var i=0; i<arr.length - 1; i++) {
      // Start at position i.
      var minIndex = i;

      // Find the next smallest value.
      for (var j=i+1; j<arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
          // Found a new minimum, remember its index.
          minIndex = j;
        }
      }

      if (minIndex !== i) {
        // Move minimum value into position by swapping places with existing value.
        var temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
    }
  }

  return arr;
}

var arr = [3,2,1,12,62,7,5,4,100,88,97,39];
console.log('Sorting ' + arr);
console.log(selectionSort(arr));

// "Sorting 3,2,1,12,62,7,5,4,100,88,97,39"
// [1, 2, 3, 4, 5, 7, 12, 39, 62, 88, 97, 100]

Notice in the above code, similar to selection sort, insertion sort has a nested loop to iterate over each element of the array. It does this in order to locate the smallest element at each step and then swap its position with the current index. It’s due to this nested looping that selection sort has a runtime complexity of O(n^2).

Hashtables

Now that we’ve covered sorting and dug a little deeper into runtime complexity analysis, the next topic to consider is how to speed up an algorithm. One of the more common methods for increasing runtime speed is through the use of hashtables.

The hash table is a data structure that has an O(1) runtime complexity, which is quite fast, taking just a single instruction to access a key/value pair. It can greatly speed up the runtime of an algorithm by effectively caching values that can be quickly looked-up in subsequent calls, as needed.

While hash tables are very fast and convenient for accessing cached values, they do take up additional storage. This can be in the form of memory or disk persistence. Therefore, the increase in runtime speed comes at the cost of space. However, in many cases, this is an acceptable tradeoff, especially as the costs for storage go down.

Using a Hashtable

A hash table can be implemented either via an array or by using an associative array. Here are two examples of caching with a hash table.

var hash = [];
hash[0] = 1;

console.log(hash[0]);

In the above example, we’re simply using an array to store the value “1” at index 0. Assuming that “0” is a valid key for our data, we can quickly access its associated value by simply reading that index from the array.

Likewise, we can do the same with an associative array (i.e., a hashtable), as shown below.

var hash = {};
hash['cat'] = 'meow';
hash['dog'] = 'woof';

console.log(hash['cat']);

In the above example, we’ve created an associative array with two keys in it. We can access the key/value pair for any entry by using the key as the index. In this manner, you can cache and retrieve data for an associated key/value pair that your algorithm requires.

Let’s take a look at how we can utilize hash tables to speed up an algorithm’s runtime.

Counting Letter Occurrences in a String

Consider the problem of counting the number of times each letter occurs within a string. For example, in the string “mississippi”, we want to count the number of times each letter appears in the string. In this case, “m” would equal 1, “i” would equal 4, “s” would equal 4, and “p” would equal 2. The total count of letters is thus 11 characters, with 4 unique characters.

A naive approach to counting the letter occurrences in a string would be to simply loop over the string for each letter and count the number of times it appears. An example is shown below.

Approach 1: Looping to Count Letters

In this example, we’ll simply loop over the string for each character and count the number of times they appear. The code example for this is shown below.

var letterCount = function(str, letter) {
  var count = 0;

  for (var i=0; i<str.length; i++) {
    if (str[i] === letter) {
      count++;
    }
  }

  return count;
}

var word = 'mississippi';

letterCount1(word, 'm')
// 1
letterCount1(word, 'i')
// 4
letterCount1(word, 's')
// 4
letterCount1(word, 'p')
// 2

You can see in the above code how we loop across the string and count the number of times our target letter appears. Since we have a single for-loop, this algorithm has a runtime complexity of O(n). That is perfectly fine, however, if this method needs to be called many times, it might be wasteful to continuously loop across the string recounting the number of times a letter appears, especially when we’ve already calculated the sum. This is where caching with a hash-table can speed things up.

Approach 2: Using a Hash Table to Count Letters

Let’s build a hashtable that contains the number of times each letter in the string appears. We can then use the hash to instantly find the counts for any desired letter.

var letterCounts = function(str) {
  var hash = {};

  for (var i=0; i<str.length; i++) {
    hash[str[i]] = hash[str[i]] ? hash[str[i]] + 1 : 1;
  }

  return hash;
}

var hash = letterCounts('mississippi');
hash['m']
// 1
hash['i']
// 4
hash['s']
// 4
hash['p']
// 2

In the above code for letterCounts we loop over the string and calculate the number of times each letter appears, incrementing the value for each letter key in our hashtable. While we have the same for-loop and runtime complexity of O(n), as the prior example, this particular method only needs to be executed a single time. Once we have the hash, there is no need to run this method a second time. We can simply access the hash, directly, to obtain letter counts. This is shown in the second example above, where we retrieve the letter counts for each letter in the word, using a runtime complexity of O(1).

As you can see, if we need to repeatedly retrieve letter counts in a string, the hashtable solution is far quicker and more optimal for returning results.

Combinatorics

The next important topic to review is how to form combinations and permutations from an array of data. This can be a relatively common task, especially when comparing and contrasting elements within a list to search for specific features.

First, let’s briefly define the difference between a combination and a permutation.

What is a Combination?

A combination is a selection of unique items from a list, regardless of their ordering. That is, duplicate items are not permitted in the list (i.e., [A, B] and [B, A] are not part of a combination).

For example, if you have a list of items [A, B, C, D, E], the two-item combinations from this list will include [AB], [AC], [AD], [AE], [BC], [BD], [BE], [CD], [CE], [DE].

To calculate the number of combinations that can be formed from selecting r elements from a list of n total elements, we can use the “n choose k” formula, as follows:

N Choose K

n is the number of total elements in the list.
k is the number of elements within each pair.

n! / k!(n- k)!

Let’s take a look at some quick examples. The number of combinations that can be formed from the first example above (letters A-E) by selecting any two letters, turned out to be 10 different combinations. This can be calculated as follows:

5C2 = 5! / 2! (5 - 2)!
5C2 = 120 / 2 (3!)
5C2 = 120 / 2 6
5C2 = 120 / 12
5C2 = 10

[A, B, C, D, E]
[AB], [AC], [AD], [AE], [BC], [BD], [BE], [CD], [CE], [DE]

What if we wanted to select 4 elements from the list and form combinations? That would be 5 choose 4, or 5C4.

5C4 = 5! / 4! (5 - 4)!
5C4 = 120 / 24 (1!)
5C4 = 120 / 24 1
5C4 = 120 / 24
5C4 = 5

[A, B, C, D, E]
[ABCD], [ABCE], [ABDE], [ACDE], [BCDE]

Calculating the Number of Combinations

To calculate the number of combinations or permutations that can be created in a given set, we’ll need to use the factorial function, as described in the above formulas.

The Factorial Function

We can easily write a factorial function with the following code.

var factorial = function(n) {
  var result = 1;

  for (var i=n; i>0; i--) {
    result *= i;
  }

  return result;
}

Code Example: Calculating the Number of Combinations

With the factorial function created, we can now calculate the number of combinations by using the following code example.

var combinationCount = function(n, k) {
  var result = 1;

  var divisor = (factorial(k) * factorial(n - k));
  if (divisor) {
    result = factorial(n) / divisor;
  }

  return result;
}

What is a permutation?

A permutation is a selection of items from a list where the order matters. This means, the selected pairs can include duplicate items in differt orders (i.e., [AB] and [BA] are both distinct valid permutations for the items ‘A’ and ‘B’). In fact, combination locks for doors, lockers, and bike chains might be better named “permutation locks”, since two different permutations of the same digits (123 or 321) are distinct valid codes for a password!

For example, if you have a list of items [A, B, C, D, E], the two-item permutations from this list will include [AB], [BA], [AC], [CA], [AD], [DA], [AE], [EA], [BC], [CB], [BD], [DB], [BE], [EB], [CD], [DC], [CE], [EC], [DE], [ED].

To calculate the number of permutations that can be formed from selecting r elements from a list of n total elements, we can use the following formula, as follows:

N Permute K

n is the number of total elements in the list.
k is the number of elements within each pair.

n! / (n- k)!

Just as we did for combinations, let’s take a look at some quick examples. The number of permutations that can be formed from the first example above (letters A-E) by selecting any two letters, turned out to be 20 different permutations. This is larger than the number of combinations because permutations allows items to be re-selected, but in a different order. This can be calculated as follows:

5P2 = 5! / (5 - 2)!
5P2 = 120 / 3!
5P2 = 120 / 6
5P2 = 20

[A, B, C, D, E]
[AB], [BA], [AC], [CA], [AD], [DA], [AE], [EA], [BC], [CB], [BD], [DB], [BE], [EB], [CD], [DC], [CE], [EC], [DE], [ED]

What if we wanted to select 3 elements from the list and form permutations? That would be 5 permute 3, or 5P3.

5P3 = 5! / (5 - 3)!
5P3 = 120 / 2!
5P3 = 120 / 2
5P3 = 60

[A, B, C, D, E]
[ABC], [ABD], [ABE], [ACB], [ACD], [ACE], [ADB], [ADC], [ADE], [AEB], …

Calculating the Number of Permutations

Just as we did with the combination counts, we can calculate the number of permutations by using the factorial function, as well. The code example for this is shown below.

var permutationCount = function(n, k) {
  var result = 1;

  var divisor = factorial(n - k);
  if (divisor) {
    result = factorial(n) / divisor;
  }

  return result;
}

Generating Combinations and Permutations

Now that we’ve described the difference between combinations and permutations and have created functions for calculating the number that can be generated, let’s see how to actually generate the sets with code.

Generating Combinations

Since we’re comparing each element against the others, generating combinations requires a nested loop as we iterate over the elements within the list. Due to the nested loop, generating combinations has a runtime complexity of O(n^2). A code example for generating pairs of 2 combinations is shown below.

var combinations = function(arr) {
  var result = [];

  for (var i=0; i<arr.length; i++) {
    var item1 = arr[i];

    for (var j=i+1; j<arr.length; j++) {
      var item2 = arr[j];

      result.push([item1, item2]);
    }
  }

  return result;
}

combinations(['A', 'B', 'C', 'D', 'E'])

// [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["B", "C"], ["B", "D"], ["B", "E"], ["C", "D"], ["C", "E"], ["D", "E"]]

Notice in the above code for generating combinations, our inner for-loop begins at one step past the outer loop’s starting position. In this manner, combinations will select unique element pairs.

Generating Permutations

Just as we did with the generation of combinations, we can generate the set of permutations by using very similar code. The difference is that instead of starting the inner for-loop at one step past the outer loop’s starting position, we’ll simply start at position 0, allowing elements to be reused in different orders. A code example is shown below.

var permutations = function(arr) {
  var result = [];

  for (var i=0; i<arr.length; i++) {
    var item1 = arr[i];

    for (var j=0; j<arr.length; j++) {
      var item2 = arr[j];

      if (item1 !== item2) {
        result.push([item1, item2]);
      }
    }
  }

  return result;
}

permutations(['A', 'B', 'C', 'D', 'E'])

// [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["B", "A"], ["B", "C"], ["B", "D"], ["B", "E"], ["C", "A"], ["C", "B"], ["C", "D"], ["C", "E"], ["D", "A"], ["D", "B"], ["D", "C"], ["D", "E"], ["E", "A"], ["E", "B"], ["E", "C"], ["E", "D"]]

Generating Combinations and Permutations in Sets of K

The above two code examples are used for generating pairs of combinations and permutations from a set. That is, each combination or permutation consists of 2 selected elements from the list. If we want to select 3, 4, 5, or K elements for each combination or permutation, a different algorithm is required.

For the case of using a variable length set size, the code will be required to keep track of the last index used, as well as the current index across the set. You can refer to the code examples to find example functions for doing this.

Below is an example of the code running.

combinationsn(['A', 'B', 'C', 'D', 'E'], 2)
// [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["B", "C"], ["B", "D"], ["B", "E"], ["C", "D"], ["C", "E"], ["D", "E"]]


combinationsn(['A', 'B', 'C', 'D', 'E'], 3)
// [["A", "B", "C"], ["A", "B", "D"], ["A", "B", "E"], ["A", "C", "D"], ["A", "C", "E"], ["A", "D", "E"], ["B", "C", "D"], ["B", "C", "E"], ["B", "D", "E"], ["C", "D", "E"]]

combinationsn(['A', 'B', 'C', 'D', 'E'], 4)
// [["A", "B", "C", "D"], ["A", "B", "C", "E"], ["A", "B", "D", "E"], ["A", "C", "D", "E"], ["B", "C", "D", "E"]]

Using Combinations to Find Pairs of a Target Product

Now that we’ve seen how to generate combinations and permutations, let’s see how it can be applied.

Suppose we want to find all pairs within a set that generate a certain product. For example, if we have a list of numbers [1, 2, 3, 4, 5] and we want to find all pairs of numbers that can be used to create the product 12, the answer would be [3, 4].

We can solve this problem by generating all possible combinations from the set and calculating their products. We wouldn’t use permutations, because 3 × 4 == 4 × 3, which both equal 12. In this case, combinations are what we’re after.

Below is a code example for solving this, which you can also run to see how it works.

var findProduct = function(product, arr) {
  var result = null;

  for (var i=0; i<arr.length; i++) {
    for (var j=i+1; j<arr.length; j++) {
      if (product === arr[i] * arr[j]) {
        result = [arr[i], arr[j]];
        break;
      }
    }

    if (result) {
      break;
    }
  }

  return result;
}

findProduct(12, [1, 2, 3, 4]);
// [[3, 4]]

findProduct(24, [1, 2, 3, 4, 5, 6, 7, 8]);
// [[3, 8], [4, 6]]

Iterative versus Recursive Functions

When working with arrays and lists of data, code often has to loop over the data and perform some kind of calculation. The two styles for looping over the data include iterative and recursive approaches.

When using an iterative approach, a while or for-loop is often used to iterate from the first position in the array to the last. By contrast, when using a recursive approach, the function calls itself repeatedly until all of the data within the array has been consumed.

Recursive functions require a base-case. This consists of a test to determine whether further code within the function should run, which will result in recursively calling the same function again. When the base-case is valid, the recursion stops, allowing the result from the calculations to bubble back up the stack to the original caller. It’s a bit easier to see an example!

Iterative Factorial

During our prior topic of combinatorics, you may recall that we used a factorial function for calculating the number of combinations or permutations that can be generated from a set. It just so happens that the factorial function can provide a perfect example of the difference between iterative and recursive functions.

The iterative factorial function is shown below.

var factorial = function(n) {
  var result = 1;

  for (var i=n; i>0; i--) {
    result *= i;
  }

  return result;
}

Notice, the iterative factorial function includes a for-loop that iterates from the starting number until it reaches 0. At each step, we multiply the result by the current number.

Recursive Factorial

Let’s take a look at what a recursive factorial function looks like.

var factorialr = function(n) {
  var result = 1;

  if (n === 0 || n === 1) {
    result = 1;
  }
  else {
    result = n * factorialr(n - 1);
  }

  return result;
}

In the above recursive implementation, we’ve defined a base-case at the top of the function. The base-case checks if n is either 0 or 1. If so, we know the answer to factorial(0) and factorial(1) are both 1. Therefore, there is no need to recurse any further, and we can simply return 1. For all other values of n, we set the result to be n multiplied by the value returned from the same factorial function using the parameter n - 1 (the number that comes before it). In this manner, we recursively call the factorial function for each digit down the line, until we reach the base-case of n equaling 1.

Running the code with some logging statements, shows the following result:

factorialr(5)

"Inside factorialr(5)."
"Inside factorialr(4)."
"Inside factorialr(3)."
"Inside factorialr(2)."
"Inside factorialr(1)."
"result = 1"
"result = 2"
"result = 6"
"result = 24"
"result = 120"
120

You can see how the recursive property of the function calls itself until the final answer is obtained. You can play with both the iterative and recursive code examples to see how they work.

Iterative Fibonacci

Let’s take a look at one more example of iterative versus recursive functions. This time, we’ll look at the code for generating the fibonacci sequence. The Fibonacci sequence contains a series of values, where each value is the sum of its two prior values. Starting from 0, 1, the next value is 1 + 0 = 1, giving us 0, 1, 1. The next value is 1 + 1 = 2, giving us 0, 1, 1, 2. The next set of steps gives us 2 + 1 = 3 and 3 + 2 = 5, giving us 0, 1, 1, 2, 3, 5, 8, 13, 21.

We’ll start with an iterative approach, as shown below.

var fib = function(n) {
  var result = [];

  for (var i=0; i<=n; i++) {
    if (i === 0) {
      result.push(0);
    }
    else if (i === 1) {
      result.push(1);
    }
    else {
      result.push(result[result.length - 1] + result[result.length - 2]);
    }
  }

  return result;
}

fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

In the above iterative approach, we use a for-loop to iterate from 0 until we reach n, appending the resulting values of the fibonacci sequence to the result array. Just as we saw with the factorial function, we can apply a recursive approach to get the same result.

Recursive Fibonacci

Let’s rewrite the fibonacci function using a recursive approach. Instead of using a for-loop to iterate over the sequence, we’ll recursively call the function itself, to generate the resulting values. The code example for this is shown below.

var fibr = function(n) {
  var result = 0;

  if (n === 0) {
    result = 0;
  }
  else if (n <= 2) {
    result = 1;
  }
  else {
    result = fibr(n - 1) + fibr(n - 2);
  }

  return result;
}

var fibSequence = function(n) {
  var result = [];

  for (var i=0; i<=n; i++) {
    result.push(fibr(i));
  }

  return result;
}

fibSequence(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Notice how the above recursive code includes a base-case. Just as we saw with the recursive factorial function, the recursive fibonacci function uses a base-case to determine if the current sequence value is 0, 1, or 2. If so, we immediately know the result and can return the answer. For all other values, we recursively call the function again, summing the two prior resulting values from the function until the final result is obtained.

Since we’re generating a sequence, we have also created a helper method, fibSequence, which builds the complete sequence from the recursive code.

Binary Search

Another topic in algorithms is the method for using binary search to find a target within an array. Binary search uses a divide and conquer approach for quickly honing in on the target value within a sorted list of items.

Binary search can be more easily explained by thinking about the classic number guessing game. One person thinks of a number from 1-100. The second person has to guess the number. At each guess, the first person says whether the guess is too high or too low. Now, the second person could randomly make guesses until they eventually arrive at the answer. However, a smarter approach is to utilize the clue of higher or lower to narrow down on the answer. Specifically, the guesser can divide in half at each guess, until they narrow down on the result.

For example, Player 1 chooses the number 76.

Round 1
Player 2 divides the range 1-100 in half and guesses 50.
Player says “too low”.
Player 2 now knows the answer can’t be 50 or less.

Round 2
Player 2 divides the range 51-100 in half and guesses 75.
Player 1 says “too low”.
Player 2 now knows the answer can’t be 75 or less.

Round 3
Player 2 divides the range 76-100 in half and guesses 88.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 88 or higher.

Round 4
Player 2 divides the range 76-87 in half and guesses 81.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 81 or higher.

Round 5
Player 2 divides the range 76-81 in half and guesses 78.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 78 or higher.

Round 6
Player 2 divides the range 76-78 in half and guesses 77.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 77 or higher.

Round 7
Player 2 divides the range 76-77 in half and guesses 76.
Player 1 says “you win!”

Binary search can be applied just like the number guessing game to efficiently find a target value within a sorted list. In fact, it can be used not just for single one-dimensional arrays, but for two or more dimensional matrices as well!

Finding a Value in an Array with Binary Search

Let’s take a look at an example of searching for a value within a sorted array. A code example is shown below.

var indexOf = function(arr, target) {
  var result = -1;
  var min = 0;
  var max = arr.length - 1;

  while (min <= max) {
    // Divide range in half and check value.
    var index = Math.floor(((max - min) / 2) + min);
    if (arr[index] === target) {
      // Found our target, we're done!
      result = index;
      break;
    }
    else if (arr[index] < target) {
      // Target is higher.
      min = index + 1;
    }
    else {
      // Target is lower.
      max = index - 1;
    }
  }

  return result;
}

indexOf([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 7)

"min=0, max=9, index=4"
"min=5, max=9, index=7"
"min=5, max=6, index=5"
"min=6, max=6, index=6"
6

indexOf([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 11)

"min=0, max=9, index=4"
"min=5, max=9, index=7"
"min=8, max=9, index=8"
"min=9, max=9, index=9"
-1

You can see, in the above code example, how the function uses binary search to find the target value in the sorted array. It does this by dividing in half the search space at each iteration, until the minimum window is greater than the maximum window, at which point we’ve found our target. In the case that the target doesn’t exist, our min counter will be greater than our max counter, and we can return -1.

You can imagine how this can drastically cut down on the time it takes to search within an array, especially if the array is very large. For example, consider a larger array and target, as shown below.

var numbers = [];
for (var i=500; i<100000; i++) {
  numbers.push(i);
}

indexOf(numbers, 12345)

"min=0, max=81482, index=40741"
"min=0, max=40740, index=20370"
"min=0, max=20369, index=10184"
"min=10185, max=20369, index=15277"
"min=10185, max=15276, index=12730"
"min=10185, max=12729, index=11457"
"min=11458, max=12729, index=12093"
"min=11458, max=12092, index=11775"
"min=11776, max=12092, index=11934"
"min=11776, max=11933, index=11854"
"min=11776, max=11853, index=11814"
"min=11815, max=11853, index=11834"
"min=11835, max=11853, index=11844"
"min=11845, max=11853, index=11849"
"min=11845, max=11848, index=11846"
"min=11845, max=11845, index=11845"
11845

numbers[11845]
12345

Linked Lists

Linked lists are a type of data structure that consists of individual nodes connected by pointers to their child and/or parent nodes. Each node in a linked list points to the next node. In this manner, linked lists can be traversed.

Linked lists can be traversed using a variety of algorithms, depending on the type of structure. For single node linked lists, where each connects just 1 other child node at a time, you can use iterative or recursive traversal.

For linked lists where each node can contain one or more child nodes, also called trees, some of the more popular traversal algorithms include depth first search (DFS), breadth first search (BFS), and the A* algorithm. DFS and BFS both have runtime complexities of O(|V| + |E|), which can be quite CPU intensive. By contrast, the A* algorithm uses an intelligent heuristic to traverse, and can be much more efficient at searching a linked list.

Let’s take look at how to construct a linked list.

Creating a Linked List

We’ll represent a node in a linked list as simple Javascript object, consisting of a value and an array of child nodes, as shown below.

var node = { val: 1, next: null };

The above data structure is sufficient to create an entire linked list. After all, we only require a means of connecting nodes to each other, which is done via the next property of the node.

Below is a method for creating a simple linked list.

var insert = function(value, parent) {
  var node = { val: value };

  if (parent) {
    // Connect a node to the parent.
    parent.next = node;
  }

  return node;
}

// Create a simple linked list, consisting of 5 nodes.
var root = insert(1);
var child = insert(2, root);
child = insert(3, child);
child = insert(4, child);
child = insert(5, child);

As you can see in the above example, we’ve linked together five nodes, containing the values of the digits 1-5. Let’s write a small function to traverse the linked list and return the values in each node.

Traversing a Linked List

We can traverse a linked list using the following code example below.

var traverse = function(root, callback) {
  while (root) {
    if (callback) {
      callback(root);
    }

    root = root.next;
  }
}

traverse(root, function(node) { console.log(node.val); });

1
2
3
4
5

In the above code, we’re simply following each node’s next property to access the next node. At each step, we can the callback function, passing in the node for processing by the caller.

Reversing a Linked List

Since linked lists are connected by a pointer to their child node, there is no direct reference from the child node back to the parent. However, we can still reverse linked list, as shown below.

var reverse = function(node, parent) {
  var result = parent || {};

  if (node) {
    var child = node.next;
    node.next = parent;

    result = reverse(child, node);
  }

  return result;
}

var reversed = reverse(root);
traverse(reversed, function(node) { console.log(node.val); });

5
4
3
2
1

In the above code, we’re reversing the linked list by setting each node’s next property to point to their parent’s node. We obtain the parent node through the recursive process by accessing each child and then passing the child, along with the original node, back into the recursive process. In this manner, each node will point to its parent. Finally, we return the last child node, as the new root.

The code to reverse a linked list can be created by using an iterative or recursive fashion.

Removing a Node in a Linked List

We can remove nodes from a linked list by following a similar pattern as the above techniques for traversing and reversing a list.

To remove a node, we begin at the head and traverse down the linked list until we reach the desired position. Once there, we set the value for next to be the subsequent child’s next. This effectively removes the target node from the chain, since the parent of the target now skips the target node and points directly to the target’s child. The code is shown below.

var remove = function(head, position) {
  if (head == null) {
    return null;
  }
  else if (position === 0) {
    return head.next;
  }
  else {
    var n = head;
    for (var i = 0; i < position - 1; i++) {
      n = n.next;
    }

    n.next = n.next.next;

    return head;
 }
}

var root = insert(1);
var child = insert(2, root);
child = insert(3, child);
child = insert(4, child);
child = insert(5, child);

traverse(root, function(x) { console.log(x.val); })
1
2
3
4
5

// Remove the node at zero-based position 3 (the node with the value "4").
remove(root, 3)

// Display the result.
traverse(root, function(x) { console.log(x.val); })


1
2
3
5

Trees

So far, we’ve seen a linked list where each node connects to a single child node. When you change the next property to allow an array of child nodes, you’re effectively creating a tree.

A tree is a linked list where each node can contain one or more children. Trees can be traversed with depth first search, breadth first search, and a variety of other traversal algorithms.

Creating a Tree

Let’s begin by creating a tree.

Below is an example of constructing a tree with a linked list.

var insert = function(value, parent) {
  var node = { val: value, children: [] };

  if (parent) {
    // Add a child to the parent.
    parent.children.push(node);
  }

  return node;
}

In the above code, we’re simply creating a new node. The difference between this example and the prior linked list example, however, is that we’re using an array to represent the child nodes. When inserting a new value into the tree, we push a new node onto the parent’s children array. This effectively links multiple nodes to the parent.

Below is an example of creating a tree that contains colors.

var root = insert('red');
var r1 = insert('red', root);
insert('orange', r1);
insert('purple', r1);
insert('brown', r1);

var g1 = insert('green', root);
insert('yellow', g1);
insert('white', g1);
insert('violet', g1);

var b1 = insert('blue', root);
insert('pink', b1);
insert('gray', b1);
insert('black', b1);

The above tree can be visually represented as shown below.

                                                red
                                         /         |          \
              red                           green                    blue
        /       |      \                 /        |       \            /      |      \
orange purple brown   yellow white violet   pink gray black

Traversing a Tree

Since a tree contains multiple children at each node, we’ll need to use a traversal algorithm to walk across each node and work its way down the depth of the branches. Let’s see how this is done using depth first search and breadth first search.

Depth First Search

Below is an example of using depth first search to traverse a tree.

var traverseDFS = function(node, callback) {
  if (callback) {
    callback(node);
  }

  for (var i=0; i<node.children.length; i++) {
    traverseDFS(node.children[i], callback);
  }
}

traverseDFS(root, function(node) { console.log(node.val); });

/*
"red"
"red"
"orange"
"purple"
"brown"
"green"
"yellow"
"white"
"violet"
"blue"
"pink"
"gray"
"black"
*/

In the above code, we’re using a recursive process to walk down each path of the tree. We begin at the root and recursively traverse each child node, deeper and deeper, until no more children are found for the given path. We then back-up in the recursive process and begin heading down the next child node path. We repeat this process until all paths within the tree have been explored.

Notice in the output of the traverseDFS function, we can see the display of each visited node along each path. The first line is the root red node. The second line is the first leftmost child of the root, also called red. That node’s children are then accessed, outputting orange, purple, and brown in order of each node being visited. This exhausts the leftmost branch.

The next branch that is visited is the green node, followed by its children, yellow, white, and violet. Finally, the process is repeated for the blue branch as well.

Depth-first search can be implemented with a stack data structure. In this manner, the stack stores each discovered child at the top and will return, or “pop”, it first when requesting the next node to traverse. This takes us deeper within the tree at each iteration. Stacks work on a first-in-last-out approach (FILO) which lends itself to depth-first search for exploring discovered nodes.

By contrast, breadth-first search can be implemented with a queue. In this manner, child nodes are appended to the end of the list, but the next node to be explored will be the first, or oldest, one that we’ve come across so far (the top-level child). Queues work on a first-in-first-out approach (FIFO).

Breadth First Search

Similarly to depth first search, we can apply a breadth first search algorithm to the tree. This allows us to traverse each layer in full, before going deeper into the tree.

An example of breadth first traversal is shown below.

var traverseBFS = function(node, callback) {
  var fringe = [ node ];

  while (fringe.length) {
    node = fringe.pop();

    if (callback) {
      callback(node);
    }

    // Collect all nodes on the fringe.
    for (var i=0; i<node.children.length; i++) {
      // Add child to front of array for exploration last.
      fringe.splice(0, 0, node.children[i]);
    }
  }
}

traverseBFS(root, function(node) { console.log(node.val); });


/*
"red"
"red"
"green"
"blue"
"orange"
"purple"
"brown"
"yellow"
"white"
"violet"
"pink"
"gray"
"black"
*/

In the above code, notice that we’re no longer using recursion for this process. Instead, we’re using a while loop that processes a fringe array. The fringe consists of all visible nodes that have been discovered at the current depth. Each time we discover a new node, we add it to the fringe, to eventually be processed by the callback. Once we finish processing the current node, we pop the next node off of the fringe and repeat the process until all depth layers and nodes have been processed.

You can see in the traversal output how there is a difference in the nodes that are discovered. In this example, we first process the red root node, followed by its children, red, green, and blue. This is immediately different than depth first search. Instead of walking down the red branch towards its child leaves, we instead process all child nodes at the current depth (1). Next, we move on to the next depth layer, which discovers the bottom leaf nodes, orange, purple, brown, yellow, white, pink, gray, and black.

Both algorithms discover all 13 nodes. However, they differ in the order of discoverability. Depth-first search is usually used to find complete paths down a tree, from root to leaf. Breadth-first search is used to discover the tree one layer at a time. This opens up the potential to apply a heuristic approach to traversing the tree, effectively changing the way traversal occurs, depending on the values found at the current level.

This leads us to the A* algorithm.

A* Algorithm

The A* algorithm uses an intelligent heuristic for traversing a tree. At each level, and each step in the traversal process, the A* algorithm calculates a score for how close it is to a particular goal. In this manner, A* can guide traversal down specific paths or branches, aiding it in efficiently finding an optimal solution.

A* works by first collecting all visible nodes at the current depth in the tree. A heuristic function is applied to each node, calculating the cost (h), along with an additional cost for distance (g). In the case of tree traversal, the distance cost can simply be considered the depth. The total cost for a node is h + g. When the cost for a node reaches 0, it can be assumed that a solution is found. Once a solution node is reached, you can traverse backwards up the tree, from solution node to root, recording each visited node as the solution path.

Let’s modify our tree from the previous example to make it slightly more complex. This will give the A* algorithm a little more to work with. We’ll use the following tree shown below.

                                                red
                                         /         |          \
              red                           green                                 blue
        /       |      \                 /        |       \                /               |          \
orange purple brown   yellow white violet   pink               gray        black
                                                                   /   |   \              /   \
                                                          teal magenta tan mauve lime

We’ve expanded our example tree to include an additional layer deeper. This tree is constructed with the following sequence of commands.

var root = insert('red');
var r1 = insert('red', root);
insert('orange', r1);
insert('purple', r1);
insert('brown', r1);

var g1 = insert('green', root);
insert('yellow', g1);
insert('white', g1);
insert('violet', g1);

var b1 = insert('blue', root);
var p1 = insert('pink', b1);
insert('teal', p1);
insert('magenta', p1);
insert('tan', p1);
var g2 = insert('gray', b1);
insert('mauve', g2);
insert('lime', g2);
insert('black', b1);

Searching for Lime using Breadth First Search

Let’s suppose that we want to find the node lime. How can we do this? We’ve learned previously that we could traverse the tree using breadth-first or depth-first search, in order to locate the node. Let’s see how many steps it takes to find this node.

var isDone = false;
var solution = [];

traverseBFS(root, function(node) {
  if (!isDone) {
    solution.push(node.val);
    if (node.val === 'lime') {
      isDone = true;
    }
  }
});

Breadth-first search traverses the tree by exploring each child node at the current depth, before moving a layer deeper, until the goal lime node is found. It visits the following list of nodes, shown below, before discovering the solution.

["red", "red", "green", "blue", "orange", "purple", "brown", "yellow", "white", "violet", "pink", "gray", "black", "teal", "magenta", "tan", "mauve", "lime"]

solution.length
18

Breadth-first search visited 18 nodes before arriving at the solution. In fact, that consists of all nodes in the tree! That is certainly the worst-case scenario, with regard to runtime complexity and CPU processing time. BFS did this because it explores all child nodes at the current depth, before moving deeper and repeating the process. Since our goal node is located at the very bottom layer, and at the far-right of the tree, it will be the last node discovered.

Searching for Lime using Depth First Search

Let’s see if depth-first search can do any better. Recall, DFS traverses from root to leaf, cutting through each layer in the tree to the very bottom, as it moves across the branches. In this manner, we should expect the goal node to be discovered in less steps than breadth-first search. This is because the goal node is not at the end of the tree, when DFS is concerned. The node black is located at the far-right, which will not be visited in DFS, as our goal node lime should be reached beforehand.

Let’s run the algorithm and see how it does.

var isDone = false;
var solution = [];

traverseDFS(root, function(node) {
  if (!isDone) {
    solution.push(node.val);
    if (node.val === 'lime') {
      isDone = true;
    }
  }
});

["red", "red", "orange", "purple", "brown", "green", "yellow", "white", "violet", "blue", "pink", "teal", "magenta", "tan", "gray", "mauve", "lime"]

solution.length
17

As we can see in the above results, depth-first search was indeed faster, in that it discovered the goal lime node before exhausting every single node in the tree. It was able to skip the black node, since it already discovered the solution.

Both breadth-first search and depth-first search are capable of finding a solution path to a goal node. However, they work by brute-force in their searching process.

Let’s take a look at how the A* algorithm uses an intelligent heuristic to efficiently find a solution path in far fewer steps.

Searching for Lime using A*

We can implement the A* algorithm in a similar manner to breadth-first search, but instead of a callback parameter, we’ll provide a cost function. The cost function, created by the calling client, will return a cost for the current node. A* will call the cost function each time it discovers a new node, so that it can prioritize which nodes to visit next.

Below is an implementation of the A* algorithm for traversing a tree.

var traverseA = function(node, cost) {
  var depth = 0;
  var fringe = [ { node: node, h: cost(node), g: depth } ];
  var solution = [];

  while (fringe.length) {
    // Explore the next state with the lowest cost.
    var current = fringe.pop();

    console.log('Checking ' + current.node.val);

    if (current.h === 0) {
      // Solution found! Walk backwards from leaf back to parent.
      solution = [];
      while (current) {
        // Add this node to the front of the array.
        solution.unshift(current.node);
        current = current.parent;
      }

      break;
    }

    // Collect all nodes on the fringe.
    for (var i=0; i<current.node.children.length; i++) {
      var child = current.node.children[i];
      fringe.push({ parent: current, node: child, h: cost(child), g: current.g + 1 });
    }

    // Sort the nodes by their heuristic score in descending order (we pop() from the end, so we want the lowest score there).
    fringe = fringe.sort(function(a, b) { return (b.h + b.g) - (a.h + a.g); });
  }

  return solution;
};

The first item to note is that we have an array called fringe. This array contains the currently discovered nodes that are still to be explored. When we start the algorithm, we initially populate the fringe with our root node. We also apply the cost function to the root node and assign a depth cost of 0. We then begin looping for as long as we have more nodes to explore and we have not yet arrived at the solution node.

At each iteration, we check if the cost for the current node is 0. If it is, then we know that we’ve arrived at a solution node. In this case, we walk backwards up the tree, saving each parent node in our solution array to be returned as the result.

If a solution is not yet found, we find all child nodes at the current level and add them to the fringe array. We apply the cost function to each node, along with a value for depth + 1 (since the child node is located 1-level deeper than the parent).

Finally, we sort the fringe in descending order of cost. In this manner, the least cost nodes are located at the end of the array, while the most expensive are located at the front. When our while loop iterates, it will pop the lowest costing node from the fringe to be explored next. This is how A* is able to efficiently explore the tree, without examining every single node across the branches.

Let’s see how it runs.

The A* Solution

To use A*, we’ll call the traverseA function and pass it a cost function for determining the cost of a given node. In particular, we’re looking for the lime node. We’ll use a landmark-based heuristic to guide the A* algorithm. In this manner, we’ll decrease the cost of a node if we know it’s on the way to the goal.

There are many different types of heuristics that can be applied to nodes with the A* algorithm, but we’re using a landmark-based one for simplicity.

The code example below shows how the A* algorithm is called on or tree, along with the cost function.

var solution = traverseA(root, function(node) {
  var cost = 100;

  if (node.val === 'red') {
    cost = 75;
  }
  else if (node.val === 'blue') {
    cost = 50;
  }
  else if (node.val === 'gray') {
    cost = 25;
  }
  else if (node.val === 'lime') {
    cost = 0;
  }

  return cost;
});

While running the above code, we can see the following list of nodes as explored while traversing with the A* algorithm.

"Checking red"
"Checking blue"
"Checking gray"
"Checking lime"

Notice how the A* algorithm traversed immediately down the correct branch, blue, then gray, and finally arriving at lime. It did this because the cost of these nodes decreased, while the other costs remained higher.

We can print the solution path, as recorded by A* in the solution, using the following code.

for (var i=0; i<solution.length; i++) {
  console.log(solution[i].val);
}

// "red"
// "blue"
// "gray"
// "lime"

A* took just 4 steps to discover the solution!

Binary Trees

A binary tree is a type of tree that consists of a left and right child at each node. In our prior tree example, we were using a tree where each node could connect to one or more child nodes. By contrast, a binary tree only contains, at most, two child nodes for any node. In addition, the child nodes are ordered based upon their value. The left child node is less than the parent node, while the right child node is greater than the parent node. In this manner, a binary tree offers a way of tracking values, and even sorting data, in a particular order.

When inserting a new node in a binary tree, you first traverse the tree in order to find the correct location to insert the new node. Starting at the root, if the new value to insert is less than the root, we move left. If the new value is greater, we move to the right. We repeat this process, traversing down the tree, until we reach an empty slot to insert our value, so that the parent node is greater than the new value (if inserting as a left child) or less than the new value (if inserting as a right child).

Let’s construct a binary tree. We can start by implementing the insert method, just as we did with our other trees. The difference, this time, is that we’ll locate the child node to insert the new node under.

The following code example constructs a binary tree.

var insert = function(value, root) {
  if (!root) {
    // Create a new root.
    root = { val: value };
  }
  else {
    var current = root;
    while (current) {
      if (value < current.val) {
        if (!current.left) {
          // Insert left child.
          current.left = { val: value };
          break;
        }
        else {
          current = current.left;
        }
      }
      else if (value > current.val) {
        if (!current.right) {
          // Insert right child.
          current.right = { val: value };
          break;
        }
        else {
          current = current.right;
        }
      }
      else {
        // This value already exists. Ignore it.
        break;
      }
    }
  }

  return root;
}

Notice in the above code, we first check if a root is available. If it’s not, then this is the first node that we’re creating. Otherwise, we start traversing the binary tree, left and right, according to whether the new value to be inserted is less than or greater than the current node. When we find an empty slot, we insert the new value on the proper leaf.

Let’s create a small binary tree.

var root = insert(10);
insert(5, root);
insert(6, root);
insert(3, root);
insert(20, root);

The above code creates a binary tree that appears, as follows.

       10
     /      \
   5         20
 /    \
3    6

Searching a Binary Tree for a Value

Since a binary tree is constructed using a set of rules for where to insert new values, we can search a binary tree in an efficient manner to locate a target node.

The code example below implements a function to check if a value exists in a binary tree.

var exists = function(value, root) {
  var result = false;

  var current = root;
  while (current) {
    if (value < current.val) {
      current = current.left;
    }
    else if (value > current.val) {
      current = current.right;
    }
    else {
      result = true;
      break;
    }
  }

  return result;
}

exists(10, root)
// true
exists(3, root)
// true
exists(7, root)
// false

The above code is very similar to the logic used in the insert function. We simply traverse left or right, depending on whether the value being searched is less than or greater than the current node. If the value is equal, then we’ve found the node and return true. If no more child nodes exist on the path, we return false.

Traversing a Binary Tree

Traversing a binary tree can be done using a variety methods, with the most common being pre-order, post-order, and in-order traversal.

The different methods for traversing correspond to how each node in the binary tree is visited, and thus, the order of the values that are returned. For example, inorder traversal will return a sorted list of values from the tree. All three traversal types follow a very similar code style, differing only in the step where the node’s value is returned.

Let’s take a look at the code to walk through a binary tree using each of the three methods. We’ll start with preorder traversal.

Traversing a Binary Tree: Preorder Traversal

If you recall from earlier, we constructed a very simple binary tree consisting of 5 nodes, as shown below.

       10
     /      \
   5         20
 /    \
3    6

When using preorder traversal, we’ll walk through the nodes starting at the root 10. Next, we’ll always head left towards the smaller values, and record the value at each node. In this manner, we find 5, and then 3. Since we’re at a terminal leaf, we’ll move back up and to the right, finding the node 6. We repeat the process, moving back up and to the right, to find the node 20.

The preorder traversal algorithm is shown below.

1. Check if the current node is null.
2. Display the value of the current node..
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function.

Below is a code example for traversing a binary tree, using preorder traversal.

var traversePre = function(head, callback) {
  // Preorder traversal.
  if (head) {
    if (callback) {
      callback(head.val);
    }

    traversePre(head.left, callback);
    traversePre(head.right, callback);
  }
}

traversePre(root, function(value) { console.log(value); })
10
5
3
6
20

In the above code, notice how we simply print the current node’s value, followed by traversing the left, and then the right, branches. This is how we give preference to the smaller values in the tree, moving left, until we hit a terminal leaf, and then moving back and to the right.

Traversing a Binary Tree: Postorder Traversal

Similar to preorder traversal of a binary tree, postorder traversal is essentially the preorder algorithm, but reversed. In postorder traversal, we hold off from returning the value of the current node, and instead traverse first. We still traverse towards the left, locating the smallest values first, followed by backing up and moving to the right. However, the main difference from preorder traversal is in the order that we return the node values.

The postorder traversal algorithm is shown below.

1. Check if the current node is null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the value of the current node..

The code example below shows a postorder traversal of a binary tree.

var traversePost = function(head, callback) {
  // Postorder traversal.
  if (head) {
    traversePost(head.left, callback);
    traversePost(head.right, callback);

    if (callback) {
      callback(head.val);
    }
  }
}

traversePost(root, function(value) { console.log(value); })
3
6
5
20
10

Traversing a Binary Tree: Inorder Traversal

The final traversal type that we’re cover is inorder traversal of a binary tree. This allows retrieving the values in a binary tree in sorted order, from smallest to largest node values.

The inorder traversal algorithm is shown below.

1. Check if the current node is null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the value of the current node..
4. Traverse the right subtree by recursively calling the in-order function.

The code example below shows an inorder traversal of a binary tree.

var traverseIn = function(head, callback) {
  // Inorder traversal.
  if (head) {
    traverseIn(head.left, callback);

    if (callback) {
      callback(head.val);
    }

    traverseIn(head.right, callback);
  }
}

traverseIn(root, function(value) { console.log(value); })
3
5
6
10
20

Traversing Iteratively

So far, we’ve shown code examples for recursively traversing binary trees. This is the simplest way to traverse this type of tree. However, it can also be done iteratively. To traverse iteratively, we’ll be required to keep track of visited nodes that we’re not yet displaying the values for. We can use a stack for this purpose, popping the next node off of the stack when we reach a leftmost leaf. In this manner, we can traverse, save off nodes, and display node values in the designated pre/post/in order traversal.

The code example below shows inorder traversal of a binary tree, using an iterative style.

var traverseIn = function(head, callback) {
  // Inorder traversal.
  var current = head;
  var history = [];

  // Move down to the leftmost smallest value, saving all nodes on the way.
  while (current) {
    history.push(current);
    current = current.left;
  }

  current = history.pop();
  while (current) {
    if (callback) {
      callback(current.val);
    }

    // Move to the right, and then go down to the leftmost smallest value again.
    current = current.right;
    while (current) {
      history.push(current);
      current = current.left;
    }

    current = history.pop();
  }
}

Finding the Max Depth of a Binary Tree

Now that we’ve seen how to construct and navigate a binary tree, let’s combine this knowledge with what we’ve learned from searching. Suppose you want to determine the maximum depth of a binary tree. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

We can find the maximum depth of a binary tree by using either breadth-first search or depth-first search. Both algorithms will explore the tree from root to leaf and allow us to find the lowest leaf node.

Let’s use the same binary tree from our example before, with one addition child node (1). As you recall, we can construct the tree with the following commands.

var root = insert(10);
insert(5, root);
insert(6, root);
insert(3, root);
insert(20, root);
insert(1, root);

The above code creates a binary tree that appears, as follows.

         10
      /      \
     5         20
   /    \
  3    6
 /
1

The maximum depth for our tree is 4, with the leaf node 1 at the deepest level.

We can implement depth-first search to find the maximum depth of this binary tree. Our search will start at the root and traverse down each branch, until it reaches a leaf node with no children (i.e., no left or right child node). We’ll then compare the depth that we’ve reached against the maximum depth so far. If the new maximum depth is greater, we’ll update our result.

The following code determines the maximum depth of a binary tree.

var maxDepth = function(root) {
    var fringe = [{ node: root, depth: 1 }];
    var current = fringe.pop();
    var max = 0;

    while (current && current.node) {
        var node = current.node;

        // Find all children of this node.
        if (node.left) {
            fringe.push({ node: node.left, depth: current.depth + 1 });
        }
        if (node.right) {
            fringe.push({ node: node.right, depth: current.depth + 1 });
        }

        if (current.depth > max) {
            max = current.depth;
        }

        current = fringe.pop();
    }

    return max;
};

As you can see, we start at the root with a depth of 1. We actually add the root node onto our fringe of nodes to be explored, assigning it an initial depth of 1. We then begin the process of locating all child nodes (left and right). Each child node is pushed onto the fringe. Recall, that a stack is used for depth-first search and a queue is used for breadth-first search.

Next, we check the current depth and pop the next child node off of the stack. We’ll continue drilling down the right-most branch until we reach a leaf with no child nodes. At this point, the next node to be popped off the stack will be the most recent right-most branch that we’ve discovered. We repeat this process until no more nodes are left to be explored. Our final result is the maximum depth of the binary tree.

maxDepth(root);
// 4

Binary Heaps

Before we finish up talking about binary trees, there is a specialized type of binary tree called a “heap”.

Binary heaps look and behave just like the traditional binary tree, as discussed above, with an additional set of constraints on how items are added to the tree. Specifically, a binary heap adds items to the binary tree such that every child value is less than or greater than the parent value. Heaps are useful for situations where you frequently need to locate the smallest or largest value within a collection.

For min-heaps, every child value on the binary tree is greater than the parent value. The root holds the minimum value of the tree.
For max-heaps, every child value on the binary tree is less than the parent value. The root holds the maximum value of the tree.

Additionally, binary heaps are complete binary trees. That is, all levels of the tree are fully filled, except possibly for the last level. When adding new values to a heap, the leaves are fully filled from left to right.

With standard binary trees, as discussed earlier, we add new values to the tree by traversing left or right depending on the new value being greater or less than the parent. With binary heaps, we always move from left to right, locating an empty leaf on the tree to insert the value at the correct level.

Binary heaps allow searching in O(n) time complexity, inserting on O(1) and peeking (i.e., obtaining the minimum or maximum value at the root of the heap) in O(1) time complexity. In this manner, they can be an efficient way of working with sorted data.

Inserting a Value into a Binary Heap

To insert a new value into a binary heap, we can follow the steps listed below.

1. Add the element to the bottom level of the heap.
2. Compare the added element with its parent; if they are in the correct order, stop.
3. If not, swap the element with its parent and return to the previous step.

By repeating these series of steps, the value added at the bottom of the heap, can “bubble-up” to the correct level, thus maintaining the order of the heap.

Deleting a Value from a Binary Heap

Similarly, to remove a value from a binary heap, we can follow the steps listed below.

1. Replace the root of the heap with the last element on the last level.
2. Compare the new root with its children; if they are in the correct order, stop.
3. If not, swap the element with one of its children and return to the previous step. That is, swap with its smaller child in a min-heap and its larger child in a max-heap.

This series of steps can be thought of as “sinking down” the value towards the correct level of the heap.

Min-Heap

An example of implementing a min-heap can be found at the link provided. We can utilize the min-heap to store and retrieve sorted values as shown below.

var heap = new BinaryHeap(function(x) { return x; });

// Generate some random numbers.
var arr = [10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 5];

// Add each number to the heap.
for (var i=0; i<arr.length; i++) {
  heap.push(arr[i]);
}


// Remove a number from the heap.
heap.remove(2);


// Pop each value from the heap in ascending sorted order.
while (heap.size() > 0) {
  console.log(heap.pop());
}

1
2
3
4
5
6
7
8
9
10

Notice in the above output, how we’re able to access the randomly added values in sorted order, starting from the minimum value. The number 2 is present in the output (even though we’ve called heap.remove(2)), as it was added to the heap twice.

Object-Oriented Javascript

Now that we’ve gone through a fairly wide range of computer science algorithm topics, let’s briefly discuss object-oriented javascript classes. This is a topic that is likely more important to full-stack and front-end web developers, but equally important to know for those versed in javascript.

The latest versions of Javascript now support the “class” declaration. This makes it particularly easy to create object-oriented classes from within Javascript. Of course, you might be more comfortable using traditional function style coding, and this is usually the proper route to take, it can still be handy to utilize object-oriented design when it makes sense.

The Person Class

Let’s begin by creating a simple class to represent a person object. We can use the class declaration to create the object. We’ll construct our person object to support a first and last name, as shown below.

var Person = class {
  constructor(first, last) {
    this.first = first;
    this.last = last;
  }

  toString() {
    return this.first + ' ' + this.last;
  }
};

The above object-oriented class defines a Person object. Notice that our class contains a constructor to initialize the first and last name properties. We’ve also included a class method, toString(), which simply returns the person in a string format.

We can instantiate a new person object by using the new keyword, as shown below.

var alice = new Person('Alice', 'Seasons');
console.log(alice.toString());

var joel = new Person('Joel', 'Smith');
console.log(joel.toString());

Alice Seasons
Joel Smith

Adding an Auto-Incrementing Unique Id to the Person Class

We’ve just seen a very basic example of defining a class in Javascript. Let’s add one more interesting spin to the example by giving each person object an automatically generated id value. Of course, you would typically pull a generated id from a database and seed the person object with this value. However, to demonstrate the idea of static variables in javascript and maintaining state, let’s see how we can add an auto-incrementing value to our class.

We can define a function outside the scope of the Person object to generate ids for us. An example is shown below.

var generateId = function() {
  this.id = this.id ? this.id + 1 : 1;
  return this.id;
}

The above code will initialize an id value within the generateId function of 1. Each time the function is called, the value will be incremented accordingly. In this manner, we can utilize this method within our person class to generate id values, as shown below.

var Person = class {
  constructor(first, last) {
    this.first = first;
    this.last = last;
    this.id = generateId();
  }

  toString() {
    return this.id + ' ' + this.first + ' ' + this.last;
  }
};

We can use the above class to output the person, including their auto-generated id value, as shown below.

var alice = new Person('Alice', 'Seasons');
console.log(alice.toString());

var joel = new Person('Joel', 'Smith');
console.log(joel.toString());

1 Alice Seasons
2 Joel Smith

Notice how our global generateId function is able to automatically increment the id value for each instantiated Person object.

Of course, the function generated values will not persist beyond a page refresh, however this still demonstrates how to maintain static values within javascript. For persisting values and data beyond this scope, a database or other persistent storage is required.

Extending Person with Inheritance

Since we’re now using object-oriented design with our Javascript object, we can utilize inheritance to extend the person class with additional functionality. Suppose we want to create an “Employee” specific object, that inherits the properties and methods of the “Person” class. We can do this with the following code, shown below.

var Employee = class extends Person {
    isManager() {
      return false;
    }
}

With the above extension, we can now instantiate both generic Person objects and specific Employee objects, as well. An example of this is shown below.

var alice = new Person('Alice', 'Seasons');
console.log(alice.toString());

var developer = new Employee('Kevin', 'Nice');
console.log(developer.toString());
console.log(developer.isManager());

Now, if we run the above code, we’ll still see the same output for the first and last name, along with the auto-generate id, but we’ll also have access to the new Employee method isManager, which will display false.

1 Alice Seasons
2 Kevin Nice
false

As you can see, object-oriented Javascript can be a useful tool, adding some of the power of other traditionally object-oriented languages such as C# and Java.

What is a Closure?

Another tricky topic when dealing with javascript, is understanding the function of a closure. Closures can be downright confusing to use, and even trickier to explain.

A closure is essentially a way to encapsulate a variable within a child scope. That is, if a particular function declares a local variable, normally when that function terminates, the variable is no longer in scope. This is the typically expected behavior of programming environments. With the exception of global or class-level variables, local variables are not retained when a function or method exits.

A closure allows you to encapsulate a local variable and thus, retain access to the variable’s value from within the scope of a child function. In this manner, child scopes can utilize variables that were declared in the parent scope, as long as they’ve created a closure around the variable.

In javascript if you use the function keyword from within another function, you are creating a closure. In this context, accessing any variable outside of your immediate lexical scope creates a closure.

Let’s take a look at a simple example.

A Simple Closure

We’ll create a simple function to say hello. The function will contain a local variable, containing the text message that is to be printed. We can create the function as shown below.

function sayHello(name) {
  var text = 'Hello ' + name; // Local variable

  var say = function() { console.log(text); }

  return say;
}

var say = sayHello('Jennifer');
say();

Hello Jennifer

In the above code, we’ve defined a simple function sayHello. The function takes a name as an argument and contains a local variable for displaying the message. In a traditional scenario, when the function exits, the local variable text would be lost. If that were to happen, the child say function would lose the value of text and be unable to print it. However, the child function is creating a closure around text.

As you can see in the output shown above, after the sayHello method exits, we can still call say() and the correct text message is printed. This is because the variable text has been wrapped within a closure, created by the child function.

In fact, if you peek at the output of say.toString(), you can actually see how the code refers to the variable text.

say.toString()

"function () { window.runnerWindow.proxyConsole.log(text); }"

Additionally, you can call the sayHello function as many times as you like. Each child function returned will still retain the correct message to print, since each function maintains its own closure of the variable text.

var say = sayHello('Jennifer');
say();

var say2 = sayHello('Alexa');
var say3 = sayHello('Jordan');

say();
say2();
say3();

Hello Jennifer
Hello Jennifer
Hello Alexa
Hello Jordan

Closures and For-Loops

An interesting scenario, which is often asked during interviews as a trick question, occurs when you attempt to utilize a for-loop variable from an event callback handler, such as jQuery or native DOM event handlers.

Consider the following simple code example, which contains several buttons with assigned click event handlers.

<input id='btn-0' type='button' value='Click Me 1' />
<input id='btn-1' type='button' value='Click Me 2' />
<input id='btn-2' type='button' value='Click Me 3' />

for (var i = 0; i < 3; i++) {
  var btn = document.getElementById('btn-' + i);

  btn.addEventListener('click', function(){
    console.log(i);
  });
}

Upon initial glance, the above code looks like it should simply print 0, 1, 2 when each of the three buttons are clicked. After all, the for-loop iterates across each button, assigns a click-event handler, and prints the value of i when the button is clicked.

If you run the above code, you’ll see the output is actually the final value of i for each button click.

3
3
3

What’s actually happening here is that the for-loop value for i is changing its value, leaving the final value as the result to the click event handler.

To correct this situation, we can utilize a closure, passing in the specifically desired value of i so that the click event handler has an instance of the actual desired value. This is shown below.

for (var i = 0; i < 3; i++) {
  var btn = document.getElementById('btn-' + i);

  (function (x) {
    btn.addEventListener('click', function(){
      console.log(x);
    });
  })(i);
}

In the above code, we’ve slightly changed our click event handler to include a closure function around the outside of it. This particular closure accepts a single parameter for the value of i and then passes that value to the scope of the child function. This gives the click event handler access to the locally passed-in variable, and thus, it can now print the correct value.

Also notice how the click event handler refers to the variable x, which is defined within our closure, and not the variable i. We assign the variable x to hold the value of i and then pass it to the enclosed child scope.

0
1
2

Practicing for a Technical Interview

In addition to reviewing the overall topics of data structures and algorithms, you may also want to practice your skills on a variety of problems. There are several sites available where you can train and hone your skills, in preparation for a technical interview or whiteboard session. Sites such as HackerRank and LeetCode offer an excellent set of algorithmic problems that you can practice on. It’s recommended to try at least one problem per day, leading up to an interview. This will give you a fresh mindset for problem solving and hopefully have you prepared for any technical discussion you might come across.

Conclusion

We’ve covered a lot of topics in this post, ranging from runtime-complexity analysis with Big-O notation, combinatorics, sorting algorithms, trees and traversal techniques, heuristics, and even object-oriented Javascript and closures. While this combines a broad range of content, it’s just the beginning of computer science algorithms and data structure fundamentals.

While refreshing your knowledge, you may also want to review the technique of map-reduce, for working with large data sets and computations across multiple sources (for example, determining the prime divisors for a set of numbers). Other topics to review include understanding the differences between locks, mutexes, semaphores, deadlocks, and livelocks. Further practice should also include a review of software application scalability (architecting an application through a web application layer, load balancers, REST service layer, and database; followed by offloading traffic with static content, content delivery networks (CDN), Amazon S3 and Cloudfront access, as well as caching, batch jobs, and client-based code for data or calculation intensive processing).

About the Author

This article was written by Kory Becker, software developer and architect, skilled in a range of technologies, including web application development, artificial intelligence, machine learning, and data science.

Sponsor Me