13

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?

Daniel
  • 944
  • 1
  • 7
  • 24
  • 1
    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. – Warren P Jul 09 '11 at 19:10
  • 1
    Do you know how many terms there are? – Oliver Charlesworth Jul 09 '11 at 19:11
  • 4
    @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`. – Oliver Charlesworth Jul 09 '11 at 19:13
  • No, you don't know the degree. That would help, I think. – Daniel Jul 09 '11 at 19:19
  • @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. – Daniel Jul 09 '11 at 19:27
  • Oli = it seems that x=0 returns the constant term, and that x=1 returns the sum of the constant terms and coefficients. – Warren P Jul 10 '11 at 17:09

1 Answers1

28

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.

PengOne
  • 48,188
  • 17
  • 130
  • 149
  • 1
    I don't understand this at all. – Daniel Jul 09 '11 at 19:19
  • So is n = N+1 in the example? – Daniel Jul 09 '11 at 19:25
  • 4
    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... – Draksis Jul 09 '11 at 19:26
  • 4
    Ok. So how the hell was I suppose to think of doing that? – Daniel Jul 09 '11 at 19:28
  • 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. – Draksis Jul 09 '11 at 19:29
  • 5
    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. – Szabolcs Jul 09 '11 at 19:31
  • @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. – PengOne Jul 09 '11 at 19:50
  • @PengOne, I believe that for real coefficients it is impossible to detect the degree, in the strict sense. – Szabolcs Jul 09 '11 at 19:55
  • @PengOne 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. – Szabolcs Jul 09 '11 at 20:04
  • @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. – PengOne Jul 09 '11 at 20:05
  • @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. – Szabolcs Jul 09 '11 at 20:16
  • 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. – sdcvvc Jul 09 '11 at 20:25
  • 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. http://en.wikipedia.org/wiki/Signed-digit_representation – sdcvvc Jul 10 '11 at 00:47