# Coding Interview Problem #1

## Problem Statement

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

## Example

Given, input of [10, 15, 3, 7] and k of 17, the method returns true. Since 10 + 7 is 17.

### Bonus

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

puts result
``````

Performance: We have nested loops (two), so it is O of N square.

### Variation

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

``````

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
1 {}, 10 10 7
2 10, {10,15} 15 2
3 {10,15}, {10.15,3} 3 14
4 {10.15,3} 7 10

The set column as the beginning and the end values of the set as we iterate through the list.

``````require 'set'

set = Set.new

input.each do |element|
if set.member?(k - element)
return true
end
end
false
end

``````

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

No spam ever. Unsubscribe anytime.