DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 383--------------------------------------------------
Microsoft Interview question-3
By: srini Date: December 10, 2012, 10:13 am
---------------------------------------------------------
Which program paradigm would you use to solve the following?
Please support your answer by solving it. ;D ;) :)
You are climbing a stair case. It takes 16 steps to reach to the
top.
Each time you can either climb 1 or 2 steps. In how many
distinct ways can you climb to the top?
#Post#: 384--------------------------------------------------
Re: Microsoft Interview question-3
By: kpr29 Date: December 10, 2012, 11:01 am
---------------------------------------------------------
@Srini: Dynamic Programming Paradigm............. Use recursion
and cache the result of the subproblems which will be used
later........
kp.
#Post#: 390--------------------------------------------------
Re: Microsoft Interview question-3
By: ravusairam Date: December 10, 2012, 10:04 pm
---------------------------------------------------------
Greedy appoach, I will take 2 steps every time so with in 8
units of time I will reach the top of the stair case
#Post#: 392--------------------------------------------------
Re: Microsoft Interview question-3
By: ravusairam Date: December 10, 2012, 10:22 pm
---------------------------------------------------------
Total number of ways will be 2^8,
becuase we can reach 16 steps with 8 - 2 steps and each 2 can be
replaced with two 1s.
So total 2^8 ways.
#Post#: 400--------------------------------------------------
Re: Microsoft Interview question-3
By: srini Date: December 10, 2012, 11:33 pm
---------------------------------------------------------
@ravu: good answer.
Solve for general case i.e it takes n steps to reach the top.(N
can be even or odd).
#Post#: 403--------------------------------------------------
Re: Microsoft Interview question-3
By: srini Date: December 10, 2012, 11:55 pm
---------------------------------------------------------
@All: sorry. Ravu's answer is incorrect.
For example n=4 case: Five cases are possible.
1111
121
112
211
22
But according to Ravu only 2^2=4 cases are possible.
Hint for solving general case: Fibonacci series
#Post#: 409--------------------------------------------------
Re: Microsoft Interview question-3
By: kpr29 Date: December 11, 2012, 3:04 am
---------------------------------------------------------
@Srini: If the hint is fibonnaci series, then by recursion for N
elements the time complexity is O(2^N). But if we solve using
dynamic programming paradigm it will be reduced to O(N).....
Just sharing the knowledge may be little out of context but
worth to know about it.......
kp.
*****************************************************