## The Fibonacci Number, A Logic Interview Question

Posted by d in interview questions, java, logic, programming questions on Wednesday, July 22, 2009

I've seen a share of logic questions recently and I'd like to share and discuss them. Obviously, my answers aren't the best out there but you may be able to use them to help you find some direction.

In an interview I was asked to program the Fibonacci Sequence/Number. Slow as I am sometimes, it took me a while to remember what a Fibonacci number was. In general there are three rules:

1) The Fibonacci number of 0 is 0.That is the Fibonacci number of 2 is equal to the Fibonacci number of 1 added to the Fibonacci number of 0. Or a Fibonacci number can be determined by the addition of the two Fibonacci numbers before it (other than 0 or 1). This is all well defined on Wikipedia.

2) The Fibonacci number of 1 is 1.

3) The Fibonacci number of any other number is determined by the function:

F(n) = F(n-1) + F(n-2)

So let's look at a series of Fibonacci numbers.

f(0) = 0Now before we look at the code, let's go over the business logic or rules. It's super easy.

f(1) = 1

f(2) = 1 + 0 = 1

f(3) = 1 + 1 = 2

f(4) = 2 + 1 = 3

f(5) = 3+ 2 = 5

f(6) = 5 + 3 = 8

f(7) = 8 + 5 = 13

- We'll need a function that returns an int and accepts an int as an argument
- When you pass in the value of 0, return the value of 0
- When you pass in the value of 1, return the value of 1
- When you pass in the value of anything else, return the value of the method with n-1 added to the value of the method with n-2

A Java implementation of this using recursion is:

class FiboTest {

public static int fibo(int num) {

if (num == 0) return 0;

else if (num == 1) return 1;

else {

return fibo(num-1) + fibo(num-2);

}

}

// This will test out the fibonacci numbers for 0, 1, 2, 3, 4, 5, 10, and 20

public static void main(String args[]) {

System.out.println(fibo(0));

System.out.println(fibo(1));

System.out.println(fibo(2));

System.out.println(fibo(3));

System.out.println(fibo(4));

System.out.println(fibo(5));

System.out.println(fibo(10));

System.out.println(fibo(20));

}

}

In my Intro-to-Programming course, I presented this problem to my students. One of them attempted to program it without using recursion and opting for a simple iterative loop. His code looks like:

import java.util.Scanner;

public class Fibonacci

{

public static void main(String args[])

{

Scanner input = new Scanner(System.in);

// Time to initialize a bunch of variables

int countto;

int counting;

int num1L;

int num2L;

int num3L;

// Starting values

counting = 1;

num1L = 0;

num2L = 0;

System.out.print ("What number in the fibonacci sequence do you want? ");

countto = input.nextInt();

if (countto == 0)

num3L = 0;

else

num3L = 1;

while (countto > counting)

{

num1L = num2L;

num2L = num3L;

num3L = num1L+num2L;

counting = counting+1;

}

System.out.println(num3L);

}

}

}

Want more interview questions? I've blogged recently about some of the questions I've been asked. You might want to glance over them to what employers are asking these days:

Interview Questions from a Government-Influenced Company

Interview Questions from a Start-Up

Interview Questions from a Mid-Sized Company

This entry was posted on Wednesday, July 22, 2009 at 4:12 PM and is filed under interview questions, java, logic, programming questions. You can follow any responses to this entry through the RSS 2.0. You can leave a response.

# by Anonymous - July 22, 2009 at 6:55 PM

I still don't get recursive stuff. Tanx for the help though, I'll be sure to learn this...

Post a Comment