## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: -

Comment hidden because of low score. Click to expand.
3
of 3 vote

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 + 1 * f + 1 * f + 1 * f + 1 * f last column

d = 1 * f + 2 * f + 3 * f + 4 * f second last column

C = 1 * f + 3 * f + 6 * f third last column

b = 1 * f + 4 * f

a = 1 * f

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

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

synthetic division:

note that f(x) = g(x - 1) = (x-1)^n g[n] + ... + (x-1)g + g
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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

for (int i = 1; i <= degreeN; i++)
{
if (i > 1)
ConstructPolyDegN(polynomial, 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);

}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

wow did Microsoft really ask this?!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone do better than O(n^2) time? I've only thought about this for 5-10 minutes, but O(n^2) time and O(n) space is the best I have so far.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 =  * 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])``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.