## Google Interview Question Software Engineer / Developers

- 0of 0 votes
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.

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

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

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.

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

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

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

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

}

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));

}

}

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.

4. get the best result adding best result for n-1 to current cost.

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

- lucas.eustaquio on August 01, 2011 Edit | Flag Reply