Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
public class HousePainting {
public static void main(String[] args) {
getColouring(0, -1).colours.forEach(System.out::println);
}
private static int[][] costMatrix = {
{7, 5, 10},
{3, 6, 1},
{8, 7, 4},
{6, 2, 9},
{1, 4, 7},
{2, 3, 6}};
private static Colouring getColouring(int position, int previousColor) {
if (position == costMatrix.length) {
return new Colouring();
}
Colouring cheapestColouring = null;
int minCost = Integer.MAX_VALUE;
for (int colorIndex = 0; colorIndex < costMatrix[0].length; colorIndex++) {
if (colorIndex == previousColor) {
continue;
}
Colouring nextColouring = getColouring(position + 1, colorIndex);
int cost = costMatrix[position][colorIndex] + nextColouring.totalCost;
if (cost < minCost) {
nextColouring.colours.addFirst(colorIndex);
nextColouring.totalCost = cost;
cheapestColouring = nextColouring;
}
}
return cheapestColouring;
}
private static class Colouring {
LinkedList<Integer> colours = new LinkedList<>();
int totalCost = 0;
}
}
public class HousePainting {
public static void main(String[] args) {
getColouring(0, -1).colours.forEach(System.out::println);
}
private static int[][] costMatrix = {
{7, 5, 10},
{3, 6, 1},
{8, 7, 4},
{6, 2, 9},
{1, 4, 7},
{2, 3, 6}};
private static Colouring getColouring(int position, int previousColor) {
if (position == costMatrix.length) {
return new Colouring();
}
Colouring cheapestColouring = null;
int minCost = Integer.MAX_VALUE;
for (int colorIndex = 0; colorIndex < costMatrix[0].length; colorIndex++) {
if (colorIndex == previousColor) {
continue;
}
Colouring nextColouring = getColouring(position + 1, colorIndex);
int cost = costMatrix[position][colorIndex] + nextColouring.totalCost;
if (cost < minCost) {
nextColouring.colours.addFirst(colorIndex);
nextColouring.totalCost = cost;
cheapestColouring = nextColouring;
}
}
return cheapestColouring;
}
private static class Colouring {
LinkedList<Integer> colours = new LinkedList<>();
int totalCost = 0;
}
}
public class HousePainting {
public static void main(String[] args) {
getColouring(0, -1).colours.forEach(System.out::println);
}
private static int[][] costMatrix = {
{7, 5, 10},
{3, 6, 1},
{8, 7, 4},
{6, 2, 9},
{1, 4, 7},
{2, 3, 6}};
private static Colouring getColouring(int position, int previousColor) {
if (position == costMatrix.length) {
return new Colouring();
}
Colouring cheapestColouring = null;
int minCost = Integer.MAX_VALUE;
for (int colorIndex = 0; colorIndex < costMatrix[0].length; colorIndex++) {
if (colorIndex == previousColor) {
continue;
}
Colouring nextColouring = getColouring(position + 1, colorIndex);
int cost = costMatrix[position][colorIndex] + nextColouring.totalCost;
if (cost < minCost) {
nextColouring.colours.addFirst(colorIndex);
nextColouring.totalCost = cost;
cheapestColouring = nextColouring;
}
}
return cheapestColouring;
}
private static class Colouring {
LinkedList<Integer> colours = new LinkedList<>();
int totalCost = 0;
}
}
public class HousePainting {
public static void main(String[] args) {
getColouring(0, -1).colours.forEach(System.out::println);
}
private static int[][] costMatrix = {
{7, 5, 10},
{3, 6, 1},
{8, 7, 4},
{6, 2, 9},
{1, 4, 7},
{2, 3, 6}};
private static Colouring getColouring(int position, int previousColor) {
if (position == costMatrix.length) {
return new Colouring();
}
Colouring cheapestColouring = null;
int minCost = Integer.MAX_VALUE;
for (int colorIndex = 0; colorIndex < costMatrix[0].length; colorIndex++) {
if (colorIndex == previousColor) {
continue;
}
Colouring nextColouring = getColouring(position + 1, colorIndex);
int cost = costMatrix[position][colorIndex] + nextColouring.totalCost;
if (cost < minCost) {
nextColouring.colours.addFirst(colorIndex);
nextColouring.totalCost = cost;
cheapestColouring = nextColouring;
}
}
return cheapestColouring;
}
private static class Colouring {
LinkedList<Integer> colours = new LinkedList<>();
int totalCost = 0;
}
}
```public class HousePainting {
public static void main(String[] args) {
getColouring(0, -1).colours.forEach(System.out::println);
}
private static int[][] costMatrix = {
{7, 5, 10},
{3, 6, 1},
{8, 7, 4},
{6, 2, 9},
{1, 4, 7},
{2, 3, 6}};
private static Colouring getColouring(int position, int previousColor) {
if (position == costMatrix.length) {
return new Colouring();
}
Colouring cheapestColouring = null;
int minCost = Integer.MAX_VALUE;
for (int colorIndex = 0; colorIndex < costMatrix[0].length; colorIndex++) {
if (colorIndex == previousColor) {
continue;
}
Colouring nextColouring = getColouring(position + 1, colorIndex);
int cost = costMatrix[position][colorIndex] + nextColouring.totalCost;
if (cost < minCost) {
nextColouring.colours.addFirst(colorIndex);
nextColouring.totalCost = cost;
cheapestColouring = nextColouring;
}
}
return cheapestColouring;
}
private static class Colouring {
LinkedList<Integer> colours = new LinkedList<>();
int totalCost = 0;
}
}```
public class HousePainting {
public static void main(String[] args) {
getColouring(0, -1).colours.forEach(System.out::println);
}
private static int[][] costMatrix = {
{7, 5, 10},
{3, 6, 1},
{8, 7, 4},
{6, 2, 9},
{1, 4, 7},
{2, 3, 6}};
private static Colouring getColouring(int position, int previousColor) {
if (position == costMatrix.length) {
return new Colouring();
}
Colouring cheapestColouring = null;
int minCost = Integer.MAX_VALUE;
for (int colorIndex = 0; colorIndex < costMatrix[0].length; colorIndex++) {
if (colorIndex == previousColor) {
continue;
}
Colouring nextColouring = getColouring(position + 1, colorIndex);
int cost = costMatrix[position][colorIndex] + nextColouring.totalCost;
if (cost < minCost) {
nextColouring.colours.addFirst(colorIndex);
nextColouring.totalCost = cost;
cheapestColouring = nextColouring;
}
}
return cheapestColouring;
}
private static class Colouring {
LinkedList<Integer> colours = new LinkedList<>();
int totalCost = 0;
}
}
- akii May 27, 2015