## Amazon Interview Question for Software Developers

Country: United States

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

edited: changed recursion as Fernandoz pointed out
Analysis:
--

the cost of a single column depends on which color is on which row.
Which color can be painted on which row depends on the previous
column. No greedy choice is possible if optimal solution is wanted.

Solution (assuming no negative cost)
--
a) brute force, trying all potential combinations which are
roughly 3!^n = 6^n

b) look at all potential combinations per columns as adjacent nodes
from all the reachable combinations of the previous column. Thus build
a graph and find the shortest path. This can be done using Dijkstra's
shortest path algorithm. That's a bit a heavy tool for this problem.

There is a better alternative because in the DAC there are only edges from
Nodes in Column i to Column i + 1.

Every column can have 6 potential house-color combinations RGB, RBG, BGR, ...)
potentially each of those combinations can be reached by various paths, but
we are only interested in the cheapest path to a given combination. So, we
could just calculate the cost to go from each combination in column i to
each allowed combination in column i+1 and if multiple ways are allowed, we
pick the cheapest.

as recursion:

``````DP(col, comb) = Min(DP(col-1, prev_comb) + cost(comb))
for each prev_comb that leads to comb,
cost(comb) is the cost for the combination comb
if col = 0: DP(col, comb) = 0

The minimal cost then is: Min(DP(N, last_comb)) for each of the 6 color combinations``````

complete solution (iterative DP solution), time complexity O(n*8*8*3*6) = O(n), space: O(n)

``````public class PaintHouses {
static final String[] COLOR_COMBINATION_STR = new String[]{"RGB", "RBG", "GBR", "GRB", "BGR", "BRG" };

static public void printMinPaint(int n) {
int[][] cost = new int[n][COLOR_COMBINATION_STR.length]; // can optimize 1st dimension to 2
int[][] backTrack = new int[n][COLOR_COMBINATION_STR.length]; // previous combination

// initialize
for (int j = 0; j < COLOR_COMBINATION_STR.length; j++) {
cost[0][j] = getCost(0, j);
}
for(int i = 1; i < n; i++) {
for (int j = 0; j < COLOR_COMBINATION_STR.length; j++) {
cost[i][j] = Integer.MAX_VALUE;
}
}

// calculate cheapest cost
int min = 0; // keeps the cheapest last color combination
for(int i = 1; i < n; i++) {
int minCost = Integer.MAX_VALUE;
for(int l = 0; l < COLOR_COMBINATION_STR.length; l++) { // O(n*9)
for(int r = 0; r < COLOR_COMBINATION_STR.length; r++) { // O(n*9*9)
if(cost[i-1][l] < Integer.MAX_VALUE && isValidAdjacent(l, r)) {
int rc = cost[i-1][l] + getCost(i, r);
if(cost[i][r] > rc) {
cost[i][r] = rc;
backTrack[i][r] = l;
if(rc < minCost) {
min = r;
minCost = rc;
}
}
}
}
}
}

// backtrack to print (... print in reverse order, that's the same cost result)
for(int i = n-1; i >= 0; i--) {
System.out.println("Column: " + (n - i) + " Colors: " + COLOR_COMBINATION_STR[min]);
min = backTrack[i][min];
}
System.out.println("---");
}

// some arbitrary cost function to produce a "random" cost per column for
// a certain combination of house colors for the three rows
private static int getCost(int column, int rowColorCombination) {
return ((rowColorCombination * 17) * (column * 31)) % 11;
}

// can next column have this colors per row
// e.g. if left=0 and right=1:
// left   right
// R      R
// G      B
// B      G
// result false, because R   and R in the first row
static private boolean isValidAdjacent(int left, int right) {
for(int i = 0; i < 3; i++)
if(COLOR_COMBINATION_STR[left].charAt(i) == COLOR_COMBINATION_STR[right].charAt(i))
return false;
return true;
}

static public void main(String[] args) {
printMinPaint(2);
printMinPaint(6);
printMinPaint(12);
}

}``````

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

In general for this kind of problems I prefer to use the tabling method as it solves you all the pain of unrolling the recursion which is specially useful on an interview. You have to check that DP is going to be effective so you have to check that there are multiple repeated calls and the solution is monotonous.
Here is a possible implementation in python

``````# cost(n, color) is supposed to be the function with the
# cost for a given row and colors
from itertools import permutations

def compute_houses_cost(n, colors):
tabling = dict()
# Initialize the first column.
# This saves the base case on the
# recursive function
for p in permutations(colors):
tabling[(0, p)] = cost(0, p)
def _aux(n, colors):
if (n, colors) in tabling:
return tabling[(n, colors)]
res = []
for p in permutations(colors):
# Don't recurse using the same colors
if p == colors:
continue
res.append(_aux(n-1, p))
tabling[(n, colors)] = min(res) + cost(n, colors)
return tabling[(n, colors)]
return _aux(n, colors)``````

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

