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.