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

result = add_upto?(input, k)
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

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
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'

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).


Related Articles


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.