Amazon Interview Question
SDE1sCountry: India
This turns out to simply be the Fibonacci sequence. Consider in what ways you can cover the top left corner. If you lay down a tile horizontally, you reduce the problem to 2 x (W-1), and if you lay down a tile vertically, you have no choice but to lay down another tile vertically right next to it (top right corner), leaving you with a space of 2 x (W-2) to fill when you're done. All the tilings you get with the first choice are different from all the tilings you get from the second choice, so the total number of tilings is the number of ways to tile a 2 x (W-1) board plus the number of ways to tile a 2 x (W-2) board. Thus, letting F(W) be the number of tilings for a 2 x W board, F(W) = F(W-1) + F(W-2) subject to F(1) = 1 and F(2) = 2 (if you want, you can define F(0) = 1). This is just the Fibonacci sequence and may be computed in any manner in which you normally compute Fibonacci numbers -- with recursion & DP, iteratively, or using the efficient matrix-squaring approach.
This problem is simple application for DP. See
{
solutions[W] ; // contains the number of ways to cover the tile for W columns
Solutions[0] = 1 if W==1
Solutions[1] = 2 if W == 2
By analysis, you can see that , any odd W can be covered by
Solutions[W] = Solutions[W-1] + 1
any even W, Solutions is just the sum of
Solutions[W] = Solutions[W-2] + 2
So final code is
Int64 GetNumberOfWaysToCover(int floor[2][W])
{
int sol[w] = {0};
sol[0]=1; sol[1] = 2;
if( w==0) return 1; if (w==1) return 2;
for(int i=2;i<w;i++)
{
if(i&1) sol[i] = sol[i-1]+1;
else sol[i] = sol[i-2] +2;
}
return sol[w-1];
}
Turns out to be a fibonacci pattern. Consider:
This simple logic
To add DP to this (caching):
Or, you could just do it iteratively:
- Michael.J.Keating May 20, 2014