Sorting result array

Question

I was asked this question in Adobe interview:

We have an integer array that is sorted in ascending order. We also have 3 integers A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and return the corresponding sorted array.

Example I was given:

Input array = -1 0 1 2 3 4
A = -1, B = 2, C = -1`

Result of applying the formula to each element = -4 -1 0 -1 -4 -9
So expected result = -9 -4 -4 -1 -1 0 (sorted)

My best solution was to apply formula and sort it resulting in O(nlogn) solution. I could not do it better.

Any guidance in improving it is helpful.

Answer 1

The equation given is parabolic. So the result of applying it to a sorted array will result in an array that will have a maximum/minimum with the sub-arrays to its left and right sorted.

In your case the maximum is 0 and the sub array to its left [-4 -1] is sorted in ascending order and the sub-array to its right [-1 -4 -9] is sorted in descending order.

All you need to do is merge these sorted arrays which is linear in time.

So the algorithm is:

1. Apply equation on each element
2. Find maximum/minimum
3. Merge subarrays

Answer 2

You can do this in O(n). Find the minimum value of the polynomial which occurs when

2 * A * x + B = 0

so that

x_min = -B / 2 * A.

Then, walk the array until you find the integer closest to x_min. This is O(n). From here, successively pick from the left or right of this element depending on whether or not |x_min - left| is smaller or greater than |x_min - right|. Return the values of evaluating the polynomial at these points in the resulting order. This is O(n).

This assumes that A is positive. You can handle the case of negative A similarly.

Example:

input array = -1 0 1 2 3 4 A = -1, B = 2, C = -1

Here, the maximum value occurs at x_max = -2 / 2 * -1 = 1. From the input array, the closest value is 1, the third element. Then we successively pick the elements in the following order based on their distance to 1.

1, 0, 2, -1, 3, 4

Then, because A is negative, we have to run these in reverse order

4, 3, -1, 2, 0, 1

and evaluate the polynomial on them

-9, -4, -4, -1, -1, 0

Done.

Note that we are exploiting a special property of parabolas. Namely, for x less than x_extreme and A positive, applying the polynomial to such x is a decreasing function of x. For x greater than x_extreme and A positive, applying the polynomial to such x is an increasing function of x. (Similar reasoning applies if A is negative.) Thus, partition the array into two pieces, those x less than x_extreme and those x greater than x_extreme. Then apply the polynomial to these two pieces to end up with two arrays which are sorted. Now apply merge sorted to these sorted arrays. Note that the above description is effectively the merge sort.

Answer 3

The solution is O(N) and there is no need to perform any calculus, although it helps to understand the shape of the curve.

The answers above are doing the most intuitive thing and solving the equation to find the minimum or maximum and then splitting the list.

There is an advantage in calculating the first derivative but no need to actually do so, nor do we need to find the maximum or minimum point at this time.

Just know that it could move in one direction and then back in the other direction but will never change direction more than once.

We are going to start at each end and iterate across from both sides until we merge somewhere in the middle. Before we do anything else we need to check the direction at each end, which we will do by just comparing the end two elements. So we see if one end is moving upward and the other downward.

If we have N elements let's say we have data X[0] and X[N-1] so calculate f(X[0]) and f(X[N-1]) and f(X[1]) and f(X[N-2]). If f(X[0]) < f(X[1]) and f(X[N-1]) > f(X[N-2]) then actually all our data is one side of the maximum/minimum and thus already sorted. Same if the comparisons are in the other direction. (One direction may require a reverse).

Otherwise just perform the merge from both ends, thus f(X[0]) and f(X[N-1]) are either maxima or minima of their sub-ranges (we know from the earlier comparisons) and create the merged list from whichever is the appropriate direction.

Applying to your data:

-1 0 1 2 3 4
A = -1, B = 2, C = -1`

f = [ -4, -1, 0, -1, -4, -9 ]

-4 < -1 and -9 < -4 so we do cross the point and we have minima at each end.

-9 is lower than -4
-4 and -4 are equal so push both
-1 and -1 are equal so push both
0 remains.

our sequence is [-9, -4, -4, -1, -1, 0 ]

Answer 4

You can recognise that the result of applying the quadratic to the data is nearly sorted (as described in answers above, or by recognising that the derivative of a polynomial of degree n is continuous, of degree n - 1, and has at most n zeros).

So if you have a sorting routine in your library that does something clever with almost sorted data (such as a mergesort which keeps this in mind), you can just throw the data at it and expect linear performance. Searching the web finds Which sort algorithm works best on mostly sorted data? which points at http://svn.python.org/projects/python/trunk/Objects/listsort.txt.