Amazon Interview Question
Software DevelopersCountry: United States
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)
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);
}
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]);
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());
}
}
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:
complete solution (iterative DP solution), time complexity O(n*8*8*3*6) = O(n), space: O(n)
- Chris May 16, 2017