When was the last time you prayed?

goldenspiralPraying is a good technique for learning because when you recite something again and again, then you can learn it easily.

I was in a job interview today and there was a really simple test question I failed.

I had to write a method which gets an integer for Fibonacci sequence as index and returns the value of that index.

 

First of all I wrote the declaration of my method and created a block as its body and placed two checks in it. I wanted to check at the beginning of the processing if the argument is the first or second index. It is ok to return as soon as possible when we realized that there is no need to do more inside the method. I also knew that it had to be a recursive call. But I did not see that, I did not realize that these checks also be used as many as recursive call is done therefore they are the trigger for finishing the process.

The problem was that I was not able to realize that the two selections where I checked the index argument are also the BASE CASE!

fibo1This is the same as:

fibo2

At this moment the guys who interviewed me suggested using the following as it is written also here:

fibo5

The slide show about what is happening inside:

fibo_motionWhy does it work? Because every return value depends on previous returned values. This little code, little algorithm is like a prayer. Collect as many of them as you can and keep reciting them. They will be part of you. They will be in your heart, in your brain, in your blood. You do not have to think about the correct answer any more. That’s why praying is useful.

Example code with nasty built-in magic number:

(Magic number: Unique values with unexplained meaning or multiple occurrences which could (preferably) be replaced with named constants)

 

package fibonacciPkg;

public class FibonacciMain
{
  public static void main(String[] args)
  {
    TheFiboProcessor fP = new TheFiboProcessor();
    System.out.println(fP.getFiboValue(7));
  }
}

 

package fibonacciPkg;
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

public class TestTheFiboProcessor
{
  private TheFiboProcessor fP;
  @Before
  public void setUp() throws Exception
  {
    fP = new TheFiboProcessor();
  }

  @Test
  public void testFirstElement()
  {
    assertEquals(1, fP.getFiboValue(1));
  }
  @Test
  public void testSecondElement()
  {
    assertEquals(1, fP.getFiboValue(2));
  }
  @Test
  public void testThirdElement()
  {
    assertEquals(2, fP.getFiboValue(3));
  }
  @Test
  public void testFourthElement()
  {
    assertEquals(3, fP.getFiboValue(4));
  }
  @Test
  public void testFifthElement()
  {
    assertEquals(5, fP.getFiboValue(5));
  }
  @Test
  public void testSixthElement()
  {
    assertEquals(8, fP.getFiboValue(6));
  }
  @Test
  public void testSeventhElement()
  {
    assertEquals(13, fP.getFiboValue(7));
  }
  @Test
  public void testEighthElement()
  {
    assertEquals(21, fP.getFiboValue(8));
  }
  @Test
  public void testNinethElement()
  {
    assertEquals(34, fP.getFiboValue(9));
  }
}

 

package fibonacciPkg;
public class TheFiboProcessor
{
  public int getFiboValue(int index)
  {
    if(index < 3)
    {
      return 1;
    }
    return getFiboValue(index - 1) + getFiboValue(index -2);
  }
}

The command line which I used for testing (as you can see it is only one line)

java -cp .:fibonacciPkg/*:
   org.hamcrest.core_1.3.0.v201303031735.jar:junit.jar
       org.junit.runner.JUnitCore fibonacciPkg.TestTheFiboProcessor

And the output of it:

JUnit version 4.11
.........
Time: 0,01
OK (9 tests)
Advertisements
This entry was posted in algorithms, programming, theories and tagged , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s