## Google Interview Question for Software Engineers

• 2

Country: United States
Interview Type: In-Person

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

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

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

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

Solution:
Breath First Search.
Create a map that stores Map<Node, [PreviousNode, Cost]> the cost to the current node.
Since the question asks for the actual shortest path, in the map also store the previous node in the path.
During the BFS, if the current node has been visited before, but the current cost < former cost, update the cost and route for the current node (only keep the min cost route). Otherwise if current cost > former cost, stop search by not including the current node into the BFS queue.

To stand for a node in the map with an integer rather than a point (x, y), do
nodeID = x * matrix.length + y;

To convert the ID back to a point, do
x = nodeID / matrix.length;
y = nodeID % matrix.length;

``````//Follow-up
public void minCostPath(int[][] matrix) {
Queue<Integer> queue = new ArrayDeque<>();
Map<Integer, int[]> map = new HashMap<>(); //key: current location; value: the previous node from where it gets to the current location, value:total cost up to current node
for(int j = 0; j < matrix.length; j++) { //put first row into queue
if(matrix[j] != 0) {
map.put(j, new int[] {-1, matrix[j]});
}
}
int destination = -1, minCost = Integer.MAX_VALUE;
while(!queue.isEmpty()) {
int id = queue.poll();
int fromX = id / matrix.length, fromY = id % matrix.length;
if(fromX + 1 < matrix.length) {
int cost = moveMinCost(queue, map, matrix, id, fromX + 1, fromY);
if (cost >= 0 && fromX + 1 == matrix.length - 1) {
if (cost < minCost) {
destination = id + matrix.length;
minCost = cost;
}
}
}
if(fromY + 1 < matrix.length)
moveMinCost(queue, map, matrix, id, fromX, fromY + 1);
if(fromX - 1 >= 0)
moveMinCost(queue, map, matrix, id, fromX - 1, fromY);
if(fromY - 1 >= 0)
moveMinCost(queue, map, matrix, id, fromX, fromY - 1);
}
if(destination == -1) return; //no such path from first row to last row
while(map.containsKey(destination)) {   //print shortest path from destination to source
int x = destination / matrix.length, y = destination % matrix.length;
System.out.println("(" + x + ","+ y + "),");
destination = map.get(destination);
}
}

private int moveMinCost(Queue<Integer> queue, Map<Integer, int[]> map, int[][] matrix, int from, int x, int y) {
if(matrix[x][y] == 0) return -1;
int id = x * matrix.length + y;
int cost = map.get(from) + matrix[x][y];
if(!map.containsKey(id) || map.get(id) > cost) {
map.put(id, new int[]{from, cost});
return cost;
}
return -1;
}``````

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

Apply BFS through a queue, with each Node containing pointer to previous Node and cost so far. Keep track of nodes visited. If a Node is present again in the queue, it can be ignored as we previously traversed it with lower cost.

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

The original question: BFS.
The follow up: Dijkstra (the code below).

``````class Node {
public:
Node(int row, int col)
{
row_ = row;
col_ = col;
}
int row_, col_;
};

class Label {
public:
Label(int parent_idx, int idx, Node node, int cost) : node_(node.row_, node.col_)
{
parent_idx_ = parent_idx;
idx_ = idx;
cost_ = cost;
}
bool operator>(Label const &other) const
{
return cost_ > other.cost_;
}

int idx_, parent_idx_;
Node node_;
int cost_;
};

vector <Node> ShortestPath(vector<vector<int>> const &m)
{
vector<Node> path;
if (!m.empty() &&
!m.empty())
{
priority_queue<Label, vector<Label>, greater<Label>> pq;
unordered_set<uint64_t> seen;
vector<Label> labels;
for (int col = 0; col < m.size(); ++col) {
labels.push_back(Label(-1, labels.size(), Node(0, col), m[col]));
pq.push(labels.back());
}
while (!pq.empty()) {
Label l = pq.top();
pq.pop();
Node n = l.node_;
uint64_t key = ((uint64_t)n.row_ << 32) | n.col_;
if (m[n.row_][n.col_] != 0 &&
seen.find(key) == seen.end())
{
seen.insert(key);
if (n.row_ == m.size() - 1) {
for (int i = l.idx_; i != -1; i = labels[i].parent_idx_) {
path.push_back(labels[i].node_);
}
reverse(path.begin(), path.end());
break;
}
if (n.row_ - 1 >= 0) {
labels.push_back(Label(l.idx_, labels.size(), Node(n.row_ - 1, n.col_), l.cost_ + m[n.row_ - 1][n.col_]));
pq.push(labels.back());
}
if (n.row_ + 1 < m.size()) {
labels.push_back(Label(l.idx_, labels.size(), Node(n.row_ + 1, n.col_), l.cost_ + m[n.row_ + 1][n.col_]));
pq.push(labels.back());
}
if (n.col_ - 1 >= 0) {
labels.push_back(Label(l.idx_, labels.size(), Node(n.row_, n.col_ - 1), l.cost_ + m[n.row_][n.col_ - 1]));
pq.push(labels.back());
}
if (n.col_ + 1 < m.size()) {
labels.push_back(Label(l.idx_, labels.size(), Node(n.row_, n.col_ + 1), l.cost_ + m[n.row_][n.col_ + 1]));
pq.push(labels.back());
}
}
}
}
return path;
}``````

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

use Dijkstra

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.