## Microsoft Interview Question

Software Engineer / Developers**Country:**-

good one. So you want to compute the whole pascal triangle, and then compute the weighted sums of the coefficients ?

This will be O(n^2) space. hmm.. I wonder if we can this with linear space ?

The pascal triangle was for illustration. Each element is a binomial coefficient that can be easily computed so no need for O(n^2) space.

sorry for stupidiness.. but I still did not get your solution

Each coefficient g[i] is a weighted sum of

coefficients f[i] where the weights are precisely the binomial coefficients.

But how do you want to compute g[i]'s without evaluating the whole pascal triangle first ?

My point is, as you have shown in your example,

to compute each g[i] you need to take one COLUMN of pascal triangle

but the triangle itself is evaluated in a ROW-WISE manner..

so you need to store the data somewhere

sorry for stupidiness.. but I still did not get your solution

Each coefficient g[i] is a weighted sum of

coefficients f[i] where the weights are precisely the binomial coefficients.

But how do you want to compute g[i]'s without evaluating the whole pascal triangle first ?

My point is, as you have shown in your example,

to compute each g[i] you need to take one COLUMN of pascal triangle

but the triangle itself is evaluated in a ROW-WISE manner..

so you need to store the data somewhere

synthetic division:

note that f(x) = g(x - 1) = (x-1)^n g[n] + ... + (x-1)g[1] + g[0]

hence we can compute the coefficients of g by iteratively dividing f by (x-1)

that is:

g_0 = f mod (x-1)

g_1 = (f div (x-1)) mod (x-1)

... and so on

one division with remainder costs O(n) ops because the degree of one polynomial is fixed

thus we have O(n^2) complexity and O(n) space

How can one calculate g_0 = f mod ( x -1 ) easily ???

Lets assume f(x) = a x^2 + b x + c

f(x) = g(x-1) = aa (x-1) ^ 2 + bb ( x - 1) + cc

Now the task is to find aa , bb , cc

to find cc you have a to do (a x^2 + b x + c) mod ( x -1 ) as per algorithm unless I am missing something.

well, that's easy. As I said just use a schoolbook division for polynomials. In fact, no "actual" division is require because the divisor is very simple - (x-1)

practice dividing ax^3 + bx^2 + cx + d by (x-1)

you will get: ax^3 + (b+a)x^2 + (c+b+a)x

and the remainder is (c+b+a+d) which is the trailing coeff of g

now divide ax^2 + (b+a)x + (c+b+a) by (x-1) again and so on

once you see the pattern, it's easy to come up with O(n^2) algorithm using O(n) space

I think row wise calculation of the entire Pascal triangle of order n is better than calculating binomial coefficients using combinatrice. Although calculation of Pascal triangle requires O(n^2) space but is much more time efficient than calculating binomial coefficients (remember we will have to find factorials of a large number of numbers a number of time :-) :P)

```
//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);
}
}
}
```

Find the maximum coefficient in f(x), say M, evaluate f(M+10000) and base it by M+9999, then we know the coefficients of g(x).

```
def poly(coeffs):
posCoeffs = [max(coeff, 0) for coeff in coeffs]
negCoeffs = [max(-coeff, 0) for coeff in coeffs]
return [i - j for i, j in zip(polyPos(posCoeffs), polyPos(negCoeffs))]
def polyPos(coeffs):
assert all(coeff >= 0 for coeff in coeffs)
M = max(coeffs) + 1000
v = polyEval(coeffs, M+1)
return base(v, M, len(coeffs))
def polyEval(coeffs, val):
v = 0
for coeff in coeffs:
v = v * val + coeff
return v
def base(val, base, numOfCoeffs):
# e.g. base(38, 6, 4) = [0, 1, 0, 2], 38 = 1 * 6*6 + 0 * 6 + 2 * 1
newCoeffs = [0] * numOfCoeffs
for i in range(numOfCoeffs):
m = val % base
newCoeffs[-(i+1)] = m
val -= m
val /= base
return newCoeffs
if __name__ == "__main__":
assert 199 == polyEval([5, 3, 1], 6)
assert [5, 13, 9] == poly([5, 3, 1])
assert [5, 13, 7] == poly([5, 3, -1])
```

For simplicity assume that n = 4

- Anonymous September 28, 2011Visualize 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