Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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[0].empty())
{
priority_queue<Label, vector<Label>, greater<Label>> pq;
unordered_set<uint64_t> seen;
vector<Label> labels;
for (int col = 0; col < m[0].size(); ++col) {
labels.push_back(Label(-1, labels.size(), Node(0, col), m[0][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[0].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;
}
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[0].length + y;
To convert the ID back to a point, do
x = nodeID / matrix[0].length;
y = nodeID % matrix[0].length;
- aonecoding August 03, 2017