Use a Hash Table Instead of a For Loop

I have decided to spend my time during quarantine getting better at the technical interview process. When I attended a coding bootcamp a year ago, the focus wasn’t on this aspect of the job search. We spent time building projects so we had a portfolio, breezing through topics so we could understand just enough to build things. Which I think is a great approach when you want your students to learn by doing, however it leaves a ton of gaps in the knowledge bucket.

To fill these gaps, I’ve been spending time trying to gain a deeper understanding of how javascript actually works and the best ways to implement it.

This brings me to Big O notation. While I’m not going to spend this blog post explaining Big O, there are a few things that are important to understand when interviewing about it. Space and time complexity matter when building out a function. If I build a nested for loop, I run into O(n²). As for time complexity, this is terrible. Running a nested for loop takes a lot of time. However, its space complexity is constant as long as you aren’t creating anything each time you iterate (like a new array of new values or something from the results).

In an interview, if you come across a problem that requires a nested for loop, the solution can generally be achieved using O(n) instead, or linear time. A hash table can achieve this nicely. Its space complexity is a bit different, however. We are creating a new hash, so we are using O(n) instead of O(1) to do this. We have to decide which is better, saving time or saving space. Generally, the answer to this is that time is move valuable than space.

A hash table requires creating key value pairs. Looking up a key on a hash table is constant and doesn’t require any sort of iteration. So once you’ve made a key on a hash table, it’s extremely simple to grab out of the hash.

Here’s an example of a simple interview problem solved using a for loop:

Find out if the sum is present in the input array and return the two numbers that make up the sum, if there are not two numbers in that array that equal the sum, return false.

function isSumPresent(input, sum) {
  
  for (let i = 0; i < input.length; i++) {
    for (let j = 0; j < input.length; j++) {
      if (input[i] !== input[j+1] && input[i] + input[j+1] === sum){
        return [input[i], input[j+1]]
      }
    }
  }
  return false
}

You can see that since we are using a nested for loop to compare each item in the array to each item in the array, this solution is not ideal. It’s good to have an alternate way of doing this, and this is where the hash table comes in handy. We can achieve the same result like this:

function isSumPresent(input, sum) {
  const hash = {}
  
  for (let i = 0; i < input.length; i++) {
    let target = sum - input[i]
    if (hash[target]) {
      return [input[i], sum - input[i]]
    }
    hash[input[i]] = true
  }
  return false
}

Each time we iterate through the input array, we first calculate the sum minus our value at the index of input array and store it in a variable target. If the key of that target value exists on our hash, that means we’ve already come across that number and we know that we have a pair of numbers that equal our sum. If we don’t see that target value as a key on our hash, we create a key with our current value at the index of our input array and just set its value as true. In this situation, the value of the key in our hash is true so that when we check if hash[target] exists it will return true as it’s value so that we know it’s there.

We will continue iterating through our input array until we find a match where the target key already exists on the hash. If we never find it, we break out of our loop and return false.

Getting familiar with creating key, value pairs on hashes is an important concept that any code newbie should get comfortable with implementing in an interview. It shows that you understand space and time complexity and have a deeper understanding of the basics of javascript.

Photo by Shot by Cerqueira on Unsplash