I'm looking to learn more about algorithms and how to think like a programmer, by practicing coding problems. I subscribed to the mailinglist of dailycodingproblem.com so I will receive one such problem in my inbox every morning and see if I can solve it before the end of the day. Learn with me!

Today's coding problem was recently asked by Google in a coding interview:

Problem:

Given a list of numbers a and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?

My thought process:

  • First thought was that for each element in the array, we could loop over the rest of the array, calculate the sum for each element, and see if it matches k.
  • But that would be horribly inefficient, especially seeing that it's not too hard to find out what that other number would need to be, for the sum to be k.
  • More efficient would be to calculate the matching number compliment and see if it's present in the rest of the array. So that's my solution.

Solution: 


function codingProblem(a, k){
  for (let i = 0; i < a.length; i++){
        let compliment = k - a[i];
        let index = a.indexOf(compliment)
        if (index !== -1 && index !== i) return true
  }
}
  • This function takes two arguments, the a array and the number k.
  • It loops over the array a. I'm using a for loop here instead of a forEach() method, because there is no way to stop a forEach() in javascript once you've found a number that matches. It will just keep going until the last element of the array, which is inefficient.
  • For every element, this function calculates the compliment. The sum of the element and the compliment would make k.
  • Next, we find if the complimentary number compliment is present in the array with indexOf().
  • Then, the conditional if statement checks if the indexOf() returns a value and if that value is not the element itself, by checking if the position of element and compliment aren't identical. E.g. if k = 10 we don't want to return true if there is only one 5 in the array.

I've run a few tests, and this solution seems to work nicely. However, seeing that I haven't upgraded to premium yet, I only receive the problems and not the solutions in my inbox.

Let me know if I missed something!