Google Interview Question Software Engineer / Developers

  • google-interview-questions
    0
    of 0 votes
    13
    Answers

    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.

    - Softy on July 25, 2011 Report Duplicate | Flag
    Google Software Engineer / Developer Algorithm



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

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

}

- lucas.eustaquio on August 01, 2011 | Flag Reply
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).

- memo on July 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous on July 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- memo on July 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon on July 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I got anonymous's solution. Thanks.

- anon on July 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- iluvproblems on August 01, 2011 | Flag
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.

- anonymous on August 06, 2011 | Flag
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;
}

- wenlei.zhouwl on May 15, 2012 | Flag
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

- jack on July 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Zerg on July 26, 2011 | Flag
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));
}

}

- Softy on July 30, 2011 | Flag Reply
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

- Anonymous on August 28, 2011 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More