Coding Interview Problem #2

Problem

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

Example

Input : [1,2,3,4,5] must return [120, 60, 40, 30, 24]
Input : [3,2,1] must return [2,3,6]

Followup

What if you cannot use division?

Solution #1

Find the product of all the numbers in the array. Divide by each of the numbers.

def product(input)
  product_of_all_numbers = input.inject(1) {|result, element| result *= element}
  input.collect {|element| product_of_all_numbers/element}
end

input = [3, 2, 1]

p product(input)

Solution #2 - Without Division

The i-th element needs the product of numbers before i and the product of numbers after i. Multiply those two numbers to get the desired product. This solutions is O(N) time and space. This results in lot of code.

Solution #3 - Concise Without Division

The simplest solution that does not use division is to exclude the index of the current element when multiplying the numbers in the array.

def product(input)
  output = []

  for exclude_index in 0..input.size-1 
    result = 1
    input.each_with_index do |element, index|
      if exclude_index != index
        result *= element
      end
    end
    output << result
  end

  output
end

input = [3, 2, 1]

p product(input)


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.