CareerCup

Can you please elaborate on this please "The goal is for the furthest of all lots to be as near as 1 possible to an office building. Determine the building placement to minimize the distance the 0 most distant lot is from an office building"

in the given question n(no.of cities) does not exceed 5 (when i was asked in my interview question) so you can simply use brute force technique by placing all cities in all the way possible if n is some higher number then you can use dyanmic programming.

public int shortestDistance(int[][] grid) {
int[][] distance = new int[grid.length][grid[0].length];
int[][] reach = new int[grid.length][grid[0].length];


int numBuilding = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
helper(grid, distance, reach, i, j);
numBuilding++;
}
}
}

int result = Integer.MAX_VALUE;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 0 && reach[i][j] == numBuilding) {
result = Math.min(result, distance[i][j]);
}
}
}

return result == Integer.MAX_VALUE ? -1 : result;
}

private void helper(int[][] grid, int[][] distance, int[][] reach, int i, int j) {

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

//two queue, one for direction, one for distance tracking
LinkedList<int[]> q = new LinkedList<>();
LinkedList<Integer> qDist = new LinkedList<>();

q.offer(new int[]{i, j});
qDist.offer(1);

while (!q.isEmpty()) {
int[] head = q.poll();
int dis = qDist.poll();

for (int k = 0; k < 4; k++) {
int x = head[0] + dx[k];
int y = head[1] + dy[k];

if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 0) {
grid[x][y] = -1;

q.offer(new int[]{x, y});
qDist.offer(dis + 1);

distance[x][y] += dis;
reach[x][y]++;
}
}
}

for (int m = 0; m < grid.length; m++) {
for (int n = 0; n < grid[0].length; n++) {
if (grid[m][n] == -1) {
grid[m][n] = 0;
}
}
}
}

You have to place n offices in such a way that for any non-office cell, it's nearest as possible. In short among all combinations of placing n offices, find min(max(office_distance_from_cells) of all combinations)