Adobe Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
does this work if, say, k == 4. alreadyTakenSteps will contain "2" and "3", which is incorrect
#include<stdio.h>
#include<conio.h>
void stair(int,int,int);
int pri[5];
int main()
{
int n = 4;
int k = 2;
stair(4,2,0);
return 0 ;
}
void stair(int n, int k,int c)
{
if(n==0)
{
int i = 0;
while(pri[i] != NULL)
{
printf("%d ",pri[i++]);
}
printf("\n");
return;
}
else
{
for(int i = 1; i<=k; i++)
{
if((n-i) >= 0)
{
pri[c++] = i;
stair(n-i,k,c);
pri[--c] = '\0';
}
}
}
}
public static void main(String[] args){
List<List<Integer>> ls = getCombinationOfStairs(4, 2);
for(List<Integer> lsFromSubStr : ls){
System.out.println("size " + lsFromSubStr.size());
for(int num : lsFromSubStr){
System.out.print(" " + num);
}
System.out.println("");
}
}
public static List<List<Integer>> getCombinationOfStairs(int numOfSteps , int k){
List<List<Integer>> ls = null;
if(numOfSteps == 0)
return ls;
ls = new ArrayList<List<Integer>>();
for(int i = 1; i <= k ; i++){
if(i <= numOfSteps){
int numOfStepsRemaining = numOfSteps - i;
List<List<Integer>> lst = getCombinationOfStairs(numOfStepsRemaining , k);
if(lst != null){
for(List<Integer> lsFromSubStr : lst){
lsFromSubStr.add(0, i);
ls.add(lsFromSubStr);
}
}else{
List<Integer> singleElemLst = new ArrayList<Integer>();
singleElemLst.add(i);
ls.add(singleElemLst);
}
}
}
return ls;
}
public class Algos {
private Map<Integer, List<List<Integer>>> _cache = new HashMap();
public List<List<Integer>> getSequence(int steps, int maxStep){
if(_cache.containsKey(steps))
return _cache.get(steps);
List<List<Integer>> list = new ArrayList();
if(maxStep > steps )
return list;
if(steps == 1 && maxStep <= steps){
if(_cache.containsKey(1))
return _cache.get(1);
list.add(Arrays.asList(1));
_cache.put(1, list);
return list;
}
if(steps == 0){
return list;
}
for(int firstStep = 1; firstStep <= maxStep; firstStep++){
List<List<Integer>> subList = getSequence(steps - firstStep, maxStep);
for(List<Integer> sequence : subList){
sequence.add(firstStep);
}
list.addAll(subList);
}
_cache.put(steps, list);
return list;
}
}
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
void steps(string sofar,int n,int k)
{
if(n==0)
cout<<sofar<<endl;
else
{
for(int i=1;i<=k;i++)
{
if(n>=i)
{
stringstream out;
out<<i;
steps(sofar+out.str(),n-i,k);
}
}
}
}
int main()
{
int n=4;
int k=2;
steps("",n,k);
}
#include <stdio.h>
#include<stdlib.h>
int stairsUtil(int *arr, int n, int k, int id)
{
int i =0;
if(0 == n)
{
for(i=0; i<id; i++)
printf("%d\t",arr[i]);
printf("\n");
}
for(i=1; i<=k; i++)
{
if(n-i>=0)
{
arr[id] = i;
stairsUtil(arr,n-i,k,id+1);
}
}
}
int stairs(int n, int k)
{
int *arr = (int*)malloc(n*sizeof(int));
stairsUtil(arr,n,k,0);
}
int main()
{
//printf("Hello, World!\n");
stairs(4,2);
return 0;
}
In Ruby:
# recursion requirement, this returns an array of array, which is
# array of all the possible steps to take, for n step staircase, and
# k step possible each time
def all_ways(n, k)
# this is tricky because it is 1 way if n = 0, which is "doing nothing"
# it is not 0 way, it is 1 way
return [[]] if n == 0
result = []
1.upto(k) do |n_steps|
if n >= n_steps
all_ways(n - n_steps, k).each do |possible_way|
result.push([n_steps] + possible_way)
end
end
end
return result
end
all_ways(4, 2).each {|i| puts i.join(", ")}
/* package whatever; // don't place package name! */
- Anonymous December 16, 2014package ds;
import java.util.*;
import java.lang.*;
import java.io.*;
class StairCase
{
static void steps(int n, String alreadyTakenSteps,int k) {
if (n == 0) {
System.out.println(alreadyTakenSteps);
alreadyTakenSteps=null;
}
for(int i=1;i<=k;i++){
if (n >= i) {
steps(n - i, alreadyTakenSteps.concat(""+i),k);
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
int n=4;
String s=new String();
steps(n,s,2);
}
}