If I am right then the cost will be same for fixed 3 row of houses, 3 combinations of paint and variable number of columns(houses) N. The program below shows the answer.
Order of complexity O(n*m).

I'm open to suggestions, improvement and learning. :)

``````public static List<List<string>> InitRows(int row, int columns)
{
List<List<string>> rowOfHouses = new List<List<string>>();
for (int i = 0; i < row; i++)
rowOfHouses.Insert(i, InitHouses(i, columns));

return rowOfHouses;
}

// Create Columns of Houses
public static List<string> InitHouses(int row, int n)
{
List<string> houses = new List<string>();

for (int j = 0; j < n; j++)
houses.Add(("H="+ row + "-" + j).ToString());

return houses;
}

public static List<List<string>> PaintHouses(int rows, int columns, List<List<string>> rowOfHouses)
{
string[] color = { "R", "G", "B" };
int colorSelector = 0;
int[] colorCount = new int[color.Length];

for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
rowOfHouses[i][j] = (rowOfHouses[i][j] + ":" + color[colorSelector]);

colorCount[colorSelector] = colorCount[colorSelector]+1;

if (colorSelector < 2)
colorSelector++;
else
colorSelector = 0;
}
colorSelector++;
if (colorSelector >= color.Length)
colorSelector = 0;
}
Console.WriteLine("-------------------------------------------------------------");
Console.WriteLine("-------------------------------------------------------------");
Console.WriteLine("Red: " + colorCount[0]);
Console.WriteLine("Green: " + colorCount[1]);
Console.WriteLine("Blue: " + colorCount[2]);
return rowOfHouses;
}

public static void Print(List<List<string>> list)
{
Console.WriteLine("H=[Row]-[Column]:[Color]");
for(int i = 0; i < list.Count; i++)
{
for(int j = 0; j < list[i].Count; j++)
Console.Write(list[i][j] + " ");
Console.Write("\n");
}
}

static void Main(string[] args)
{
// Number of Row of Houses
int rows = 3;
// Number of Columns = N
int columns = 6;

List<List<string>> rowOfHouses = InitRows(rows, columns);

// Print Initial Houses
Print(rowOfHouses);

// Paint Houses
rowOfHouses = PaintHouses(rows, columns, rowOfHouses);

Console.WriteLine("-------------------------------------------------------------");
Print(rowOfHouses);
}``````

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

Approach:
Dynamic Programming solution:
we can paint the ith house with blue, red or green.
so we have the following equations:
cost[i,r] = min( cost[i-1,b], cost[i-1,g] ) + cost of painting i with r.
cost[i,g] = min( cost[i-1,b], cost[i-1,r] ) + cost of painting i with g.
cost[i,b] = min( cost[i-1,r], cost[i-1,g] ) + cost of painting i with b.

Final Min Cost = min (cost[n,b], cost[n,r], cost[n,g]);

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

@ChrisK Good answer just one small detail it is weird to see the recursion not starting from the last element as it doesn't make much sense that the first column is more expensive than the last one.

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

``````public static void main(String[] args) {

int row = 3;
int column = 10;
String color[] = {"Red","Green","Blue"};
String newColor[]=new String[3];

Map<String, Integer> colorCostMap = new HashMap<>();
colorCostMap.put("Red",5);
colorCostMap.put("Green", 10);
colorCostMap.put("Blue", 8);

Map<String, Integer> rowWiseCostMap = new HashMap<>();

int val[] = {2,0,1};

for(int i=0; i<=column; i++){
if(i==0){
for(int j=0; j<row; j++){
System.out.print(color[j]+" - ");
}
}else{
for(int j=0; j<row; j++){
newColor[j] = color[val[j]];
System.out.print(newColor[j]+" - ");
if(rowWiseCostMap.get("Row-"+j)==null){
rowWiseCostMap.put("Row-"+j, colorCostMap.get(newColor[j]));
}else{
rowWiseCostMap.put("Row-"+j, rowWiseCostMap.get("Row-"+j)+colorCostMap.get(newColor[j]));
}
}
for(int k=0; k<color.length; k++){
color[k] = newColor[k];
}
}
System.out.println();
}
for(Map.Entry<String, Integer> mapEntry: rowWiseCostMap.entrySet()){
System.out.println(mapEntry.getKey() + " cost is : "+mapEntry.getValue());
}
}``````

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.