Microsoft Interview Question
Country: India
Little knowledge can be dangerous. Hopefully you won't be writing critical airplane software.
People got wrong all the time, we all learn from mistakes. So be nice, and if you have time, show your "big" knowledge.
wow, seems like someone took that the wrong way.
The idea behind this problem is similar as the way we solve Fibonacci in log(n) time costs, which we have to use matrix multiplication. so, even it has factor of 2, the basic algorithm is almost the same. What we need to do is to modify the Fibonacci algorithm a little bit, then we all set.
The Fibonacci algorithm:
| f(n+1) f(n) | = | 1 1 |^(n)
| f(n ) f(n-1) | | 1 0 |
Then we take a look at our problem:
| f(n+1) f(n) | =| 3 1 | *| 2 1 |^(n-1)
| f(n ) f(n-1)| | 1 0.5 | | 2 0 |
To solve our problem, I changed the
| 1 1 | to | 2 1 |
| 1 0 | | 2 0 |
because of the factor of 2. then in Fibonacci serious, the f(1) = 1 and f(2) =1 which is slightly different with our problem, in our problem, f(0)=0.5, f(1) = 1, f(2)=3, so I give it a initial matrix
| 3 1 | to let it start, then make the n to n-1, because
| 1 0 |
we've already got our initial matrix.
again, apologize for my little knowledge, I'm not writing code for airplane so no worries.
The quality of the original post, and the fact that one can easily write down the correct matrix instead of the fibonacci one, once you understand the approach, does make it sound like little knowledge.
Of course, looking at siren's other posts (not a huge sample though), looks like siren prefers brevity (unless tricked into explaining things better, like above :-)).
Use this :
| f(n-1) | | 2 2 | = | f(n) |
| f(n-2) | | 1 0 | | f(n-1) |
Matrix exponentiation over it will give f(n) in O(log(n))
The solution is correct, but there is a small problem with the notation of the vector:
You are multiplying a 2x1 matrix with a 2x2 matrix, and that is not possible.
Either swap places of vector and matrix, or define the vector horizontally (i.e 1x2 matrix).
| f(n-1) f(n-2) | x | 2 1 | = | f(n) f(n-1) |
| 2 0 |
Yes, it s correct this way only ( mine was just a representation that looks better ;) )
Can you explain how it is O(log(n))? You have to multiply the initial matrix [1 3] with [2 1 --- 2 0] n time. How this is O(log(n))?
Are you sure func(2) is 3? If func(1) = 1 then if func(0) = 0 func(2) becomes 2 and if func(0) = 1 then func(2) becomes 4. How do you arrive at the value 3?
or were you provided with f(0) by the interviewer? to create a basic matrix for the equation, f(0) is must.
f(0) = 1, it is obvious from the the given equation.
f(2) = 2*f(1) + f(0)
=> f(0) = f(2) - 2*f(1)
=> f(0) = 3-2 = 1
Follow the given parameters rather then making any assumptions.
Oh sorry,
f(n) = 2*f(n-1) + 2*f(n-2)
Then also we don't need f(0) to solve as base matrix can be multiplied with appropriate [f(n),f(n-1)] to get [f(n+1,f(n)]. So we can use f(n) = 3 and f(n-1) = 1 where n = 2. Use kth power of base to get f(2+k-1) i.e. f(k+1) or we can say f(n+1)
LOL! Given a recurrence, and two (required) initial values which define the whole sequence uniquely and you ask if the person is sure?
void Multipy(int a[4], int b[4], int c[4])
{
c[0] = a[0] * b[0] + a[1] * b[2];
c[1] = a[0] * b[1] + a[1] * b[3];
c[2] = a[2] * b[0] + a[3] * b[2];
c[3] = a[2] * b[1] + a[3] * b[3];
}
void Exp(int a[4], int b[4], int n)
{
if (n == 1)
{
memcpy(b, a, sizeof(int) * 4);
return;
}
if (n == 0)
{
b[0] = b[3] = 1;
b[1] = b[2] = 0;
return;
}
int half_n = int(n / 2);
int c[4];
Exp(a, c, half_n);
int c2[4];
Multipy(c, c, c2);
if (n % 2 == 1)
{
Multipy(c2, a, b);
}
else{
for (int i = 0; i < 4; i++)
b[i] = c2[i];
}
}
int main(int argc, char ** argv)
{
if (argc < 2)
return 0;
int n = atoi(argv[1]);
int a[4] = {2, 2, 1, 0};
int b[4];
Exp(a, b , n - 1);
int fn = b[0] + b1 / 2; // b1 must be even number, cause fn is a integer
cout << fn << endl;
return 0;
}
The Theorem which used in calculate Fibonacci number - cost O(lgn).
- siren0413 January 24, 2013you can search it on google, basically it's [[F(n+1),F(n)],[F(n),F(n-1)]] = [[1,1],[1,0]]^n.