In interviews and in general, it usually is a good idea to get a correct yet inefficient solution and then try to optimize it. This usually yields better insights in my experience. Here is a quadratic solution:

https://gist.github.com/isbo/7239007