Here is a coding exercise I was asked to solve during a recent interview:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

This is a basic solution, it is what I consider a rough prototype.

/*
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
 */
package interviewQuestion;

import java.util.ArrayList;
import java.util.List;

public class Question2 {

    public static void main(String[] args) {

        long startTime = System.currentTimeMillis();
        System.out.println(getSumOfEvenNumbers(getFibonnociSequenceUpToFourMillion()));
        long endTime = System.currentTimeMillis();
        long totalTime = endTime - startTime;
        System.out.println(totalTime);

    }

    private static ArrayList<Integer> getFibonnociSequenceUpToFourMillion() {
        ArrayList<Integer> fibonnociSequence = new ArrayList();
        fibonnociSequence.add(new Integer(0));
        fibonnociSequence.add(new Integer(1));
        while (fibonnociSequence.get(fibonnociSequence.size()-1) < 4000000) {            
            fibonnociSequence.add(fibonnociSequence.get(fibonnociSequence.size()-1) + fibonnociSequence.get(fibonnociSequence.size()-2));
        }
        fibonnociSequence.remove(fibonnociSequence.size()-1);
        return fibonnociSequence;
    }

    private static int getSumOfEvenNumbers(List<Integer> addUpMyEvenNumbers) {
        int sumOfEvenNumbers = 0;
        for (int i = 0; i < addUpMyEvenNumbers.size(); i++) {
            Integer amIEven = addUpMyEvenNumbers.get(i);
            boolean numberIsEven = (amIEven % 2 == 0);
            if (numberIsEven) {
                sumOfEvenNumbers += amIEven;
            }
        }
        return sumOfEvenNumbers;
    }

}

Here is a more architected solution. Tasks have been separated into classes with clear and narrowly defined responsibilities. I consider this a decent draft 2. This code is still not ready to be used in a production system.

/*

Interview Question:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

*/

package interviewQuestion;

import java.util.List;

/**
 *
 * @author bkturley
 */
public class Question2 {

    public static void main(String[] args) {   
        StopWatch stopWatch = new StopWatch();
        stopWatch.start();
        long theAnswer = getTheAnswer();
        long answerCalculationTime = stopWatch.getElapsedTimeNanoSeconds();
        System.out.println("Answer: " + theAnswer);
        System.out.println("CalculationTime: " + answerCalculationTime);
        
    }

    private static Integer getTheAnswer() {
        
        FibonnociSequenceGenerator fibonnociSequenceGenerator = new FibonnociSequenceGenerator();
        List<Integer> fibonnociSequenceUpToFourMillion = fibonnociSequenceGenerator.getFibonnociSequenceUpTo(new Integer(4000000));
        
        EvenNumberFilter evenNumberFilter = new EvenNumberFilter();
        List<Integer> filteredListOfOnlyEvenNumbersFromFibonnociSequenceUpToFourMillion = evenNumberFilter.getEvenNumbersFromList(fibonnociSequenceUpToFourMillion);
        
        SumOfListContentsCalculator sumOfListContentsCalculator = new SumOfListContentsCalculator();
        Integer sumOfOnlyEvenNumbersFromFibonnociSequenceUpToFourMillion = sumOfListContentsCalculator.getSum(filteredListOfOnlyEvenNumbersFromFibonnociSequenceUpToFourMillion);
        
        return sumOfOnlyEvenNumbersFromFibonnociSequenceUpToFourMillion;
    }

}
package interviewQuestion;

import java.util.ArrayList;

public class FibonnociSequenceGenerator {

    public ArrayList<Integer> getFibonnociSequenceUpTo(Integer upToHere) {
        ArrayList<Integer> fibonnociSequence = new ArrayList();
        fibonnociSequence.add(new Integer(0));
        fibonnociSequence.add(new Integer(1));
        while (fibonnociSequence.get(fibonnociSequence.size()-1) < upToHere) {            
            fibonnociSequence.add(fibonnociSequence.get(fibonnociSequence.size()-1) + fibonnociSequence.get(fibonnociSequence.size()-2));
        }
        fibonnociSequence.remove(fibonnociSequence.size()-1);
        return fibonnociSequence;
    }
}
package interviewQuestion;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class EvenNumberFilter {
    
    public List getEvenNumbersFromList(List<Integer> getMyEvenNumbers){
        ArrayList<Integer> returnMe = new ArrayList();
        Iterator<Integer> iterator = getMyEvenNumbers.iterator();
        
        while(iterator.hasNext()){
            Integer nextValue = iterator.next();
            boolean nextValueIsEven = nextValue % 2 ==0;
            if(nextValueIsEven){
                returnMe.add(nextValue);
            }                
        }
        
        return returnMe;
    }
    
}
package interviewQuestion;

import java.util.Iterator;
import java.util.List;

public class SumOfListContentsCalculator {
    public Integer getSum(List<Integer> getTheSumOfMyContents){
        Integer returnMe = new Integer(0);
        Iterator<Integer> iterator = getTheSumOfMyContents.iterator();
        while(iterator.hasNext()){
            returnMe += iterator.next();
        }        
        return returnMe;
    }
}
package interviewQuestion;


public class StopWatch {
    private long startTime;
    
    public void start(){
        startTime = System.nanoTime();
    }
    
    public Long getElapsedTimeNanoSeconds(){
        long currentTime = System.nanoTime();
        return currentTime - startTime;
    }
}

 

A complete Solution:

 https://github.com/bkturley/fibonacciUnitTested

Fleshed out unit tests make this project ready for use in a production system.

Leave a Reply

Your email address will not be published. Required fields are marked *