Amazon Interview Question for SDE1s


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;

	// already computed this value?
	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;
}

- Michael.J.Keating May 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In other words it's Fibonacci numbers.

- Anonymous May 21, 2014 | Flag
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

- Anonymous May 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good eye :)

- Michael.J.Keating May 22, 2014 | Flag
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.

- eugene.yarovoi May 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

F(2) = 2

- Anonymous May 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi May 21, 2014 | Flag
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)

- Miguel Oliveira May 20, 2014 | Flag Reply
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];
}

- vikas May 20, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More