There was an interesting post on ruby-talk mailing list. A problem was
presented as 'google hiring problem'. Problem is below:
> # There is an array A[N] of N integers. You have to compose an array
> # Output[N] such that Output[i] will be equal to the product of all
> # the elements of A[] except A[i].
> #
> # Example:
> # INPUT:[4, 3, 2, 1, 2]
> # OUTPUT:[12, 16, 24, 48, 24]
> #
> # Note: Solve it without the division operator and in O(n).
Since it is ruby mailing list we tried to solve it the rubyish way.
Here is my attempt:
input = [4,3,2,1,2]
output = []
input.each_index do |index|
odd_man_out = input[0...index] + input[index+1..-1]
starry_night = odd_man_out.join('*')
output << eval(starry_night)
end
puts output
A member, Ray Baxter, pointed out this was not O(n) but actually O(n^2)
saying that the eval I used is itself O(n-1).
1. I thought the eval used here is constant time. Please let me know
your opinion.
2. Is there any tool given the code computes the time complexity?
Cheers,
Ragu
