## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

``````import sys
from collections import deque

office = [ 'WWWWWWWWW',
'WW  O  WW',
'WWO   OWW',
'WW  O  WW',
'WWWWWWWWW' ]

def new_positions(current, free_positions):
x, y = current

res = []
for (x_1, y_1) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
if (x + x_1, y + y_1) in free_positions:
res.append((x + x_1, y + y_1))
return res

def find_paths(office):
offices = [(x, y) for (x, row) in enumerate(office) for (y, v) in
enumerate(row) if v == 'O']

free_positions = {}
positions = [ (x, y) for (x, row) in enumerate(office) for (y, v) in
enumerate(row) if v == ' ' or v == 'O' ]
min_total = sys.maxint
min_position = None

for starting_position in positions:
for position in positions:
free_positions[position] = sys.maxint

free_positions[starting_position] = 0
frontier = deque()
frontier.append((starting_position, 0))
while frontier:
position, distance = frontier.popleft()
new_distance = distance + 1

for new_position in new_positions(position, free_positions):
if new_distance < free_positions[new_position]:
free_positions[new_position] = new_distance
frontier.append((new_position, new_distance))

total = 0
for office_position in offices:
total += free_positions[office_position]

if total < min_total:
min_total = total
min_position = starting_position

return min_position, min_total``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Fernando, cool idea, just Dijkstra uses priority queues to do a shortest path on a weighted graph... yours looks more like BFS...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

how to run BFS Simultaneously from different origins

Comment hidden because of low score. Click to expand.
0
of 0 vote

@sxs155933: well, you can use one queue and place all start points in it together with an origin "id" which you need to use to maintain different visited sets, one per bfs frontier... maybe just draw the example with the map on a paper...

Comment hidden because of low score. Click to expand.
0
of 0 vote

ChrisK, i think it is just calling bfs function for each origin..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

# adjacents being a dictionary of list {0: [1,2,3], 4: [1, 3], 5: } 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
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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

vf;dvmf

Comment hidden because of low score. Click to expand.
0
of 0 vote

csd

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.length()];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.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 + ", " + find);
}

// wall -1, office = 0, hall 1
public static int[] find(int[][] arr) {

int[] ret = new int;
int minsum = Integer.MAX_VALUE;

for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[i][j] != -1) {
find(arr, i, j, 0);
int sum = sum(arr);
if (minsum > sum) {
minsum = sum;
ret = i;
ret = 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.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.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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Floyd warshall seems to have the easiest implementation. Then sum the path from each node and return the minimum one O(n^3).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

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