Java interview question: Fibonacci Series

Fibonacci series is a sequence of numbers, in which, each number is the sum of it’s previous 2 numbers. The first 2 numbers in the sequence are by definition: 0 and 1.
For some reason, it seem like writing a Java function that returns Fibonacci number is favorited by interviewers. I really find it difficult to understand why an interviewer would ask this kind of question, since it is not a question that implies on any practical knowledge or experience and can be easily memorized.
But, anyway, let’s see how it is done:
There are 2 ways of writing this function: recursive and none recursive. Interviewers may ask to write both versions.
Let’s start with the recursive version, which is surprisingly simple. well… simple if do not try to debug it in your head, but think of the process in a more mathematical way. In general, I believe that solving recursion problems is much simpler if you think of the solution in an abstract way, rather than trying to figure what exactly going on on each iteration.
Well, this is how the recursive function looks like:

package com.bashan.blog.interview;
/**
* @author Bashan
*/
public class Fibonacci {
  public static int fibonacci1(int n)
  {
    if (n == 0)
    {
      return 0;
    }
    else if (n == 1)
    {
      return 1;
    }
    else
    {
      return fibonacci1(n - 1) + fibonacci1(n - 2);
    }
}
 
public static void main(String[] args)
  {
    System.out.println(fibonacci1(12));
  }
}

Note, that both 2 first numbers in the series are handled separately. The output of the test program is of course: 144.
This function can be shorten to a single line of code:

package com.bashan.blog.interview;
/**
* @author Bashan
*/
public class Fibonacci {
  public static int fibonacci2(int n)
  {
    return n == 0 ? 0 : (n == 1 ? 1 : (fibonacci1(n - 1) + fibonacci1(n - 2)));
  }
}

The none recursive version should always save the current and the previous number in order to calculate the next number in the series. Let’s see how it looks in Java code:

package com.bashan.blog.interview;
/**
* @author Bashan
*/
public class Fibonacci {
  public static int fibonacci3(int n)
  {
    int prevN = 0, currentN = 1;
    for (int i = 0; i < n; i++)
    {
      int saveCurrentN = currentN;
      currentN = prevN + currentN;
      prevN = saveCurrentN;
    }
   
    return prevN;
  }
}

Note, that we return prevN rather than currentN. This saves us for writing a logic to handle the case of n = 0.
Here is a Java class that contains all 3 functions.

Check out this cool infographic to learn more about Fibonacci series.

Java interview question: List “contains” method

This question verifies that you know how the “contains” method of List works.
Let’s have a look at this small piece of code:

Person person = new Person("guy");
List<Person> persons = new ArrayList<Person>();
persons.add(person);
System.out.println(persons.contains(person));

The question: Is it possible, that the output of this little piece of code returns: “false”.

At first look, the answer seems to be: NO, meaning, this code will always return “true”. So how can a “Person” object that was just created and added to a list, not be contained in it?

The answer, is in the way the “contains” method works. The “contains” method, is using the “equals” method in order to check if an object is contained in the list. Therefore, the code above can return “false” if the writer of the “Person” object overridden the equals method.

Java interview question: Count the number of “1” bits in a byte

Frankly, I think it is quite an idiotic question. Not because it is too easy or too hard question, but because I think this question doesn’t really imply on the practical programming capabilities of the person being interviewed. Anyway, a friend of mine was asked to solve this question, so I though it might be an interest for more developers looking for a job and having to handle all sort of weird questions.
In general, there are 2 solutions for this question:

• First solution is iterating 8 times (a byte contains 8 bits). Each time the right most bit is extracted from the byte. and then the byte is shifted right one bit.
• Second solution, is a little bit less straight forward, but more efficient: Divide the number by 2, if there is a modulo, count it. Repeat this operation as long as the number we are dividing is greater than zero.

Here is how the first solution looks in Java code:

public class GetBits {
public static int countBits(byte num)
{
  int count = 0;
  for (int i = 0; i < 8; i++)
{
    if ((num & 1) == 1) // check if right most bit is 1
{
count++;
}
num = (byte)(num >>> 1); // shit right 1 bit, including the sign bit
}
  return count;    
}

Here is how the second solution looks like:

public static int countBits(byte num)
{
  int count = 0;
  while (num > 0)
{
    if (num % 2 == 1) // check if number have modulo
{
count++;
}
num /= 2; // divide the number by 2
}
  return count;    
}

Note, that the first solution is a bit less efficient, because it always iterates 8 times. But, it handles both positive and negative values. The second solution will simply won’t work with negative numbers.