CareerCup

Fib(n) denotes the 'n'th element in the fibonacci series
Sum(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.

We 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?

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.

Can a recursive algo work here:

fib(int n, int k)
{
for(i=0; i<k; i++)
{
if(n==i) return i;
}
if(n>k)
{
for(j=0; j<k; j++)
{
ans += fib(n-1, k);
}
return ans;
}
}

Can you share your programming exam experience in Sales Force?

int fib_n_k(int n, int k)
{

if (n<k) {
return n;
}
else {
int sum=0;
for (int i=1; i<=k; i++) {
sum+=fib_n_k(n-i,k);
}
return 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];

}}

function fib(n, k){
    var sum = 0;
    if (n<k) {
        return n;
    } else {
        for (var i=1; i<=k; i++) {
            sum += fib(n-i,k);
        }
    }
    return sum;
}
fib(6, 3); // 20

def fib(n, k): 
    # assume it is all initialized to 0
    last_k = [1] * k 

    for i in xrange(k, n+1):
        last_k[i%k] = sum(last_k)

    return last_k[n%k]

# test cases
for i in xrange(0, 10):
    print 'fib(%d, 3): %d' % (i, fib(i, 3)) 

for i in xrange(0, 10):
    print 'fib(%d, 4): %d' % (i, fib(i, 4))

<script>alert('hi');</script>

hi