HackerRank challenge to count ways to climb a staircase, solved using Java Fork Join

Question

I'm trying to solve Stair case recursion problem on HackerRank. The problem is to find all possible ways for a child to climb a stair case with height n given that he can jump 1, 2 or 3 steps at a time.

I'm using java Fork join to enhance performance but unfortunately it still slow. My approach is as follows:

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.RecursiveTask;

public class RecursiveStairCase extends RecursiveTask<Integer> {

/**
 * 
 */
private static final long serialVersionUID = 1L;
private Integer stairHeight;

public RecursiveStairCase(Integer stairHeight) {
    this.stairHeight = stairHeight;
}

@Override
protected Integer compute() {
    return getStairClimbPossibleWays(stairHeight);
}

static int getStairClimbPossibleWays(int stairHeight) {

    if (stairHeight < 0)
        return 0;

    if (stairHeight == 1 || stairHeight == 0)
        return 1;

    return getStairClimbPossibleWays(stairHeight - 1)
            + getStairClimbPossibleWays(stairHeight - 2)
            + getStairClimbPossibleWays(stairHeight - 3);
}

private List<RecursiveStairCase> createSubtasks() {
    List<RecursiveStairCase> subtasks = new ArrayList<RecursiveStairCase>();

    RecursiveStairCase subtask1 = new RecursiveStairCase(stairHeight - 1);
    RecursiveStairCase subtask2 = new RecursiveStairCase(stairHeight - 2);
    RecursiveStairCase subtask3 = new RecursiveStairCase(stairHeight - 3);

    subtask1.fork();
    subtask2.fork();
    subtask3.fork();

    subtasks.add(subtask1);
    subtasks.add(subtask2);
    subtasks.add(subtask3);

    return subtasks;
}

public static void main(String[] args) {
    Integer result = 0;
    long startTime = System.currentTimeMillis();
    int[] numbers = new int[] { 32, 33, 35, 36, 36 };
    for(int i=0;i<numbers.length;i++){
    result = 0;
    final RecursiveStairCase recursiveStairCase = new RecursiveStairCase(36);
    List<RecursiveStairCase> recursiveStairCases = recursiveStairCase
            .createSubtasks();
    for (RecursiveStairCase recursiveStairCaseThread : recursiveStairCases) {
        result += recursiveStairCaseThread.join();
    }
    System.out.println(result);
    }
    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println("Consumed:" + elapsedTime);
}
}

I recorded the following test cases/time consumed pairs (which is refused by HackerRank (timed out)).

Test Case #5 {35,30,33,36,20}-->9.47 sec
Test Case #8 {32,33,35,36,36}-->15.531 sec

I need your advice to make it perform faster.

Please add comments to your methods to explain what they're supposed to no, even though your code already does what it's supposed to do. — Kalle Richter
– Kalle Richter, Commented Jul 27, 2017 at 10:15

oopexpert · Accepted Answer · 2017-07-27 10:38:03Z

You may cache the results once you calculated it for one stair height like this:

static Map<Integer, Integer> cache = new ConcurrentHashMap<>();

static int getStairClimbPossibleWays(int stairHeight) {

    if (stairHeight < 0)
        return 0;

    if (stairHeight == 1 || stairHeight == 0)
        return 1;

    Integer ways = cache.get(stairHeight);

    if (ways == null) {
        ways = getStairClimbPossibleWays(stairHeight - 1) + getStairClimbPossibleWays(stairHeight - 2)
                + getStairClimbPossibleWays(stairHeight - 3);
        cache.put(stairHeight, ways);
    }

    return ways;
}

Imus · Accepted Answer · 2017-07-27 13:52:29Z

The reason your code still runs slow is the huge increase in how often you calculate the smaller steps.

If you want to find the number of ways for N steps. You calculate (N-1) once, (N-2) 2 times, (N-3) 4 times ..., (N-10) 274 times, ... (N-24) over a million times

Fun fact: the number of times you calculate (N-x) = calculateNumberOfWays(x).

oopexpert solved this by storing all the previous steps in a cache, so you calculate each step exactly once. This means it now takes O(N) recursive calls the first time the algorithm is called. And only 1 call afterwards (since it now became a lookup instead of a calculation).

The downside is that you actually store all intermediate results. An alternative solution is to not use recursion at all but work your way from the bottom up and store only the last 3 steps. An implementation could look like this:

public static int calculateNumberOfWays(int stairHeight){
    if(stairHeight < 0){
        return 0;
    }
    if(stairHeight < 2){
        return 1;
    }
    int twoStepsBack = 0;
    int previousStep = 1;
    int currentStep = 1;
    for(int i = 2; i <= stairHeight; i++){
        int nextStep = twoStepsBack + previousStep + currentStep;
        twoStepsBack = previousStep;
        previousStep = currentStep;
        currentStep = nextStep;
    }
    return currentStep;
}

This also has the next big advantage of not using recursion at all. Recursion in java is only good if you have a limited number of recursive steps. Otherwise you'll quickly run into a StackOverFlowError.

For example, running the following tiny program:

public static void main(String[] args) {
    recursionTest(0);
}

public static void recursionTest(int step){
    System.out.println(step);
    recursionTest(step+1);
}

Threw an error after printing 11412. For your problem giving input of over 10000 would be insane so it's probably not really an issue though which brings me to the next problem with your solution.

Both our solutions can only solve up to stairHeight 36. At 37 we get an integer overflow. Changing it from int to long allows up to 72.

If you want to work with really BIG integers, java has a BigInteger class. I'll leave the conversion to BigInteger to you (it's not that hard, as long as you remember to use someBigNumber.add(otherBigNumber) instead of the normal +).

Just for fun I tried to run it with n=10000 but the result is huuuuge (as expected). To give an idea, if I take result.toString().lenth() it's still 2647. But at least the program calculates this almost instantly :)

Stack Exchange Network

HackerRank challenge to count ways to climb a staircase, solved using Java Fork Join

2 Answers 2

You must log in to answer this question.

Hot Network Questions

HackerRank challenge to count ways to climb a staircase, solved using Java Fork Join

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions