Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have solved fibonacci series and then used the topdown and bottom up approaches to solve it. Also I have included the stairway climbing question as follows "You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has numStairs steps. Returns In how many distinct ways can you climb the staircase." Looking for code review, optimizations, best practices etc.

public final class Fibo {

                private Fibo() {} 

                /**
                 * Returns the nth number in the fibonacci sequence.
                 * 
                 * @param n     nth position in the fibo series, which starts from 0th position.
                 * @return      the nth number in the fibonacci series.
                 */
                /*
                 * TimeComplexity: O(n)
                 * Space Complexity: http://www.geeksforgeeks.org/g-fact-86/
                 */
                public static int fibo(int n) {
                    if (n <= 1) return n;
                    return fibo(n - 1) + fibo(n - 2);
                }

                /**
                 * Returns the nth number in the fibonacci sequence.
                 * 
                 * @param n     nth position in the fibo series, which starts from 0th position.
                 * @return      the nth number in the fibonacci series.
                 */
                /*
                 * Time complexity: O(n)
                 * Aux Space: O(n)
                 */
                public static int fiboTopDown(int n) {
                    if (n < 0) throw new IllegalArgumentException("The value of n: " + n  + " should be positive.");
                    final Map<Integer, Integer> fiboCache = new HashMap<Integer, Integer>();
                    return fiboCompute(n, fiboCache);
                }

                private static int fiboCompute(int n, Map<Integer, Integer> fiboCache) {
                    if (n <= 1) return n;

                    if (fiboCache.containsKey(n)) {
                        return fiboCache.get(n);
                    } 

                    int sum = fiboCompute (n - 1, fiboCache) + fiboCompute (n - 2, fiboCache); 
                    fiboCache.put(n, sum);

                    return sum;
                }

                /**
                 * Returns the nth number in the fibonacci sequence.
                 * 
                 * @param n     nth position in the fibo series, which starts from 0th position.
                 * @return      the nth number in the fibonacci series.
                 */
                /*
                 * Time complexity: O(n)
                 * Aux Space: O(1) 
                 */
                public static int fiboBottomUp(int n) {
                    if (n < 0) throw new IllegalArgumentException("The value of n: " + n  + " should be positive.");

                    int a = 0;
                    int b = 1;
                    int c = 0;
                    for (int i = 0; i < n; i++) {
                        a = b;
                        b = c;
                        c = a + b;
                    }
                    return c;
                }


                /**
                 * You are climbing a stair case. Each time you can either make 1 step or 2 steps
                 * The staircase has numStairs steps. Returns In how many distinct ways can you climb the staircase.
                 * 
                 * @param numStairs
                 * @return
                 */
                public static int stairCount(int numStairs) {
                    if (numStairs <= 0) throw new IllegalArgumentException("The number of stairs: " + numStairs  + "
        should be positive.");
                    return fiboBottomUp(numStairs + 1);
                }



                public static void main(String[] args) {

                    System.out.println(fibo(0) + ":" + fibo(1) + ":" + fibo(2) + ":" + fibo(3) + ":" + fibo(4) + ":" + fibo(5));

                    System.out.println(fiboTopDown(0) + ":" + fiboTopDown(1) + ":" + fiboTopDown(2) + ":"
                            + fiboTopDown(3) + ":" + fiboTopDown(4) + ":" + fiboTopDown(5));

                    System.out.println(fiboBottomUp(0) + ":" + fiboBottomUp(1) + ":"
                            + fiboBottomUp(2) + ":" + fiboBottomUp(3) + ":"
                            + fiboBottomUp(4) + ":" + fiboBottomUp(5));

                    System.out.println(stairCount(1) + ":"
                            + stairCount(2) + ":" + stairCount(3) + ":"
                            + stairCount(4) + ":" + stairCount(5));
                }
            }
share|improve this question

2 Answers 2

up vote 5 down vote accepted

This comment is inaccurate:

/*
 * TimeComplexity: O(n)
 * Space Complexity: http://www.geeksforgeeks.org/g-fact-86/
 */
public static int fibo(int n) { … }

A naïve recursive fibo() has O(2n) time complexity. Think of it this way: to calculate fibo(n), you break it up into two problems, each of size n - 1.

In fiboBottomUp(), don't declare/define int a = 0, since it is only ever used as a temporary variable inside the for-loop.

public static int fiboBottomUp(int n) {
    if (n < 0) {
        // Message is inaccurate: n = 0 is allowable
        throw new IllegalArgumentException("The value of n: " + n  + " should be non-negative.");
    }

    int b = 1;
    int c = 0;
    for (int i = 0; i < n; i++) {
        int a = b;
        b = c;
        c = a + b;
    }
    return c;
}

Using a HashMap<Integer, Integer> for fiboCache is more complicated than necessary. An ArrayList<Integer> or even an int[n + 1] will do, since all the keys are consecutive integers.

Consider widening your return types to long to stave off overflow for a while longer.

share|improve this answer
    
" Think of it this way: to calculate fibo(n), you break it up into two problems, each of size n - 1.", don't you mean one of size n - 1 and other of size n - 2, though ultimately every fibo(n) produces two problems of size O(n)? –  skiwi Jul 13 at 17:40

From a once over:

  • The parameter name in stairCount represents the number of steps, maybe it ought to be called numSteps instead of numStairs. Also, personally, I would prefer stepCount.

  • There really should be a new line after (numStairs <= 0) to make the code look better

  • That could give

    public static int stairCount(int stepCount) {
        if (stepCount <= 0) 
            throw new IllegalArgumentException("stepCount should be positive");
        return fiboBottomUp(stepCount + 1);
    }
    
  • Since you only work with int which is 32 bits, and so can only hold 46 numbers ( 46th is 1836311903 ), you might as well cache all 46 numbers and have your code run super fast.

  • This

    System.out.println(fiboBottomUp(0) + ":" + fiboBottomUp(1) + ":"
                     + fiboBottomUp(2) + ":" + fiboBottomUp(3) + ":"
                     + fiboBottomUp(4) + ":" + fiboBottomUp(5));
    

    is begging for a for loop to make it more DRY.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.