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

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.