## Skill Subsist Impulse Ltd Interview Question for Software Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Hi this is one of this problems that looks extremaly intimidating but somehow ends up being easy. If you check the number of ways for first few stairs length you can see that ways one can climb a staircase in respect to staircase length grows exacly like fibonacci number sequence. Lets say one step move = 1, and two steps move = 2. Possible ways for:
1 step staircase => 1 = {1} -> 1 way
2 step => 2 = {1+1}, {2} -> 2 ways
3 step => 3 = {1+1+1}, {1+2}, {2+1} -> 3 ways
4 step => 4 = {1+1+1+1}, {1+1+2}, {2+1+1}, {1+2+1}, {2+2} -> 5 ways
5 step => 5 = {1+1+1+1+1}, {2+1+1+1}, {1+2+1+1}, {1+1+2+1}, {1+1+1+2}, {2+2+1},
{1+2+2}, {2+1+2} = 8 ways.
ways(5) = ways(4) + ways(3) = 5 + 3 = 8.
I use sequencial code for optimal space complexity and additional array to store partial results to reduce time complexity to linear.

``````public static int countWays(int n)
{
if(n < 1)return -1;
if(n == 1)return 1;
int res[] = new int[n+1];
res = 1;
res = 2;

for(int i = 3; i < n+1; i++)
{
res[i] = res[i-1] + res[i-2];
}

return res[n];
}

public static void main(String args[])
{
for(int i = 1; i < 10; i++)
System.out.println(countWays(i));
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

bogdan.zima is of course correct. A better way to prove is this identity.
suppose the no of ways you can take step n is defined by a function step(n).
Now, clearly, as only 1 or 2 step at a time are allowed, you could have reached step(n)
by :

one step + take rest of (n-1) OR two steps + take rest of (n-2) steps.
Tow independent count of choices, and thus must get added up.

Hence:
step(n) = step(n-1) + step(n-2) // this gives Fibonacci sequence.

You can generalize it.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````// ZoomBA
\$count = 0
def count_stais( cur,path, max ){
if ( cur > max ) return
if ( cur == max ){
println( path ) ; \$count += 1
return
}
count_stais( cur + 1 , path + '->1' , max )
count_stais( cur + 2 , path + '->2' , max )
}
count_stais( 0 , '' , 4 )
println ( \$count )``````

You can look at the recursive code, and decide the same!

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.