## Google Interview Question for Software Engineers

• 2

Country: Korea
Interview Type: In-Person

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

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION:
BFS

``````from heapq import heappush, heappop
import numpy as np
def minCostPath(maze):
if len(maze) is 0 or len(maze[0]) == 0 or maze[0, 0] == -1:
return

m, n = len(maze), len(maze[0])
distances = np.zeros(shape = (m, n))
distances.fill(-1)

heap = []
heappush(heap, (maze[0, 0], 0, 0))
value = maze[0, 0]
distances[0, 0] = value
neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while heap and distances[m - 1, n - 1] == -1:
dist, x, y = heappop(heap)
for neighbor in neighbors:
i, j = x + neighbor[0], y + neighbor[1]
if i >= 0 and j >= 0 and i < m and j < n and maze[i, j] != -1 and distances[i, j] == -1:
heappush(heap, (maze[i, j] + dist, i, j))
distances[i, j] = maze[i, j] + dist
print distances

if distances[m - 1][n - 1] == -1:
return

x, y = m - 1, n - 1
path = []
while x != 0 or y != 0:
path.append((x, y, distances[x, y]))
x, y = getMinParent(distances, x, y, neighbors)
path.append((0, 0, maze[0, 0]))

return path

def getMinParent(distances, x, y, neighbors):
minDist = distances[x, y]
fromx, fromy = None, None
for neighbor in neighbors:
i, j = x + neighbor[0], y + neighbor[1]
if i >= 0 and j >= 0 and i < len(distances) and j < len(distances[0]) and distances[i, j] >= 0 and distances[i, j] <= minDist:
fromx, fromy = i, j
minDist = distances[i, j]
return fromx, fromy``````

A tester

``````minCostPath(np.array([[4,2,-1,1,1],
[1,-1,6,7,1],
[4,-1,3,0,1],
[4,7,3,10,1],
[4,8,6,-1,1],
]))``````

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

#4, Djkstra.

``````#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Label
{
public:
Label(int r, int c, int cost, Label* prev)
{
r_ = r;
c_ = c;
cost_ = cost;
prev_ = prev;
}
int r_, c_, cost_;
Label* prev_;
};

class LabelComparator
{
public:
bool operator()(const Label* l1, const Label* l2)
{
return l1->cost_ > l2->cost_;
}
};

void PushLabel(priority_queue<Label*, vector<Label*>, LabelComparator>& pq, vector<vector<int>> &m, vector<Label* > &labels, int r, int c, Label* prev)
{
if (r >= 0 &&
r < m.size() &&
c >= 0 &&
c < m[r].size() &&
m[r][c] >= 0 &&
m[r][c] != numeric_limits<int>::max())
{
int base_cost = prev ? prev->cost_ : 0;
Label *l = new Label(r, c, base_cost + m[r][c], prev);
labels.push_back(l);
pq.push(l);
}
}

vector<pair<int, int>> ShortestPath(vector<vector<int>> &m, int source_r, int source_c, int target_r, int target_c)
{
vector<pair<int, int>> path;
vector<Label*> labels;
priority_queue<Label*, vector<Label*>, LabelComparator> pq;
PushLabel(pq, m, labels, source_r, source_c, NULL);
while (!pq.empty())
{
Label* l = pq.top();
pq.pop();
if (m[l->r_][l->c_] != numeric_limits<int>::max())
{
m[l->r_][l->c_] = numeric_limits<int>::max();
if (l->r_ == target_r &&
l->c_ == target_c)
{
while (l)
{
path.push_back(pair<int, int>(l->r_, l->c_));
l = l->prev_;
}
reverse(path.begin(), path.end());
break;
}
PushLabel(pq, m, labels, l->r_ + 1, l->c_, l);
PushLabel(pq, m, labels, l->r_ - 1, l->c_, l);
PushLabel(pq, m, labels, l->r_, l->c_ + 1, l);
PushLabel(pq, m, labels, l->r_, l->c_ - 1, l);
}
}
for (auto l : labels)
{
delete l;
}
return path;
}

int main()
{
vector<vector<int>> m = {
{ 1, -1, 6, 7, 1 },
{ 4, -1, 3, 0, 1 },
{ 4, 7, 3, 10, 1 },
{ 4, 8, 6, -1, 1 }
};
vector<pair<int, int>> path = ShortestPath(m, 0, 0, m.size() - 1, m[0].size() - 1);
for (auto p : path)
{
cout << "(" << p.first << "," << p.second << ")=>";
}
cout << "\n";
return 0;
}``````

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.