## Amazon Interview Question for Software Engineer in Tests

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

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

Can I get the code in C / C++ for this ? I need it urgently. Please help me. Thanks.
Vivek

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

Can I get the code for this in C / C++ asap? Thanks much in advance for your help.

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

Can I get the code in C / C++ for this ? I need it urgently. Please help me. Thanks.
Vivek

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.