## Google Interview Question for Software Engineer / Developers

Country: United States

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

Paint fill + cache of the path + backtracking, keep min path in a global list.

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

Could you please elaborate a bit more?

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

why need paint fill?!

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

I feel DFS approach will solve the problem here as the intermediate results (ex: a string indicating the path) get stored on the system memory through recursive calls. And when we hit the destination, we return boolean (true else false) value based on which we get back with status whether the destination is reached or not and the result will contain the path.

Correct me i interpreted the question wrong!

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

DFS won't find the shortest path. BFS would.

``````11111111
10000001
10000001
10000001
10000001
10000001
10000001
31111111``````

If you order cell neighbors as RIGHT, BOTTOM, LEFT, TOP, then DFS would return with the longer route.
For other ordering, you can tweak the example to show, that that won't work either.

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

Since we do not know the location of 3 and there is no weight on route, I used Breath Search First. Otherwise, Dijkstra or Bellman-Ford as we learned on communication networks...
I used a matrix to track the parent of each node. I thought on using a list associated with each pendent to visit node and mark the visited in the same matrix (e.g. 4). Actually I think it use less memory with the "parent" list instead of matrix....

``````import java.util.LinkedList;

public class Snake{
static int N = 6;
static int M = 6;
int[][] matrix = new int[N][M];
Pair[][] mark = new Pair[N][M];

class Pair{
public int x;
public int y;
public Pair(int xVal,int yVal){
x = xVal;
y = yVal;
}
}

public static void main(String[] args){
Snake sn = new Snake();
sn.matrix[0] = new int[]{1,1,1,1,1,1};
sn.matrix[1] = new int[]{1,0,0,0,0,1};
sn.matrix[2] = new int[]{1,0,1,1,1,1};
sn.matrix[3] = new int[]{1,0,1,0,0,0};
sn.matrix[4] = new int[]{1,0,1,1,3,0};
sn.matrix[5] = new int[]{1,0,0,0,0,0};

sn.findRoute();
}

public  void findRoute(){
mark[0][0] = new Pair(0,0);
Pair found;
while(!visitList.isEmpty()){
Pair pair = visitList.removeLast();
found = getNeighbords(pair.x,pair.y,pair,visitList);
if(found != null){
trace(found);
break;
}
}
}
public  void trace(Pair dest){
int x = dest.x;
int y = dest.y;
Pair parent;
while(!(x == 0 && y == 0)){
System.out.println(x+" : "+y);
parent = (mark[x][y]);
x = parent.x;
y = parent.y;
}
}

public  Pair getNeighbords(int x,int y,Pair parent,LinkedList<Pair> queue ){
//Horizontal range
int xMin = Math.max(x-1, 0);
int xMax = Math.min(x+1,M-1);
int yMin = Math.max(y-1,0);
int yMax = Math.min(y+1,N-1);
for(int xp = xMin; xp <= xMax; xp++){
for(int yp = yMin; yp <= yMax; yp++){
//visited?
if(mark[xp][yp] != null)
continue;

mark[xp][yp] = parent;

//passable?
if(matrix[xp][yp] == 1){
}
//goal?
if(matrix[xp][yp] == 3){
System.out.println("found: "+x+":"+y);
return new Pair(xp,yp);
}
}
}
return null;
}
}``````

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

This solves only a possible solution. Not the shortest possible solution.

We need to use a back tracking + BFS combination to find the shortest path.

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

``````/*
Thought:
1) Using BFS
2) Find dest first, using A*
*/

import java.util.HashSet;
import java.util.ArrayList;
import java.util.Collections;

class PathStep {
int i, j;
PathStep prev;

public PathStep(int i, int j, PathStep prev) {
this.i = i;
this.j = j;
this.prev = prev;
}

public String toString() {
return "[" + i + ", " + j + "]";
}
}

class Main {
// BFS
public static void shortestPath(int[][] matrix) {
int N = matrix.length;
// initial
PathStep step = new PathStep(0, 0, null);
// using set to check if already traversed
HashSet<Integer> set = new HashSet<Integer>();
boolean findDest = false;
while(!queue.isEmpty() && !findDest) {
while(!queue.isEmpty()) {
step = queue.remove();
int i = step.i, j = step.j, id;
if(matrix[i][j] == 3) {	// find dest
findDest = true;
break;
}
PathStep next;
// move left
if(j > 0 && matrix[i][j - 1] != 0) {
id = N * i + (j - 1);
if(!set.contains(id)) {
next = new PathStep(i, j - 1, step);
}
}
// move right
if(j < N - 1 && matrix[i][j + 1] != 0) {
id = N * i + (j + 1);
if(!set.contains(id)) {
next = new PathStep(i, j + 1, step);
}
}
// move up
if(i > 0 && matrix[i - 1][j] != 0) {
id = N * (i - 1) + j;
if(!set.contains(id)) {
next = new PathStep(i - 1, j, step);
}
}
// move down
if(i < N - 1 && matrix[i + 1][j] != 0) {
id = N * (i + 1) + j;
if(!set.contains(id)) {
next = new PathStep(i + 1, j, step);
}
}
}
queue = tmpQueue;
}
if(findDest) {
// build path
ArrayList<PathStep> path = new ArrayList<PathStep>();
while(step != null) {
step = step.prev;
}
Collections.reverse(path);
// print path
for(int i = 0; i < path.size(); i++) {
if(i == path.size() - 1) {
System.out.println(path.get(i));
}
else {
System.out.print(path.get(i) + " -> ");
}
}
}
}

public static void main(String[] args) {
int[][] matrix = {
{1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,1},
{1,1,0,0,0,0,0,1},
{0,1,1,1,0,0,0,1},
{0,0,0,1,0,0,0,1},
{1,1,1,1,0,0,0,1},
{1,0,0,0,0,0,0,1},
{3,1,1,1,1,1,1,1}
};
shortestPath(matrix);
}
}``````

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

