## Amazon Interview Question Software Engineer in Tests

• -1
of 1 vote

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

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?

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

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.

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)$.

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

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

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

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

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

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>();
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)
{
}
}
}
if(previousPattern == null ||!previousPattern.getBrickLocations().contains(startingBrickLocation + 3))
{
List<Pattern> restPatterns2 = generateRow(startingBrickLocation + 3, previousPattern , rowSize);
if(restPatterns2 != null)
{
for(Pattern pattern:restPatterns2)
{
}
}
}

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();
return new Pattern(brickLocations);
}

}

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

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.

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:
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

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

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.

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

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.

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..

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### 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.