[antirez]

I did not read the final solution but this was a little stimulating quiz, so this is my Ruby solution:

https://gist.github.com/antirez/7231559

[antirez]

ehm, no it is not so simple :-) I'll try better after lunch!

[pearkes]

Thank you for posting this and demonstrating how absolutely pointless these questions are for finding qualified candidates.

For those of you who didn't notice, antirez[1] makes a data storage system called "Redis"[2]

[1]: https://twitter.com/antirez

[2]: http://redis.io/

[antirez]

;-) I'm back, and I hopefully fixed it in the gist, adding a second pass (still O(N) but more complex implementation). Probably there are simpler ways, and indeed now I'm going to read the solution proposed in the blog post.

Edit: now that I read the solution, what I found is indeed the two passes solution and not the optimal one with the two pointers going in opposite directions.