Whiteboarding - Multiply all values in array except at the index for each

Consider this interview question:

You have an array of integers, and for each index you want to find the product of every integer except the integer at that index.

Write a method get_products_of_all_ints_except_at_index() that takes an array of integers and returns an array of the products.

For example, given:

[1, 7, 3, 4]

your method would return:

[84, 12, 28, 21]

by calculating:

[7 * 3 * 4,  1 * 3 * 4,  1 * 7 * 4,  1 * 7 * 3]

Here's the catch: You can't use division in your solution!

And here's my solution:

def get_products_of_all_ints_except_at_index(arr)
products = []
(0...arr.length).each do |index|
product = 1
arr.each do |num|
if num != arr[index]
product *= num
end
end
products << product
end
products
end

First of all, congrats on producing a solution that works correctly. However, keep in mind that correctness is often not the only criteria for a successful candidate. Other typical criteria include performance, as well as the analysis of corner cases, where this solution does poorly.

Time complexity analysis

What is the time complexity of your solution?

$$\O(n^2)\$$

That's a typical question to expect at a programming interview. The point of the question is not so much the accurate computation, but an open discussion around this topic.

Would you describe this solution as optimal?

No. It's a brute-force solution.

A likely next question is: can we do better?

Algorithm

Here's the catch: You can't use division in your solution!

That's some sort of hint. It's trying to guide you in a certain direction.

Without the catch, would you implement the solution the same way? If we can use division, it's easy to see a simple optimization: first compute the product of all elements, and then for each element, divide the total product by the element. That would have time complexity $$\O(n)\$$ instead of $$\O(n^2)\$$.

The catch prevents us from using the simple optimization. Why? So that we find another way. This is the hard part, to discover something clever under high pressure. But at least it's important to reach this point by thinking out loud about time complexity, and the nature of the problem at hand.

You could compute "prefix products" $$\L\$$, such that $$\L[i]\$$ is the product of all the values that are on the left of $$\a[i]\$$, and "prefix products" $$\R\$$, such that $$\R[i]\$$ is the product of all the values that are on the right of $$\a[i]\$$. With these helper arrays, the target value to compute for each $$\i\$$ is $$\L[i] * R[i]\$$. No division needed, and time complexity of this solution is $$\O(n)\$$.

Then a discussion can follow about tradeoffs. For example, how does this compare to your original solution?

Time complexity is improved, but space complexity is now $$\O(n)\$$, instead of $$\O(1)\$$ of brute-force.

A likely next question is: can we do better?

Corner cases

Other important points an interviewer may look for:

• Does the candidate look for corner cases?

• If you don't look for them, the interviewer will probably nudge you to go look for them. It's important to recognize the nudge.
• Is the candidate able to find corner cases?

• If you are not able to, the interviewer will probably nudge you in the general direction. It's important to recognize the nudge, and then the general direction, and verbalize all that, thinking out loud.
• Can the candidate correctly adapt the solution to handle the corner cases?

So what's an interesting corner case here?

When computing products of numbers, there may be a risk of integer overflow.

At this point it's important to ask about the minimum and maximum values that may in the array, as well as the length of the array. Based on that, the candidate should discuss about the possibility of integer overflows, and try to compute if it can happen or not. And sure enough, if you are able to conclude that based on the input parameters integer overflow cannot happen, the interviewer will adjust the parameters accordingly. And then you need to discuss strategies to deal with the added complication.

You can expect the interviewer to keep adding twists to the problem, raising more and more challenges. The interview can branch and go in multiple possible directions, often in directions where you seem least comfortable. It's good to try to anticipate potential complications. Trying to find corner cases is probably a good starting point.

Discussion

The posted question contains simply the problem description and the solution. A discussion around the solution is missing, maybe you didn't think it's important. But it is. Thinking out loud, and expressing your logic clearly during a programming interview is usually just as important as the solution itself.

The first thing I would look for as an interviewer would be the use of with_index as well as map for the outer loop and reduce for the inner loop.

def get_products_of_all_ints_except_at_index(arr)
arr.each_with_index.map do |item, index|
product_except_at_index(arr, index)
end
end

def product_except_at_index(arr, except_index)
arr.each_with_index.reduce(1) do | product, (item, index)|
index != except_index ? product * item : product
end
end

puts get_products_of_all_ints_except_at_index([1, 7, 3, 4]).inspect

Depending on the use case I would certainly consider making these methods of Enumerable or possible Array

• I would honestly like more arr.map.with_index do |_, index| at line2. But here we are getting in the personal opinions – Davide Nov 7 '18 at 20:06
• I originally had it that way and would probably do it that way myself. I opted for consistency. – Marc Rohloff Nov 8 '18 at 0:06