Coding Interview Problem #1
Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
Given, input of [10, 15, 3, 7] and k of 17, the method returns true. Since 10 + 7 is 17.
Can you do this in one pass?
Brute Force Solution
Nested iteration is used to check for every pair of numbers. [10,15], [10, 3], [10,7], [15, 3], [15, 7] and [3,7].
def add_upto?(input, k) for i in (0..(input.size-1)) for j in (0..(input.size-1)) return true if i != j and input[i]+input[j] == k end end false end input = [10, 15, 3, 7] k = 17 result = add_upto?(input, k) puts result
Performance: We have nested loops (two), so it is O of N square.
We can return i,j instead of return true for the variation on this problem that requires indices as the output.
One Pass Solution Using Array
17 - 10 = 7. Is 7 in the list? We can check if (k - element) = x is in the list or not.
def add_up?(input, k) input.each do |element| if input.include?(k - element) return true end end false end p add_up?([10,15,3,7], 17)
Performance is O(N).
One Pass Solution Using Set
Use a set to remember the number we have seen so far. Then for a given number, we can check if there is another number that if added would sum to k.
|Iteration||set||element||k - element|
The set column as the beginning and the end values of the set as we iterate through the list.
require 'set' def add_up?(input, k) set = Set.new input.each do |element| if set.member?(k - element) return true end set.add(element) end false end p add_up?([10,15,3,7], 17)
If you trace the values of the variables, you can see that we look in the reverse direction. Performance is O(N).
Solution Using Binary Search
- Sort the list
- Iterate through the list. Run binary search on k - list[i].
We binary search N elements, so performance is O(N log N) and space is O(1).
Ace the Technical Interview
- Easily find the gaps in your knowledge
- Get customized lessons based on where you are
- Take consistent action everyday
- Builtin accountability to keep you on track
- You will solve bigger problems over time
- Get the job of your dreams
Take the 30 Day Coding Skills Challenge
Gain confidence to attend the interview