An Interesting Little Problem
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:
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 I had a spare 10 minutes, I decided to give it a shot … in Haskell.
I’ll cut to the chase, here’s the source to my solution:
vals :: [Int] vals = [ 4, 3, 2, 1, 2 ] answers :: [Int] answers = [ front !! (x-1) * back !! (x+1) | x <- [1..length vals] ] where front = scanl1 (*) temp back = scanr1 (*) temp temp = [1] ++ vals ++ [1]
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.
Yup, quite lazy, but very handy.
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:
#light let vals = [ 4; 3; 2; 1; 2; ] let mul a b = a * b let (++) = List.append let answers = let temp = [1] ++ vals ++ [1] let front = List.scan1_left mul temp |> List.to_array let back = List.scan1_right mul temp |> List.to_array seq { for x in [1 .. vals.Length] -> front.[x-1] * back.[x+1] }
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
In other words, my F# version smells like n00b. I’m sure there are so many better ways to implement this using the built-in features of the language and supporting libraries, but I’m yet to get to the level when I can write it. I’d love for someone to show me how
I did enjoy having a dabble with F# for the first time in ages, though I have to admit I much prefer using VIM and fsi.exe instead of Visual Studio and the interactive F# add-in.
As always, feedback and criticism welcomed (and needed).
Update
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.
-- by lf scanm f z xs = zipWith f (scanl f z xs) (tail $ scanr f z xs) main = print $ scanm (*) 1 [4,3,2,1,2] -- by Henning answers :: [Int] -> [Int] answers vals = zipWith (*) front (drop 1 back) where front = scanl (*) 1 vals back = scanr (*) 1 vals -- by desp problem input = zipWith (*) front back where front = init (scanl (*) 1 input) back = tail (scanr (*) 1 input) -- by foobar foo [] _ = ([], 1) foo (x:xs) acc = let (l, m) = foo xs (acc*x) in ((m*acc):l , m*x)
Thanks for the submissions guys Sorry for not including the imperative versions in the update.
@ashish: You haven’t read the question properly. It states that you are not allowed to use division in your answer. Since you’re using division, your solution doesn’t count.
Also, you should read the comments in the thread regarding the use of division and the issues around it. You end up with issues in the case where one of the items in the list is zero (among others).
Sorry I’m not too math minded – what does 0n mean?
C#
int[] arr = new int[] {4, 3, 2, 1, 2}; int[] output = new int[arr.Length]; for (int i = 0; i < arr.Length; i++) { int tally = 1; for (int j = 0; j < arr.Length; j++) tally *= j == i ? 1 : arr[j]; output[i] = tally; } return output;@Antk & @Ankhil: I’ve fixed up your formatting issues
I have installed a comment editing plugin, can you please let me know if it’s working for you?
@Antk: O(n) is an indication of the computational complexity of the algorithm. Check out this page at Wikipedia for a full run-down on Big O notation.
Cheers
OK guys, theme changed for a bunch of reasons. Comments now stop stripping + symbols
Thanks again for all the great feedback.
There’s a load more of these google questions here:-
http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html
Something to while away the hours/days/weeks!
You people make simple things so complicated:
#include <stdio.h> static int in[] = { 4,3,2,1,2 }; #define N (sizeof(in)/sizeof(*in)) int main(void) { int l[N] = {1}; int r[N] = {1}; for( int i = 0; ++i < N; ){ l[i] = l[i-1] * in[i-1]; r[i] = r[i-1] * in[N-i]; } for( int i = 0; i < N; i++ ) printf("out[%d] = %d\n", i, l[i] * r[N-1-i]); return 0; }“Sorry I’m not too math minded – what does 0n mean?”
It means that your solution is too slow, because the number of operations it performs is a (constant) multiple of N*N, i.e., O(N^2), but the problem is to do in in a number of operations that is a (constant) multiple of N, i.e., O(N).
“For example, the “sweep left, then sweep right” idea fails when there is a single zero (though it works for 2 or more zeros).
That’s silly. You really need to sharpen your mathematical intuition.
Simpler yet, per grahamf’s “in place” suggestion (except that this sweeps right to left and then left to right, so the results can be output in order without a separate print loop):
#include <stdio.h>
static int in[] = { 4,3,2,1,2 };
#define N (sizeof(in)/sizeof(*in))
int main(void)
{
int out[N];
for( int p = 1, i = N; –i >= 0; p *= in[i] )
out[i] = p;
for( int p = 1, i = 0; i < N; p *= in[i++] )
printf(”out[%d] = %d\n”, i, out[i] *= p);
return 0;
}
@truth machine: You need to ease up on your tone. People are just having a go at solving the problem themselves. So what if their solutions are “so complicated”? This is a learning experience for all. It’s what blogging is all about. I can’t see how your solution is any more or less simple than many others that have been posted. Get off your high horse mate
This sounds like the kind of problem that could quite neatly be solved using C++ template trickery or even entirely using the pre-processor in some (nasty) macro. If I get chance between nappy changes and feeds I’ll give it a go, just for the fun of it.
Ah yes, finding the time between nappy changes. I remember saying that too
It took nearly 4 months to find it! 
“So what if their solutions are “so complicated”? This is a learning experience for all.”
I was providing some education.
“I can’t see how your solution is any more or less simple than many others that have been posted.”
On;y if you mix apples and oranges. There are some ridiculously complicated C solution. Your own Haskel solution was ridiculously complicated compared to others.
@Truth machine – thanks for the 0n explanation – I’ve been looking into it.
Also, doesn’t your solution use the division operator?
a = [4, 3, 2, 1, 2] foo = [1]+([1] * len(a)) goo = [1]+([1] * len(a)) for i, x in enumerate(a): foo[i+1] = x * foo[i] for i, x in enumerate(reversed(a)): goo[i+1] = x * +goo[i] goo.reverse() print [foo[i] * goo[i+1] for i in range(len(a))][...] interview question on their site a few weeks ago and subsequently the problem was referenced by OJ’s rants and later posted to the programming subreddit on reddit.com. Like everyone else, I sat down and [...]
@ Ant K — maan, I like your innocence / sarcasm, whichever way you meant tat comment,
about tat guys soln having a division operator, so technically truth machine has published an incorrect ans [:P]