``````#include <iostream>
#include <queue>
#include <stack>

using namespace std;

void printPath(int prev[], int dest, int dist, int n) {
stack<int> st;

while (dest != 0) {
st.push(dest);
dest = prev[dest];
}

cout<< "Shortest distance to destination is: " << dist << " steps."<<endl;
cout << "0,0 => ";
while (!st.empty()) {
dest = st.top();
st.pop();
cout << dest/n<<","<<dest%n;
if(!st.empty())
cout<<" => ";
}
cout << endl;
}

void shortestPath(int mat[100][100], int n) {
int d[n*n];
int prev[n*n];
for(int i=0; i< n*n; ++i) {
d[i] = n*n+1;
prev[i] = -1;
}
d[0] = 0;
queue<int> q;
q.push(0);
bool reached = false;
while(!q.empty() && !reached) {
int curr = q.front();
int row = curr/n;
int col = curr%n;
if(mat[row][col] == 3){
// reached destination
reached = true;
break;
}
q.pop();
int next;
// go UP
if(row>0 && mat[row-1][col] != 0){
next = (row-1)*n + col;
if(d[next] > d[curr]+1){
d[next] = d[curr]+1;
prev[next] = curr;
q.push(next);
}
}
//go DOWN
if(row < n-1 && mat[row+1][col] != 0){
next = (row+1)*n + col;
if(d[next] > d[curr]+1){
d[next] = d[curr]+1;
prev[next] = curr;
q.push(next);
}
}
//go LEFT
if(col > 0 && mat[row][col-1] != 0){
next = row*n + col-1;
if(d[next] > d[curr]+1){
d[next] = d[curr]+1;
prev[next] = curr;
q.push(next);
}
}
//go RIGHT
if(col < n-1 && mat[row][col+1] != 0){
next = row*n + col+1;
if(d[next] > d[curr]+1){
d[next] = d[curr]+1;
prev[next] = curr;
q.push(next);
}
}
}

if(reached){
printPath(prev, q.front(), d[q.front()], n);
}
}

int main() {
int mat[100][100] = {{1,1,1,1,1,0},
{1,1,0,0,1,0},
{0,1,1,1,1,0},
{1,1,0,3,1,0},
{1,1,1,1,1,1},
{0,0,0,0,0,0}};

shortestPath(mat, 6);
}``````

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

``````package google;

import java.util.Collections;
import java.util.List;

public class ShortestPath {
public static List<Field> findShortestPath(int[][] area) {
Field[][] fields = new Field[area.length][area[0].length];
for (int i = 0; i < fields.length; i++) {
for (int j = 0; j < fields[0].length; j++) {
if (area[i][j] != 0) {
fields[i][j] = new Field(i, j, Integer.MAX_VALUE, null);
}
}
}

Field start = fields[0][0];
start.dist = 0;

Field dest = null;
Field cur;
while ((cur = q.poll()) != null) {
if (area[cur.x][cur.y] == 3) {
dest = cur;
}
visitNeighbour(fields, q, cur.x - 1, cur.y, cur);
visitNeighbour(fields, q, cur.x + 1, cur.y, cur);
visitNeighbour(fields, q, cur.x, cur.y - 1, cur);
visitNeighbour(fields, q, cur.x, cur.y + 1, cur);
}

if (dest == null) {
return Collections.emptyList();
} else {
cur = dest;
do {
} while ((cur = cur.prev) != null);

return path;
}
}

private static void visitNeighbour(Field[][] fields, LinkedList<Field> q, int x, int y, Field parent) {
int dist = parent.dist + 1;
if (x < 0 || x >= fields.length || y < 0 || y >= fields[0].length || fields[x][y] == null) {
return;
}
Field cur = fields[x][y];
if (dist < cur.dist) {
cur.dist = dist;
cur.prev = parent;
}
}

private static class Field implements Comparable<Field> {
public int x;
public int y;
public int dist;
public Field prev;

private Field(int x, int y, int dist, Field prev) {
this.x = x;
this.y = y;
this.dist = dist;
this.prev = prev;
}

@Override
public int compareTo(Field o) {
return dist - o.dist;
}
}

public static void main(String[] args) {
int[][] area = new int[][] {
{1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 1, 1},
{1, 1, 1, 3, 1, 1},
{0, 0, 0, 0, 0, 0}
};
List<Field> shortestPath = findShortestPath(area);
for (Field f : shortestPath) {
System.out.println(String.format("(%d;%d)", f.x, f.y));
}
}
}``````

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

In fact, I just tested my code. Turned out the cache is not working. It only stores the first path it has found. How should I fix this cache? If I took out the cache, the code works fine and is able to find the shortest path.

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

So did you have 50 interviews at Google recently?

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

A* algorithm.

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.