Print a polynomial using minimum number of calls

Question

I keep getting these hard interview questions. This one really baffles me.

You're given a function poly that takes and returns an int. It's actually a polynomial with nonnegative integer coefficients, but you don't know what the coefficients are.

You have to write a function that determines the coefficients using as few calls to poly as possible.

My idea is to use recursion knowing that I can get the last coefficient by poly(0). So I want to replace poly with (poly - poly(0))/x, but I don't know how to do this in code, since I can only call poly. ANyone have an idea how to do this?

Alvis

This one makes NO sense to me at all. What is the name and meaning of the single integer parameter x when you call Poly(x)? Poly(coefficient_index)? It returns a coefficient? What does it return? Your question is not well defined. – Zebra

Do you know how many terms there are? – Chelseychelsie

@Warren: I think the OP means that for something of the form a + b.x + c.x^2 + d.x^3 + ..., evaluating for x=0 will give you a. – Chelseychelsie

No, you don't know the degree. That would help, I think. – Alvis

@warren: yeah. i know. I think I bombed it. I just have no idea how to do this, and that was all I could think of. – Alvis

Oli = it seems that x=0 returns the constant term, and that x=1 returns the sum of the constant terms and coefficients. – Zebra

Answer 1

Here's a neat trick.

int N = poly(1)

Now we know that every coefficient in the polynomial is at most N.

int B = poly(N+1)

Now expand B in base N+1 and you have the coefficients.

---

Attempted explanation: Algebraically, the polynomial is

poly = p_0 + p_1 * x + p_2 * x^2 + ... + p_k * x^k

If you have a number b and expand it in base n, then you get

b = b_0 + b_1 * n + b_2 * n^2 + ...

where each b_i is uniquely determined and b_i < n.

Antihelix

I don't understand this at all. – Alvis

So is n = N+1 in the example? – Alvis

I'll try to explain. Say poly = 4x^3 + 3x^2 + x + 2, just to simplify the argument. If you do poly(1), that gives you the sum of the coefficients of the polynomial, because you're just doing 4*1^3 + 3*1^2 + 1*1 + 2. Since all of the coefficients are non-negative, you know that poly(1) + 1 > any of the coefficients by itself. Now that you are confident of that, you can proceed to do poly(M), where M = poly(1) + 1. This would give you 4*M^3 + 3*M^2 + 1*M^1 + 2*M^0. This looks like the definition of a base number, base M (like binary is base 2, hexadecimal is base 16, etc). Continued... – Acerb

Ok. So how the hell was I suppose to think of doing that? – Alvis

So if you evaluate poly(M) base M, you get a number which would look like 4312 (base M). These happen to be your coefficients! Make sure you watch out, if one coefficient is zero, then there will be a zero in the number you get. Also, if you know a maximum bound on the polynomial coefficients, you can just skip the call to poly(1) and instead use that maximum bound + 1 as your value of M. We only care to make sure that M > than each coefficient. – Acerb

Cool. You're exploiting the fact that all quantities are NONNEGATIVE integers. I would have expected that we need as many calls as the degree. I believe this is the case for real-valued coefficients. – Mutant

@Szabolcs: Yes, I definitely need the nonnegativity. I don't know how to modify this for real coefficients if you don't know the degree in advance. – Antihelix

@PengOne, I believe that for real coefficients it is impossible to detect the degree, in the strict sense. – Mutant

@Antihelix Actually this observation (that if negative coefficients are allowed then we can't possibly detect the degree) can be a hint that the nonnegativity of coefficients is the key to finding an upper bound on the degree. It takes one one step closer to the solution you described. – Mutant

@Szabolcs: If you can find a number algebraically independent from the coefficients, then this will work for nonnegative reals. For example, poly(e) expanded in base e. This circumvents knowing the degree, but with negative coefficents, I'm at a complete loss. – Antihelix

@PengOne, exactly. It can be proven that with negative coefficients it is not possible to detect the degree with a finite number of calls to poly. Assume you calculated poly for n >> 2 values, and found that a 2nd degree polynomial described all n values completely. There exists a degree n polynomial that gives you exactly the poly(x_i) values for all x_i you called poly with, but it gives different values than the 2nd degree polynomial you found for any other value of x. Simply because given n points one can always find a degree n-1 polynomial that describes them. – Mutant

A strategy in real nonnegative case that succeeds with probability 1: Compute f(1) to get bound M for coefficients. Then take a random number X from [M,M+1] with uniform distribution, compute f(X) and express in base X. With probability 1 X will be algebraically independent of coefficients. – Libra

For possibly-negative integer case, if you know a bound N on absolute value of coefficients, you can query on 2N+1 and use a positional system with digits of negative value to get the answer: base-(2N+1) encoding with digits -N, -N+1, ..., N. en.wikipedia.org/wiki/Signed-digit_representation – Libra