I've given plenty of interviews in my day. Almost all of them have been for highly technical positions; typically software development. Of all the interview questions I've ever asked, this one is my absolute favorite:

*"Write a function that can take the derivative of a single variable polynomial of any order. Perform this operation using the smallest number of operations possible."*

Now, normally the people freak - and that's okay. They hear "derivative" and start flailing around, their brain short circuiting from the stress of the interview situation, until they aren't entirely certain if a derivative is a mathematical construct or the pet name of a certain species of spotted owl. I would typically continue on to give them an example of a taking a derivative, just to refresh their memory. I also tell them that the function can take whatever input they feel is neccessary. I then give them 15 minutes to work on this.

No one has ever come close to answering the question right. Well, one guy did, and I hired him. Of the rest of the people that I hired, they all got close - but here's the trick. The question wasn't about finding the right answer. The question was about finding out how your brain worked by a) stressing you and b) requiring you to think logically under that stress.

Anyone care to take a stab at it? Brownie points for the first person to get it right. ðŸ™‚

PingBack from http://microsoft-sharepoint.simplynetdev.com/my-favorite-interview-question/

The derivative is just the slope of function at a point. To aproximate the derivative, sample the function at the point and at a small delta away then calculate the slope through the two samples.

I think you expect a polynomial as output. I will like this. I’ll represent a polynomial

Ax^(n) + Bx^(n-1) + … + C

as an array of length (n+1) like

[A, B, …, C]

with 0 wherever necessary.

For e.g. 4x^(3) + 5x will be represented as [4, 0, 5, 0].

Now to calculate derivative, I just need to multiply the ith value of input with the exponent of x at that point. Moreover, the output will contain one term less than input.

int[] derivative(int[] input) {

if (input == null || input.length < 1)

return null;

int order = input.length – 1;

int[] output = new int[order]; // note: 1 less

for (int i = 0; i < output.length; i++)

output[i] = input[i]*(order – i);

return output;

}

I want more information. Is this a numerical derivative such as dferg thinks or more symbolic as bsanghvi thinks? Also, what are some examples of single variable polynomial of any order? "x^2+x" might be single variable or might not depending on how you are defining it.

I think the example "x^2" fits while "x^2 + x" doesn’t given a single variable and an order as input. My answer there then is:

def derivative(variable, order):

return order * (variable ^ (order – 1));

You’d then find the derivative of x^2 at x=3 using:

derivative(3, 2)

and get a result of

6

There are, of course, issues of floating point and so forth. But if you used a duck-typed language, the above code could even work whether you wanted a symolic result or a numerical result depending on how operators are overloaded on the input objects. Fun stuff.

brantgurga:

You are absolutely correct. The expectation is that the output would be a symbolic expression; obviously, my statement of the question was a bit lacking.

As a result, bsanghvi gets the brownie points. The solution bsanghvi gives is the closest to exactly the right response; the only criticism I might give is that, as he uses an integer array, his function doesn’t obviously support fractional constants. 1 brownie point for brantgurga for point this out.