## Salesforce Interview Question

Software Engineer / DevelopersWe need to know what the intial k values are, i.e. it should be part of the input.

Call the list of initial values the vector f = [f(k) f(k-1) ... f(1)]

Let A be the k by k matrix

A = [ 1 1 ... 1] [1 0 0 ..0] [0 1 ...0] [0 0 1 ...0] ... [0 .... 1 0]

Calculate A^n * f . One of the entries (I will let you figure out which one) is Fib(n,k)

This has O(k^3 log(n)) running time.

why do we need vector and matrix? fib(n,k) is just a series which extends 2 to k, right?

Fib(n,k) is a particular term in an infinite sequence. What do you mean extends 2 to k?

Also, the matrix is used to give a very efficient algorithm, using only integer multiplication/addition.

The normal iterative methods will be O(kn) i suppose. That matrix if O(logn * M(k)) where M(k) is the complexity of multiplying two k by k matrices. The trivial algo for multiplication is O(k^3), but better ones exist.

Another aspect of using matrices is that it can be parallelized very easily. Try doing that with the iterative version.

That's a nice technique. It's called memoization. http://en.wikipedia.org/wiki/Memoization

We can re-use the space for keeping track of k terms. Hence, o(k) space.

The running time however is O(nk) and not O(n) since we have to traverse k locations in the array to find the current sum.

//Alternate implementation

void fib(int n, const int type)

{

vector<int> track;

// Insert first K number of series in vector

for(register int i =0 ;i < type ;i++)

track.push_back(i);

// check if N is less then type

int t = n>=type?type:n;

for(register int i =0 ;i<t;i++)

cout<< track[i] <<" ";

//Start series

for(register int i=2;i< n;i++)

{

int newNum =0;

for(register int j = 0 ;j <type;j++)

newNum += track[j];

cout<< newNum <<" ";

track.erase(track.begin()); //remove the first number so that all number shift by 1 postion

track.push_back(newNum); // insert a new fib number

}

}

<pre lang="" line="1" title="CodeMonkey54649" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));

String s;

while (!(s=r.readLine()).startsWith("42")) System.out.println(s);

}

}

</pre><pre title="CodeMonkey54649" input="yes">

</pre>

<pre lang="" line="1" title="CodeMonkey98982" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));

String s;

while (!(s=r.readLine()).startsWith("42")) System.out.println(s);

}

}

</pre><pre title="CodeMonkey98982" input="yes">

</pre>

```
public class ModifiedFibonacci{
public static void main(String[] args) {
int n = 10;
int k = 3;
int [] array = new int[n];
fibonacci(n-1,k,array);
System.out.println("dss");
for(int i = 0;i<array.length;i++){
System.out.println(array[i]);
}
}
private static int fibonacci(int n, int k,int[] array){
if(n <= 0)
return 0;
if(n == 1){
array[1] = 1;
return 1;
}
/*if(n == 2)
return 1;
*/
if(array[n]>0){
return array[n];
}
int sum =0;
for(int i =k;i>=1;i--){
sum += fibonacci(n-i, k, array);//+ fibonacci(n-1, k, array);// +fibonacci(n-3, k, array);
}
array[n]= sum;
return array[n];
```

}}

Fib(n) denotes the 'n'th element in the fibonacci series

- csl March 29, 2009Sum(n) denotes summation of first n elements in the fibonacci series.

Algo :

Always maintain an array of (k+1) summations.

If you are calculating Fib(n+1) the array should have Sum(n-k),Sum(n-k+1) ... Sum(n-1),Sum(n)

Now Fib(n+1) = Sum(n) - Sum(n-k)

Now update the summations array so that it contains Sum(n-k+1),Sum(n-k+2) ... Sum(n),Sum(n+1)

Sum(n+1) = Sum(n) + Fib(n+1)

Now Fib(n+2) = Sum(n+1) - Sum(n-k+1)

Again update the summations array and continue with same thing

Example : Let k=3. Fib(1)=1, Fib(2)=2, Fib(3)=3

Fibonacci series : 1,2,3,6,11,20,37,68 ...

Summations array [1,3,6, dont have the 4th summation yet]

Fib(4) = 6

Summations array [1,3,6,12]

Fib(5) = Sum(4) - Sum(1) = 12 - 1 = 11

Summations array [3,6,12, 12+11 ] = [3,6,12,23]

Fib(6) = Sum(5) - Sum(2) = 23 - 3 = 20

Summations array [6,12,23, 23+20 ] = [6,12,23,43]

Fib(7) = Sum(6) - Sum(3) = 43 - 6 = 37

Summations array [12,23,43, 43+37 ] = [12,23,43,80]

Fib(8) = Sum(7) - Sum(4) = 80 - 12 = 68

Summations array [23,43,80, 80+68] = [23,43,80,148]

... So on ...

This runs in O(n) time and takes O(k) space.