This post was inspired by a recent interview question that was posted over at fsharp.it. It’s one of those neat little questions which looks really simple on the surface but is quite tricky.
The question apparently originates from an interview that someone had with Google, and goes something like this:
Since I had a spare 10 minutes, I decided to give it a shot … in Haskell.
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).
I’ll cut to the chase, here’s the source to my solution:
1 2 3 4 5 6 7 8 9
I’m hoping that this is quite self-explanatory. But in case it’s not, I’ll cover some of the gory bits.
The core of the problem is coming up with a way of determining the value of the product of numbers from the start of the list up to a given index, and to do the same at the other end of the list from that given index.
I thought that the easiest way would be to create two lists: both of them containing the compounded products of the numbers in the list, but each of them in different directions. To generate those lists, I thought that I’d add the value of 1 to the list, both at the start and at the end, as it would allow me to do two things:
- Generate the lists using the scanl1 and scanr1 functions.
- Index into the list using a counter that’s based on the size of the original values without having to worry about going past the bounds of the list.
Here’s the output when I execute answers in GHCi:
Prelude> :l google.hs [1 of 1] Compiling Main ( google.hs, interpreted ) Ok, modules loaded: Main. *Main> answers [12,16,24,48,24] *Main>
Problem solved in O(n). Neato! After feeling rather chuffed with myself I thought I’d go back to Fsharp.it and check out the answer posted there. The principle was similar, but the implementation listed was a little longer.
So I thought I’d have a go at writing up my solution using F#. It didn’t seem like a stretch until I realised how little of the language I know (I’m currently reading through Expert F#, but I’m still far from being one myself). Here’s what I came up with:
1 2 3 4 5 6 7 8 9 10 11 12
A few things you might notice:
- My syntax highlighter plugin doesn’t currently support F# :)
- I use a similar method to the Haskell solution, but ended up having to convert the front and back lists to arrays. The reason was because I need to be able to index into the resulting integer set, and I can’t do that with lists (if I’m wrong, please let me know!)
- I defined a function called mul which does a simple multiplication. I wanted to pass () as the first parameter to the scan1_ functions, but the interpreter took that as the start of a comment instead! So I had to resort to a dodgey hack. If you know a way around this, please let me know.
- I wrote my own (++) operator because I didn’t want to have to write List.append more than once :)
As always, feedback and criticism welcomed (and needed).
After some great feedback (see below), I’ve come to realise that the !! operator in Haskell is actually O(n) itself. Hence it was a bad choice for inclusion. Back to the drawing board for me!
Here are a couple of submitted Haskell solutions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Thanks for the submissions guys :) Sorry for not including the imperative versions in the update.