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 numbersa
and a numberk
, 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 numberk
. - It loops over the array
a
. I'm using afor
loop here instead of aforEach()
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 makek
. - Next, we find if the complimentary number
compliment
is present in the array withindexOf()
. - 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. ifk = 10
we don't want toreturn true
if there is only one5
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!