Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
I assume the question is, where do I need to place the boss, so that it minimizes the total distance he has to walk if he walks to each office space once.
Or, more formal, find the field that minimizes the sum of the shortest path from this field to each office space.
First approach is to run a BFS simulatenously (increment distance one by one) from each office space. The field that is first visited by all BFSs is the place for the boss.
This is inefficient but guarantees the best solution. More efficient solutions are thinkable, such as using heuristics to cover only parts of the map (like in A*). Another approach might be to run A* towards the center of gravity of all office spaces, assuming that there are no closed-off areas (like a rectangles surounded by walls). Maybe one can even change the A* behavior by adapting the center of gravity based on the progress of the simultaneously running A*'s etc.
A similar but less difficult question was:
[https][://][www]careercup.com/question?id=5084886537863168
which gives an idea about A*.
How ever, in an interview I'd probably go for save grounds and use BFS from multiple origins.
@ChrisK, Hey hello Chris!! Hope you are doing well. Thanks for your comment. Perhaps I should have used the term a Dijkstra's algorithm variation. I know the code is a little bit convoluted and it doesn't look like it but I am using a priority queue on the code. By the way the elements are added to the queue the ones with a shortest distance are always first, the algorithm is uniform-cost search if anybody is interested into digging in the details.
ChrisK, what i have understood from your explanation is...
Let us say a graph have n nodes.... where each node has a propery called visitedcount.
let the number of office spaces be 3.
so 3 origins am adding to queue with 3 visitedsets.
in Bfs function, whenever a node is visited from one of the origin as a source, its node.visitedcount is increased by 1. if it is equal to 3-meaning if it is the first node visited by all the 3 origins, then we return this node as our answer. am i correct Chrisk?
@sxs155933: this is correct, although you need a measure to find out for each origin if you already visited that field. So, count is good to find out if completed, but you will still need a "visited"-flag per origin...
something like this, hope I didn't type to many bugs in, but it should definitely transport the idea... on a generic graph, one need to adapt to the matrix thing
from collections import deque
def find_center(adjacents, origins):
# adjacents being a dictionary of list {0: [1,2,3], 4: [1, 3], 5: [1]} for a directed graph
# origins a list of verices [0, 2]
queue = deque([(o,o,0) for o in origins]) #(original origin, current node, distance)
visited = {} # dictionary of dictionary, vertex as 1st key, origin as 2nd key, distance as value
while queue:
origin, current, dist = queue.popleft()
if len(visited[current]) == len(origins):
return sum(visited[current].values) # done, return sum of path lengths
adjs = adjacents.get(current)
if adjs is not None:
for next in adjs:
vis1 = visited.get(next)
vis2 = None
if vis1 is not None:
vis2 = vis1.get(origin)
else:
vis1 = {}
visited[next] = vis1
if vis2 is None:
vis1[origin] = dist + 1
queue.append((origin, next, dist + 1))
public static void main(String[] args) {
String[] s = { "WWWWWWWW", "WWW O WW", "WWW OW", "WWW WWWW", "WO WWWW", "WWW WWWW", "WO W", "WWWWWWWW" };
int[][] arr = new int[s.length][s[0].length()];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (s[i].charAt(j) == 'W')
arr[i][j] = -1;
else
arr[i][j] = Integer.MAX_VALUE;
}
}
int[] find = find(arr);
System.out.println(find[0] + ", " + find[1]);
}
// wall -1, office = 0, hall 1
public static int[] find(int[][] arr) {
int[] ret = new int[2];
int minsum = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] != -1) {
find(arr, i, j, 0);
int sum = sum(arr);
if (minsum > sum) {
minsum = sum;
ret[0] = i;
ret[1] = j;
}
}
}
}
return ret;
}
public static int sum(int[][] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] != -1){
sum += arr[i][j];
arr[i][j] = Integer.MAX_VALUE;
}
}
}
return sum;
}
// wall -1, office = 0, hall 1
public static void find(int[][] arr, int i, int j, int steps) {
if (i < 0 || j < 0 || i > arr.length - 1 || j > arr[0].length - 1)
return;
if (arr[i][j] == -1)
return;
if (arr[i][j] < steps)
return;
arr[i][j] = steps;
int[] dx = { 0, 0, -1, 1 };
int[] dy = { -1, 1, 0, 0 };
for (int k = 0; k < 4; k++) {
find(arr, i + dx[k], j + dy[k], steps + 1);
}
}
class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms.length == 0)
{
return;
}
for(int i = 0; i < rooms.length; i++)
{
for(int j = 0; j < rooms[0].length; j++)
{
if(rooms[i][j] == 0)
{
helperWallsAndGateDFS(rooms, i, j, 0);
}
}
}
return;
}
public void helperWallsAndGateDFS(int rooms[][], int i, int j, int dist)
{
if(i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < dist)
{
return;
}
rooms[i][j] = dist;
helperWallsAndGateDFS(rooms, i + 1, j, dist + 1);
helperWallsAndGateDFS(rooms, i - 1, j, dist + 1);
helperWallsAndGateDFS(rooms, i, j + 1, dist + 1);
helperWallsAndGateDFS(rooms, i, j - 1, dist + 1);
}
}
I don't know if I got the question alright but for this question I would use the Dijkstra's algorithm. Compute the Dijkstra's algorithm from every available position and keep a minimum (there might be more than one).
A little bit cumbersome to code but here is an implementation in python.
- Fernando July 13, 2017