## Google Interview Question Software Engineer / Developers

• 0

There are a row of houses, each house can be painted with three colors red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?

Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.

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

Solution using dynamic programing.
The solution is as folows (calc(int, int) function):
1. If a best solution was found, use it.
2. Select one color not forbiden;
3. Solve the problem for n-1 houses.
5. see if it is the current minimum when you add current color cost
6. update minimum if needed.
7. save best result.

Time complexity: Colors*Houses.
Space complexity: Colors*Houses.
Is easy to see it, if you realize that the runtime cost is the time to fill the best solution matrix, sized Colors*Houses.
By the way, for the problem stated above, the solution is:
Colors: [1, 0, 2, 1, 0, 1] (G, R, B, G, R, G)
Cost: 18

``````public class PaintHouse {
public class BestResult {
public int[] colors;
public int cost;
public BestResult(int[] colors, int cost) {
this.colors = colors;
this.cost = cost;
}

}
private int[][] cost;
private BestResult[][] best;
public PaintHouse(int[][] cost) {
this.cost = cost;
this.best = new BestResult[cost.length][cost[0].length];
}
public BestResult calc() {
return calc(cost[0].length, -1);
}
private BestResult calc(int n, int forbiden) {
if (forbiden >= 0 && best[forbiden][n-1] != null)
return best[forbiden][n-1];
BestResult min = null;
for (int c = 0, h = cost[0].length - n; c< cost.length; ++c) {
if (c != forbiden) {
if (n == 1) {
if (min == null || min.cost > cost[c][h]) {
min = new BestResult(new int[] {c}, cost[c][h]);
}
} else {
BestResult next = calc(n-1, c);
if (min == null
|| min.cost > (next.cost + cost[c][h])) {
min = new BestResult(new int[next.colors.length+1],
next.cost + cost[c][h]);
min.colors[0] = c;
System.arraycopy(next.colors, 0,
min.colors, 1, next.colors.length);
}
}
}
}
if (forbiden >= 0)
best[forbiden][n-1] = min;
return min;
}

}
public class PaintHouseTest {
@Test
public void testCalc() {
int[][] cost = new int[][] {
new int[] { 7, 3, 8, 6, 1, 2},
new int[] { 5, 6, 7, 2, 4, 3},
new int[] {10, 1, 4, 9, 7, 6}
};
PaintHouse calc = new PaintHouse(cost);
BestResult bestResult = calc.calc();
System.out.println("Colors: " + Arrays.toString(bestResult.colors));
System.out.println("Cost: " + bestResult.cost);
assertEquals(bestResult.cost, 18);
}

}``````

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

If T(i) is the min up to the ith place, and T(i,j) is the min up to ith place with ith spot having the color j, then:

T(i)=min(T(i-1,B)+min(Gi,Ri), T(i-1,R)+min(Gi,Bi), T(i-1,G)+min(Bi,Ri))

which naively would result in exponential growth, but if you cache the results in an array, I believe it should be O(n).

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

u hv to maintain 3 minimums
cost(i,b)=min(cost(i-1,g),cost(i-1,r))+cost of painting i as b;
cost(i,g)=min(cost(i-1,b),cost(i-1,r))+cost of painting i as g;
cost(i,r)=min(cost(i-1,g),cost(i-1,b))+cost of painting i as r;

finally min(cost(N,b),cost(N,g),cost(N,r)) is the ans

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

Yea, an extremely vague and intuitive thought process said arrays, but when I thought about it driving this morning, I could see that just keeping three values would be enough. The two recursive formulations are equivalent though.

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

I doubt if it can be solved using DP. A challenge for you. Show how it works here?
N = 6 (houses)
cost matrix:

``````1     2      3      4       5       6
----------------------------------------
R   7      3      8      6       1       2

G   5      6      7      2       4       3

B   10     1      4      9       7       6``````

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

I got anonymous's solution. Thanks.

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

A greedy solution:

Let Cost(house h, color c) be the cost of coloring house with color c.
Compute Cost(h,c) for each house and color and sort the costs in ascending order in an array. Now traverse the array from low to high cost. Accept the house color only if
1. The house color is not yet selected.
2. The adjacent house does not have the same color.

In the example above the least cost solution = 20 with the following pattern,

1 2 3 4 5 6
G B R G R G

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Greedy fails. Optimal cost is 18. Before write up something, check your correctness atleast.

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

#include <iostream>
#include <cstdio>
#include <cassert>
using namespace std;

int v[1000][3];
int dp[1000][3];

int min(int a, int b)
{
if (a <= b)
{
return a;
}
return b;
}

int min(int a, int b, int c)
{
return min(min(a, b), c);
}

void printPath(int n)
{
int c = 0;
if (dp[n][1] < dp[n][c])
{
c = 1;
}
if (dp[n][2] < dp[n][c])
{
c = 2;
}
char buff[20];
sprintf(buff, "%d", c);
string result = string(buff);
for (int i = n - 1; i > 0; --i)
{
if (dp[i][(c + 1) % 3] <= dp[i][(c + 2) % 3])
{
c = (c + 1) % 3;
sprintf(buff, "%d", c);
result = string(buff) + " " + result;
}
else
{
c = (c + 2) % 3;
sprintf(buff, "%d", c);
result = string(buff) + " " + result;
}
}
cout << result << endl;
}

int paint(int n)
{
assert(n > 0);
dp[1][0] = v[1][0];
dp[1][1] = v[1][1];
dp[1][2] = v[1][2];
for (int i = 2; i <= n; ++i)
{
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i][1];
dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + v[i][2];
}
int result = min(dp[n][0], dp[n][1], dp[n][2]);
printPath(n);
return result;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> v[i][0];
}
for (int i = 1; i <= n; ++i)
{
cin >> v[i][1];
}
for (int i = 1; i <= n; ++i)
{
cin >> v[i][2];
}
int result = paint(n);
cout << result << endl;
return 0;
}

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

dp,
dp[i][j] = minimum cost of painting 0,1,....,i using color j

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

This is not DP, because in DP optimal solving of problem means that all subproblems are also solved optimally. This is not the case here because we have additional limitation that two nearby houses cannot be painted by same color.
I think it is NP-complete problem.

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

class Paint
{
int[] Red = { 7, 3, 8 , 6, 1, 2 };
int[] Green = { 9, 6, 7, 2, 4, 3 };
int[] Blue = { 2, 1, 4, 9, 7, 6 };

public Paint()
{
int minR = MinRed(Red.Length - 1);
int minG = MinGreen(Green.Length - 1);
int minB = MinBlue(Blue.Length - 1);

int minimum = Min(minR, Min(minB, minG));

}

int Min(int a, int b)
{
return a < b ? a : b;
}

int MinRed(int N)
{
if (N < 0)
return 0;
else
return Red[N] + Min(MinGreen(N - 1), MinBlue(N - 1));
}

int MinGreen(int N)
{
if (N < 0)
return 0;
else
return Green[N] + Min(MinRed(N - 1), MinBlue(N - 1));
}

int MinBlue(int N)
{
if (N < 0)
return 0;
else
return Blue[N] + Min(MinGreen(N - 1), MinRed(N - 1));
}

}

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

@lucas can u explain ur solution little bit more by taking values say for 3 houses

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.

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