Taken from the google interview question here
Suppose that you have a sorted array of integers (positive or negative). You want to apply a function of the form f(x) = a * x^2 + b * x + c to each element x of the array such that the resulting array is still sorted. Implement this in Java or C++. The input are the initial sorted array and the function parameters (a, b and c).
Do you think we can do it with O(n) time?
the question is rather easy, you know the f(x) is a parabolic curve, you first need to figure out the x-axis of the highest/lowest point, and then count number one by one from the lowest or from two end of the array
a*x^2 + b * x + c is monotonically increasing or decreasing on the two side of x_mid == -b / 2a. so if the number in the input array is all to the left or right of x_mid, the function would still remain sorted. If the number s in the input array overlap with x_mid, then starting from both end, the number with distance furthest to x_mid should be evaluated first.
a == 0 is a special case where the function become linear, and the resulting array is sorted.