Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
no, it seems to me that it is not fibonacci problem, it is a simple probability problem
for eg, for 3 = 3, using ur fiboinacci formula, it is giving answer as 3, but there are only 2 ways we can put tiles on a 2 * 3 floor.
the answer is (W/2) * 2 ways in total.
Please correct if my understanding of the question is wrong.
It's a dynamic programming question. And the solution format is just like the fabocci sequence. For example, if w = 1, then the answer is 1, if w = 2, the answer is 2, if w = 3, the answer is 1 + 2 = 3, if w = 4, the answer is 2 + 3 = 5. And the dynamic equation is
dp[n] = dp[n - 1] + dp[n - 2]. Here is the code:
- ravio June 07, 2014