Goldman Sachs Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
#include <stdio.h>
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
/* function that returns nth Fibonacci number */
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
/* Optimized version of power() in method 4 */
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if( n%2 != 0 )
multiply(F, M);
}
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Driver program to test above function */
int main()
{
int n = 9;
printf("%d", fib(9));
getchar();
return 0;
}
Dynamic programming approach:
1. Use Map to store calculated key/value pair.
2. BEfore using standard recursive approach, check if map contains calculated number. It it contains, then just return value else call function recursively.
static Map<Integer, Integer> map = new HashMap<Integer,Integer>();
map.put( 0, 0 );
map.put( 1, 1 );
DP_Fibonacci(40);
Set<Integer> keys = map.keySet();
for ( Integer key : keys ) {
System.out.print( map.get( key ) + " " );
}
int DP_Fibonacci( int n ) {
if ( !map.containsKey( n ) ) {
map.put( n, DP( n - 1 ) + DP( n - 2 ) );
}
return map.get( n );
}
But as you probably know, this is example of extremely inefficient implementation, in recursive calls,lot of things is calculated many times...
- tpcz March 05, 2013The better one is based on storing already calculated values..