20190626 Daily Coding Problem

20190626_daily_coding_problem.rb

# Good morning! Here's your coding interview problem for today.
# This problem was asked by Uber.
# 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.
# For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
# Follow-up: what if you can't use division?

# Results
#                  user     system      total        real
# div:         0.003087   0.000214   0.003301 (  0.003285)
# rotate:      0.421551   0.004000   0.425551 (  0.425792)
# reduce:      0.458880   0.002784   0.461664 (  0.461909)

require 'benchmark'

arr = (1..1000).to_a

Benchmark.bm(10) do |x|
  # with division
  x.report('div:') do
    total = arr.reduce(:*)
    arr.map { |i| total / i }
  end

  # with rotate
  x.report('rotate:') do
    arr.map.with_index do |i, n|
      arr.rotate(n).drop(1).reduce(:*)
    end
  end

  # with reduce
  x.report('reduce:') do
    arr.map do |i|
      arr.reduce { |t, j| i.equal?(j) ? t : t * j }
    end
  end
end