CareerCup

If you Search google you will find this answer also ..
F(n) to reach n steps ..
then F(n) = F(n-1) + F(n -2) [ you can reach n only from n-1 and n -2 level ]
F(1) = 1;
F(2) = 2;
But permutation and combination answer is also correct !!

public int CountWays(int N)
{
    if(N<0) return 0;
    else if(N==0) return 1;
    else
    {
        return CountWays(N-1) + CountWays(N-2);
    }
}

Total =sum of[ (x + y)!/(x!* y!)] where y ranges from 0 to (N - N%2)/N and x = N - 2*y

y from 0 to (N - N%2)/2

I think it should use dynamic programming. Start from N = 2 (which has two ways), and then increase N (= 3, 4, 5 ...)

That's very similar to Fibonacci Sequence

Your answer (as elaborated by Mr X) is right.

The fibonacci series answer is also right.

In fact what we have is an identity connecting the binomial coefficients and fibonacci numbers!

The interviewer seems to be a moron (or perhaps how well you convince him was part of the test).

int Q=0;
int FindNumberofWays(int N)
{
    if(N==1) return Q+1;
    if(N==2) return Q+1;
    if(N==0) return 0;
    return FindNumberOfWays(Q-1) +  FindNumberOfWays(Q-2);
}

At each step, one can take either one step or two steps. A simple Dynamic programming approach can be used.
Below is the working C code for n==6:

#include<stdio.h>
#include<conio.h>

int main(int n)
{
    int temp;
    int hash[7]={0};
    hash[0]=hash[1]=1;
    temp=func(6,hash);
    printf("%d",temp);
    getch();
    return 1;
}

int func(int n,int hash[])
{
    if(hash[n]!=0)
    return hash[n];
    int ways;
    ways=0;
    ways+=func(n-2,hash);
    ways+=func(n-1,hash);
    hash[n]=ways;
    return hash[n];
}