Amazon Interview Question Software Engineer in Tests

  • amazon-interview-questions
    -1
    of 1 vote
    12
    Answers

    Consider the problem of building a wall out of 2×1 and 3×1 bricks (horizontal×vertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form an internal "running crack". For example, the following 9×3 wall is not acceptable due to the internal running crack shown as a dotted line:





    There are eight ways of forming a crack-free 9×3 wall, written W(9,3) = 8. Write a program to calculate W(32,10). To get you started, here are a few smaller values:

    W(9, 3) = 8

    W(18, 5) = 7958

    - Anonymous on January 11, 2009 Report Duplicate | Flag
    Amazon Software Engineer in Test Brain Teasers



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

can you give an example of how an crack-free wall may lay out?

- Anonymous on January 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes. Please give us more details on this one. The problem isnt clear.

Also, I would like to know if you were asked this question during your phone interview or the onsite interview.

- Anonymous on January 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First, for one layer, use recursion to computer the number of possible combinations. f(m) = f(m-3)+f(m-2), f(3)=1, f(2)=1, f(1)=0, f(0)=0. Second, obtain a conflict matrix, where an item is 1 is patten i is conflict with pattern j (by looking at their cumulative sum (a sorted array), then finding the identical value in two sorted arrays (similar to merge operation)). Next, considering the other dimension, we have to record the maximum ways to lay bricks in n-1 layer for each possible patten on layer n-1 (or g(n-1, i), i \in [f(m)]). Finally, use dynamic programming to compute $g(n,i) = \sum_{k:k,i \textrm{ is compatible }} g(n-1, k), g(n) = \sum_i g(n,i)$.

- canger on February 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have implemented your strategy (see below). Works good.

- Bullocks on January 01, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution canger. But those Latex commands might look strange to people unfamiliar with Latex.

- rrs on January 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi canger
will be elaboratng your above explanation. Actually I did not get or post some link where We could get detail explanation about it.
The first for finding the number of ways in which one layer brick can be formed is undersatnble ..but for remaining part ..please elaborate it

- rajeev on March 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Bricks {

	public static int getPatterns(int rowNumber, int rowSize)
	{
		return generateCount(1, rowNumber, rowSize, null);
	}
	
	private static int generateCount(int rowNumber, int rowMax, int rowSize, Pattern previousRow)
	{
		if(rowNumber == rowMax)
		{
			List<Pattern> rowPatterns = generateRow(0, previousRow, rowSize);
			return rowPatterns.size();
		}else
		{
			int result = 0;
			List<Pattern> rowPatterns = generateRow(0, previousRow, rowSize);
			for(Pattern pattern:rowPatterns)
			{
				result += generateCount(rowNumber + 1, rowMax, rowSize, pattern);
			}
			return result;
		}
	}
	private static List<Pattern> generateRow(int startingBrickLocation, Pattern previousPattern, int rowSize)
	{
		if(startingBrickLocation + 2 > rowSize)
		{
			return null;
		}else
		{
			List<Pattern> returnList = new ArrayList<Pattern>();
			if((startingBrickLocation + 2) == rowSize || (startingBrickLocation + 3) == rowSize)
			{
				Set<Integer> brickSet = new HashSet<Integer>();
				brickSet.add(rowSize);
				returnList.add(new Pattern(brickSet));
				return returnList; 
			}else
			{
				if(previousPattern == null || !previousPattern.getBrickLocations().contains(startingBrickLocation + 2))
				{
					List<Pattern> restPatterns1 = generateRow(startingBrickLocation + 2, previousPattern , rowSize);
					if(restPatterns1 != null)
					{
						for(Pattern pattern:restPatterns1)
						{
							returnList.add(Pattern.prepend(pattern, startingBrickLocation + 2));
						}
					}
				}
				if(previousPattern == null ||!previousPattern.getBrickLocations().contains(startingBrickLocation + 3))
				{
					List<Pattern> restPatterns2 = generateRow(startingBrickLocation + 3, previousPattern , rowSize);
					if(restPatterns2 != null)
					{
						for(Pattern pattern:restPatterns2)
						{
							returnList.add(Pattern.prepend(pattern, startingBrickLocation + 3));
						}
					}
				}
				
				
				return returnList;
			}
		}
		
	}
}

class Pattern
{
	// this data structure records the end location of each brick in this pattern.
	Set<Integer> brickLocations;
	

	
	public Pattern(Set<Integer> brickLocations)
	{
		this.brickLocations = brickLocations;
	}
	

	public Set<Integer> getBrickLocations() {
		return brickLocations;
	}

	public void setBrickLocations(Set<Integer> brickLocations) {
		this.brickLocations = brickLocations;
	}
	
	
	public static Pattern prepend(Pattern pattern, int brickLocation)
	{
		Set<Integer>brickLocations = pattern.getBrickLocations();
		brickLocations.add(brickLocation);
		return new Pattern(brickLocations);
	}
	

}

- maverick on April 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey, while it is great that someone actually takes the pain to write out code and give it to others, it might be still better if you could give a short description of what your code does before the starting of the code. This might help the reader more than reading the entire program and deciphering what it does.

- ramman on July 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The strategy used here is same as what Canger outlined. Python code follows:

def brickwall(w,h):
    # generate single brick layer of width w (by recursion)
    def gen_layers(w):
        if w in (0,1,2,3):
            return {0:[], 1:[], 2:[[2]], 3:[[3]]}[w]
        return [(layer + [2]) for layer in gen_layers(w-2)] + \
               [(layer + [3]) for layer in gen_layers(w-3)]
    # precompute info about whether pairs of layers are compatible
    def gen_conflict_mat(layers, nlayers, w):
        # precompute internal brick positions for easy comparison
        def get_internal_positions(layer, w):
            acc = 0; intpos = set()
            for brick in layer:
                acc += brick; intpos.add(acc)
            intpos.remove(w)
            return intpos
        intpos = [get_internal_positions(layer, w) for layer in layers]        
        mat = []
        for i in range(nlayers):
            mat.append([j for j in range(nlayers) \
                              if intpos[i].isdisjoint(intpos[j])])
        return mat
    layers = gen_layers(w)
    nlayers = len(layers)
    mat = gen_conflict_mat(layers, nlayers, w)
    # dynamic programming to recursively compute wall counts
    nwalls = nlayers*[1]
    for i in range(1,h):
        nwalls = [sum(nwalls[k] for k in mat[j]) for j in range(nlayers)]
    return sum(nwalls)

print(brickwall(9,3))   #8
print(brickwall(18,5))  #7958
print(brickwall(32,10)) #806844323190414

- Bullocks on January 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for your Python code but most people here are comfortable with C++ and Java. Also, I think Python is not a preferred language in interviews.

- rrs on January 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hello, when I run this code, it keeps telling me that

"'set' object has no attribute 'isdisjoint'"

what does this mean? obviously you have ran it fine. I am just using a python filename.py command.

- james on September 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

Can you please elaborate on the logic.. i'm using perl to find a solution.. This is what i've done so far..

input : W(x,y)
find all possible i's and j's such that x == 3(i) + 2(j);
for each pair (i,j) ,
find n = (i+j)C(j)

Adding all these n's should give the count of all possible combinations . But i have no idea on how to find the real combinations for one row and how to proceed further.. Please help..

- Sahithya on June 20, 2010 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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