An Interview Question

At a recent job interview I was asked to write a program to solve the following problem:

You have a sorted array of integer values, you need to generated a sorted array of the results of the results obtained when there values are plugged into the quadratic equation ax^2 + bx + c.

My first thought was that this was a problem best suited to the J programming language. Unfortunately I did not have my handy dandy J dictionary with me, and I do not have it memorized, so I had to wait until I got home to write:

fa =: monad : '/:~(c,b,a)p.y'

A J expert would make this tacit, and therefor shorter, but I'm not that good yet.

Using C++ with the Boost Lambda Library I would write:

std::Vector& fa(std::Vector& x)
{
    std::transform(x.begin(), x.end(), x.begin(), a*_1*_1 + b*_1 + c);
    std::sort(x.begin(),x.end());
    return x;
}

This does all the work in place so it only consumes memory for one array.

It can be made more efficient by taking advantage of the fact that the input array is sorted, so sorting the output array can be done in linear time, but that is left as an exercise for the reader.

I should look into how to do it in Ocaml, Erlang and Oz. But I do not think any of them will be as succinct as J or as efficient as C++. If the polynomial were of higher order it might be worth pursuing an Erlang solution that distributed the evaluation of the polynomial across several machines.