Java coding question on the popular Fibonacci sequence

The Fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and 89 on to infinity is popular with the interviewers. The sequence has a series of interesting properties. The sum of any two consecutive numbers equals the next highest number. After the first four numbers, the ratio of any number to its next highest number approaches 0.618. The ratio of alternate numbers approach .382. These ratios are often simplified to the key Fibonacci levels 38%, 50%, and 62% and used in stock trading analysis, growth in living things like reproduction of rabbits, arrangement of leaves in a plant, scales of pineapples, etc. So, why is this asked in programming interview questions? This is to see if you can think logically and write code. Here are a few questions on this Fibonacci sequence.

The Fibonacci numbers under 2000 are : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597.

Where the zeroth number being 0, first number being 1, second number being 1 (i.e. 0+1), third number being 2 (i.e. 1+1), fourth number being 3 (i.e. 1+2) and so on till the 17th number being 1597 (i.e 610 + 987).

Q. Can you write a function to determine the nth Fibonacci number?
A. This can be achieved with recursion or iteration. You can learn more about recursion at iteration Vs recursion. If you provide an iterative solution then there will be follow up question to write recursive solution and vice versa.

Recursive solution:

public class RecursiveFibonacci {
 
 public int fibonacci(int n){
  if(n<0){
    throw new IllegalArgumentException("Input parameter is invalid " + n); 
  }
  
  if(n == 0){
    return 0;
  }
  
  else if(n <= 2){
    return 1;
  }
  else {
    return fibonacci(n-1)+fibonacci(n-2); // head recursion
  } 
 }
 
 public static void main(String[] args) {
   int nThfibonacciNo = new RecursiveFibonacci().fibonacci(17);
   System.out.println(nThfibonacciNo);
 }

}

As per the above implementation

fibonacci(0) = 0;
fibonacci(1) = 1;
fibonacci(2) = 1;
fibonacci(3) = fibonacci(3-1) +  fibonacci(3-2) = fibonacci(2) +  fibonacci(1) = 1 + 1 = 2

The 5th  fibonacci number will be:

Recursion 1:  [ fibonacci(4) + fibonacci(3) ]
Recursions 2 and 3:  [ fibonacci(3)+ fibonacci(2) ] + [ fibonacci(2) + fibonacci(1) ]
Recursions 4, 5, 6, and 7: [ fibonacci(2) ] +  [ fibonacci(1) ] + [1] + [1] + [1]
Recursion 8 and 9: [1] + [1] + 1 + 1 + 1 = 5

Each recursion is shown with [ ].  So, the 5th fibonacci number is 5.

Iterative Solution:

public class IterativeFibonacci {

 public int fibonacci(int n) {
  if (n < 0) {
   throw new IllegalArgumentException("Input parameter is invalid " + n);
  }

  int num1 = 0, num2 = 1;
  
  //zeroth fibonacci number is 0
  if (n == 0)
   return 0;
  
  //first and second fibonacci numbers are 1 and 1
  if (n == 1 || n == 2)
   return 1;
  
  int current = num1 + num2;
  
  //compute from the third number onwards by adding the previous fibonacci number
  for (int i = 3; i <= n; i++) {
   num1 = num2;            
   num2 = current;            
   current = num1 + num2;
  }
  
  return current;
 }

 public static void main(String[] args) {
  int nThfibonacciNo = new IterativeFibonacci().fibonacci(17);
  System.out.println(nThfibonacciNo);
 }

}

The output is: 1597

Diagrams can often simplify things and gives better clarity.

Q. How will you compute the sum of all even Fibonacci numbers under 2000?
A. This is a bit of a twist to evaluate your ability to construct the logic

public class TwistedFibonacci {

 public static void main(String args[]) {
  int num1, num2, current, evenSum;
  num1 = 0;
  num2 = 1;
  current = num1 + num2;
  evenSum = 0;

  while (current + num2 < 2000) {
   num1 = num2;
   num2 = current;
   current = num1 + num2;
   
   if (current % 2 == 0) { // if the remainder is zero then even number
    if (current > 0) {
     System.out.println(current);
    }

    evenSum += current;
   }
  }

  System.out.println("Sum of the even Fibonacci numbers  under 2000: " + evenSum);
 }
}

The output is:

2
8
34
144
610
Sum of the even Fibonacci numbers  under 2000: 798

Unit tests are not shown, but in actual interviews, you must show unit tests as well.