## Amazon Interview Question for SDE1s

• 2

Country: India

Comment hidden because of low score. Click to expand.
5
of 5 vote

Turns out to be a fibonacci pattern. Consider:

``````width    possibilities  (1 = vertical, 0 = horizontal and must be in pairs)
1         1 - 1
2         2 - 11/00
3         3 - 111/100/001
4         5 - 1111/1100/1001/0011/0000
5         8 - 11111/11100/11001/10011
10000/00111/00001/00000``````

This simple logic

``````public static int countWays(int n) {
if (n < 1)
return 0;
if (n == 1)
return 1;
else if (n == 2)
return 2;
else
return countWays(n - 1) + countWays(n - 2);
}``````

To add DP to this (caching):

``````static int[] cache = new int[w + 1];
static int countWays(int w) {
if (w == 1)
return 1;
if (w == 2)
return 2;

if (cache[w] != 0)
return cache[w];

// compute and cache
cache[w] = countWays(w - 1) + countWays(w - 2);

return cache[w];
}``````

Or, you could just do it iteratively:

``````static int countWays(w) {
if (w == 1)
return;
if (w == 2)
return;

int last = 2;
int lastlast = 1;

int ways = 0;
for (int i = 3; i <= w; i++) {
ways = lastlast + last;
lastlast = last;
last = ways;
}

return ways;
}``````

Comment hidden because of low score. Click to expand.
0

In other words it's Fibonacci numbers.

Comment hidden because of low score. Click to expand.
1
of 1 vote

also should be:
5 8 - 11111/11100/11001/10011
10000/00111/00001/00100 - not 00000

Comment hidden because of low score. Click to expand.
0

Good eye :)

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

F(2) = 2

Comment hidden because of low score. Click to expand.
0

@Anon: Oops. Edited. Also clarified the logic.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic programming. Suppose you process the floor column by column. You either put a tile vertically (filling 2 rows and 1 column) or 2 tiles horizontally (filling 2 columns and 2 rows)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.