A Fibonacci Sequence is a sequence of numbers in which the first and second numbers in the sequence are 0 and 1 respectively, and additional numbers in the sequence are calculated by adding the previous two.

The first few numbers in the Fibonacci Sequence look like this:

0, 1, 1, 2, 3, 5, 8, 13, 21...

Often in technical interviews a person will be asked to “create a function that returns the nth value in a Fibonacci Sequence”. This can be done in a few simple steps as shown in the example below.

1. Create variables to hold the current values of the last two numbers. The first and second numbers in the sequence will always be 0 and 1 respectively. In this example we are assuming that n=0 represents the first number in the series. If 0 or 1 is passed to our function, then no calculation is needed. Simply return the value of n.

2. If n is greater than 1, then create a loop starting at 1 that will increment until reaching the value of n. During each iteration, calculate a new Fibonacci number by adding the values of the previous two numbers. Once this calculation is complete, update the previous two numbers to their new values. The first number should now be set to equal the second (more recent) number, and the second number should be set to the value of the newly calculated Fibonacci number (before the next iteration). Once the loop exits, return the calculated Fibonacci number.

package com.bigdatums.interview;

public class FibonacciIterative {

    public static int fibonacciIterative(int n) {
        int num1 = 0;
        int num2 = 1;
        int output = 0;

        if(n == 0)
            return 0;
        if(n == 1)
            return 1;

        for(int i=1; i<n; i++) {
            output = num1 + num2;
            num1 = num2;
            num2 = output;
        }
        return output;
    }

    public static void main(String[] args) {
        System.out.println(fibonacciIterative(0));
        System.out.println(fibonacciIterative(1));
        System.out.println(fibonacciIterative(2));
        System.out.println(fibonacciIterative(3));
        System.out.println(fibonacciIterative(4));
        System.out.println(fibonacciIterative(5));
        System.out.println(fibonacciIterative(6));
        System.out.println(fibonacciIterative(7));
        System.out.println(fibonacciIterative(8));
        System.out.println(fibonacciIterative(9));
        System.out.println(fibonacciIterative(10));
    }

}