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

- Fernando July 13, 2017 | Flag Reply
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...

- Chris July 13, 2017 | Flag Reply
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.

- Chris July 13, 2017 | Flag Reply
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.

- Fernando July 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how to run BFS Simultaneously from different origins

- sxs155933 July 16, 2017 | Flag Reply
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...

- Chris July 16, 2017 | Flag Reply
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..

- sxs155933 July 17, 2017 | Flag Reply
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?

- sxs155933 July 17, 2017 | Flag Reply
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

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

- Chris July 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vf;dvmf

- Anonymous August 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

csd

- Anonymous August 08, 2017 | Flag Reply
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[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);
		}
	}

- sudip.innovates October 27, 2017 | Flag Reply
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[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);
    }
}

- Enam Shah April 03, 2018 | Flag Reply
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).

- AV June 14, 2019 | Flag Reply


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

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