Intel Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
package random;
public class Stair {
static int steps = 0;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args){
doSearch(0,sb);
}
public static void doSearch(int current, StringBuilder sb){
if (current == 5) {
System.out.println(sb);
return;
}
if (current + 1 <=5){
sb.append("1");
doSearch(current+1,sb);
sb.setLength(sb.length()-1);
}
if (current + 2 <=5){
sb.append("2");
doSearch(current+2,sb);
sb.setLength(sb.length()-1);
}
}
}
#include<map>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cctype>
#include<queue>
using namespace std;
int cnt=0,parr[6];
void dfs(int crs,int dep);
int main()
{
dfs(0,1);
cout<<cnt;
}
void dfs(int crs,int dep)
{
for(int i=1;i<=2;i++)
{
int ncrs=crs;
if(i==1){ncrs+=1;parr[dep]=i; }else {ncrs+=2;parr[dep]=i;}
if(ncrs==5)
{
cnt++;int sm=0;
for(int j=1;j<=5;j++)
{
sm+=parr[j];
if(sm<=5)
cout<<parr[j]<<" ";
else
cout<<"0 ";
}
cout<<endl;
return;
}
else if(ncrs>5)return;
else
{
dfs(ncrs,dep+1);
}
}
}
/*
Output :
1 1 1 1 1
1 1 1 2 0
1 1 2 1 0
1 2 1 1 0
1 2 2 0 0
2 1 1 1 0
2 1 2 0 0
2 2 1 0 0
8
*/
Plz check this line
else if(ncrs>;5)return;
semicolon got inserted automatically , remove it to run . :D
build up a tree, the root node is 5, the sub node is ether -1 or -2, which means how many steps you take, so the tree is like below. Totall 8 combinations.
5 - 4 - 3 - 2 - 1
- 0
- 1
- 2 - 1
- 0
- 3 - 2 - 1
- 0
- 1
From the tree, we can also see,
if there are 1 stairs, there is only 1 combination
2 stairs, there are 2 combinations
3 stairs = f(2) + f(1)
f(4) = f(3) + f(2)
...
if there is m stairs, you can take 1 - n steps
f(m) = f(m-1) + f(m-2) + ... + f(m-n)
public class Steps {
public static void main(String[] args) {
total("",5);
}
private static void total(String str,int steps){
if (steps == 0)
System.out.println(str);
if (steps >= 1)
total(1+" "+str,steps-1);
if (steps >= 2)
total(2+" "+str,steps-2);
}
}
1 1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
2 2 1
1 1 1 2
2 1 2
1 2 2
I have made an generic algorithm, that ask fot the number of stairs, and returns the number of ways to climb the stairs:
first, I assume that exist at least one way ti climb the stairs (only 1s), then, I add the number of permutations of '2s' in the secuence, starting with one 2, then 2 2s and so.
int n;
cout << "give me number of stairs:" << endl;
cin >> n;
int formas = 1;
int cantidad = n;
int i = 1;
int tmp;
while((cantidad - (2*i)) > 0)
{
tmp = cantidad - (2*i);
formas += (tmp + i)*i;
i++;
}
cout << "ways to climb the stairs:" << formas << endl;
This is the right solution, sorry:
cout << "give me number of stairs:" << endl;
cin >> n;
int formas = 1;
int cantidad1s = n;
int cantidad2s = 1;
int tmp;
while((n - (2*cantidad2s)) > 0)
{
cantidad1s = n - (2*cantidad2s);
formas += factorial(cantidad1s + cantidad2s)/
(factorial(cantidad1s)*factorial(cantidad2s));
cantidad2s++;
}
cout << "ways to climb to the stairs:" << formas << endl;
int stepCount(int stepRemaining) {
if( stepRemaining == 0 ) return 0;
if ( stepRemaining == -1 ) return -1;
return totalNumberOfStep = stepCount (stepRemaining -1 ) + StepCount (stepRemaining -2);
Its a Fibonacchi seq.. Can be solved by recursion in FIB.
- Neo March 05, 20131st step - 1 way to climb
2nd step - 2 ways
3rd step - 3 ways (Take one then take 2 steps or take 2 or take 1 step or take one step each. Hence total 3 ways)
4th step - will have 5 ways
and so on ...
If you look into it ... it will be a fib series.
Please post any suggestions
Thanks.