The Coding Interview

Interviewing for developer position has a few different stages a candidate has to go through. Some companies (especially the big ones) ask candidates to go through the algorithmic interview. This can definitely be quite frustrating as developers are put in a situation where they have to start coding while 1 or more other interviewers are observing them.

This can be REALLY stressful and it gives the feeling that if at that moment our brain freezes, that's it, we failed... I have gone through that process a few times and I would like to share some tips that will help more developers go through that stage without losing their hair.

First of all let me talk about the following misconception I had the first time I went through that stage. The part to focus on IS NOT ONLY TO SOLVE THE ALGORITHM!!!! Focus as much as possible on TALKING ABOUT OUR APPROACH!!

Yes exactly! Understanding the problem, asking questions, say what our plan of action is, even try things that may change later on are the points to focus on! This conversation that is happening inside our head, needs to come out of our mouth.

I cannot explain how much easier it is going to be to find the right path on solving the problem. Even better, interviewers are very likely to even give us some hints as we are making this interview more interactive (and less boring for them).

In most cases, coding interviews are designed in order to see what our approach in problem solving is and how it matches the one of our potential new colleagues (the interviewers). We should think of it more of a pair programming session that we are leading.

1. Sample algorithmic problem

You are asked to write a function which takes 2 strings as an input and detects if one of them is an anagram of the other. For example abba is an anagram of baba. Return true if they are, otherwise return false.

console.log(areAnagrams('abba', 'baba')) // true

2. Understanding the problem

It is common to feel like we don't want to waste any time and instantly jump into the code. However having a small conversation around the problem and ask questions until it is fully understood is crucial for not going to the wrong direction.

Good indicators of that are asking or giving more examples. A good approach here is to spot some obvious cases that return a result without having to go through the entire function. In this example if the 2 strings are equal then instantly return true. Another example is if the first string has different length than the second one then it is not an anagram of it either. Write these down.

  if (first === second) return true
  if (first.length !== second.length) return false

These quick wins are going to end up not only as bonuses, but will also help with starting to write some code into the function. At this stage we can ask what is more important for the interviewers to see in this interview. Is it us explaining what we would do and analyse that as deep as possible? Is it solving the problem no matter what? Or is it a bit of both worlds? They are humans and not robots, having a small chat so that they get familiar with our problem solving techniques will only do good. They will also appreciate it.

3. Start solving the problem

This one here is the meaty part of this interview. Following the same principles as before, we start by talking through our approach. Now let's talk about the code.

I personally find it easier to start with small inputs like ab and ba and add console.log around the code. That way we slowly start progressing with the function. After a while we will probably end up with something like this.

 const areAnagrams = (first, second) => {
  if (first === second) return true
  if (first.length !== second.length) return false
  let foundIndexes = []
  for (let i = 0; i < first.length; i++) {
    let found = false
    for (let j = 0; j < second.length; j++) {
      if (foundIndexes.indexOf(j) === -1 && first[i] === second[j]) {
        foundIndexes.push(j)
        found = true
        break
      }
    }
    if (!found) {
      return false
    }
  }

  return true
}

console.log(areAnagrams('ab', 'ba')) // true
console.log(areAnagrams('abba', 'baba')) // true
console.log(areAnagrams('abbc', 'cbba')) // true
console.log(areAnagrams('abbc', 'ab')) // false
console.log(areAnagrams('abbc', 'cdba')) // false
console.log(areAnagrams('stressed', 'desserts')) // true
console.log(areAnagrams('eleven plus two', 'twelve plus one')) // surprisingly true
console.log(areAnagrams('the morse code', 'here come dots')) // true

Something I noticed when I went through that kind of interviews is that once we reach the point where the code starts to work, there's an instant confidence boost. That also helps us move a bit faster. However now is the tough part of the interview.

The interviewer will ask "What is the Big O Notation" of that algorithm? Yep first time I was asked that I was like... what? 😅

4. The Big-O Notation and optimising the algorithm

Algorithms can run without issues when the input is small. When the input gets bigger and bigger the time complexity increases! Knowing our way around improving that is quite important at this stage. We need to keep the algorithm as fast as possible. Here is the chart with Big-O complexity.

In our example above we have a loop inside another loop. If we think about it in mathematical terms, if each of the strings has length of 3, it means that each iteration will run 3 times. Because there is a loop inside a loop it means that it will run 3 ^ 2. Our Big O is O(3 ^ 2).

In this case this is fine but what about when the input length is something crazy like 1,000,000? Following the same formula as above we will end up with 1,000,000 ^ 2 which goes way out of hand. This is where we need to add some space complexity so that we make our algorithm faster.

Space complexity is basically us assigning another variable containing data out of the first loop. That will help us solve our problem without entering a nested loop. The example above can be converted to.

const areAnagrams = (first, second) => {
  if (first === second) return true
  if (first.length !== second.length) return false

  let foundIndexes = {}
  for (let i = 0; i < first.length; i++) {
    let key = first[i]
    if (foundIndexes[key]) {
      foundIndexes[key]++
    } else {
      foundIndexes[key] = 1
    }
  }

  for (let i = 0; i < second.length; i++) {
    const key = second[i]
    if (foundIndexes[key] > 1) {
      foundIndexes[key]--
    } else if (foundIndexes[key] === 1) {
      delete foundIndexes[key]
    } else {
      return false
    }
  }

  return !!foundIndexes
}

You see where I am going with this right? The Big-O is now O(2n). If we look at edge case again where the input has length of 1,000,000 we now end up with 2 * 1,000,000 which is WAAAAY faster than before. At the same time we can benefit from the drop the constants rule of Big-O which says that any constant next to n will not really affect the result.

Think about it. 2 * 1,000,000 is not that different from 1,000,000 comparing to 1,000,000 ^ 2. So we end up with O(n) which's performance according to the graph above is fair comparing to O(n^2) which is horrible. We have successfully optimised our algorithm and made it significantly faster.

5. Clean up

I get it... You may currently be screaming NO ONE WRITES CODE LIKE THAT ANYMORE which is very true. The last point here is how we can convert this code into something more modern and take advantage of the evolution of JavaScript. We can achieve exactly the same result with the latest JavaScript array functions. Our code can magically be transformed to the following.

const areAnagrams = (first, second) => {
  if (first === second) return true
  if (first.length !== second.length) return false

  return first.split('').sort().join('') === second.split('').sort().join('')
}

In most cases it is not even needed to do any cleanup but if we reached that point we can totally tell ourselves that we ROCKED THE ** OUT OF THIS INTERVIEW. We also need to keep in mind that interviewers like it when developers use concise functions. No matter how far we have reached showing that we know how to use stuff like find, sort, reduce, etc will only prove that we know our way around arrays.

Again the most important part is to talk our way through solving the problem. I have been to interviews where I solved the problem alone by being silent and was then surprised to see that I did not pass that stage. Similarly in other interviews the interviewers really like my approach and talking out what I had in my head and end up passing it without solving the problem 100%. It obviously depends on who we are interviewing for but if there is something to take out of this post is that being a good communicator is the way forward.

I understand that some companies especially the big ones like Google, Amazon etc will require us to solve the problem in order to pass this interview so please don't start shouting in the comments. Like everything else in life this is a skill that improves by time so don't get disappointed if the first interview does not go well. The answer to the question "will i be using that in my day to day job" is probably a no. However if improving our careers and our skillset is what is important for us then this is totally something to invest in.

What are your tips on coding interviews?