given a polynomial f(x) of degree n, i.e......

Interview Questions

Microsoft Interview Questions and Answers

28. given a polynomial f(x) of degree n, i.e......

Question:
given a polynomial f(x) of degree n, i.e.:
f(x) = f[n]*x^n + f[n-1]*x^[n-1] + ... + f[0]

propose an efficient algorithm to computing
the coefficients of g(x) = f(x+1), assume arithemtic overflow cannot occur.
Example: f(x) = 5*x^2 + 3*x - 1
g(x) = f(x+1) = 5*x^2 + 13*x + 7

maybe an answer1:

For simplicity assume that n = 4

Visualize the pascal triangle

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 ignore last row because n = 4

g(x) = a x ^ 4 + b x ^ 3 + c x ^ 2 + d x + e

e = 1 * f[0] + 1 * f[1] + 1 * f[2] + 1 * f[3] + 1 * f[4] last column
d = 1 * f[1] + 2 * f[2] + 3 * f[3] + 4 * f[4] second last column
C = 1 * f[2] + 3 * f[3] + 6 * f[4] third last column
b = 1 * f[3] + 4 * f[4]
a = 1 * f[4]

This follows because
in general
if f(x) = a x ^ 2 + b x + c

g(x) = a (x+1)^2 + b ( x + 1 ) + c
= a (x^2 + 2x + 1 ) + b ( x + 1 ) + c
= a x^2 + 2 a x + a + b x + b + c
= a x^2 + ( 2a + b ) x + ( a + b + c)

and you can see that coefficents are nothing but addition of pascal columns as I have drawn above

maybe an answer2:

//Using SHIFT and ADD method to construct (x+1)^i : 2<=i<= n //at any point of time if you have (x+1)^i, we can connstruct (x+1)^(i+1) by simple
//shift and add. Ex. (x+1)^2 = 1 + 2^x + x^2
//to compute (x+1)^3 shift the coefficients of (x+1)^2 to the right one posiition then add to (x+1)^2. as follows

x^0 x^1 x^2 x^3
(x+1)^2 = 1 2 1 0
SHIFT 0 1 2 1
ADD 1 3 3 1 = (x+1)^3

using System;
using System.Collections.Generic;
using System.Text;

namespace PolynomialsProg
{
class Program
{
//This function will construct (x+1)^n polynomail
//using SHIFT and ADD method
static void ConstructPolyDegN(int[] poly, int n)
{
for (int i = n-1; i >= 0; i--)
{
int temp = poly[i];
poly[i] = 0;
poly[i + 1] += temp;
poly[i] += temp;
}
}
//This function add the poly of the form factor*(x+1)^n to the result
static void AddPolynomials(int[] result, int[] poly, int factor, int n)
{
for (int i = 0; i <= n; i++)
result[i] += factor*poly[i];

}
static void Main()
{
int degreeN; //the degree of the input polynomail
Console.Write("The degree of the polynomail: ");
degreeN = int.Parse(Console.ReadLine());
int[] origianlCoefficients = new int[degreeN+1];
int[] result = new int[degreeN+1];
int[] polynomial = new int[degreeN+1]; //will be used to construct the
//polynomials (x+1)^i: 1<=i<=n

//Read the input polynomail from the user
for (int i = 0; i <= degreeN; i++)
{
Console.Write("X^{0}: ", i);
origianlCoefficients[i] = int.Parse(Console.ReadLine());
}

polynomial[0] = polynomial[1] = 1; //this is (x+1)
result[0] = origianlCoefficients[0];

for (int i = 1; i <= degreeN; i++)
{
if (i > 1)
ConstructPolyDegN(polynomial, i);

AddPolynomials(result, polynomial, origianlCoefficients[i], i);
}

//Diplay the output
for (int i = 0; i <= degreeN; i++)
if(i == 0)
Console.Write("{0}+ ", result[i]);
else
Console.Write("{0}X^{1} + ", result[i],i);

}
}
}

(Continued on next question...)