Google Interview Question
Software EngineersCountry: Korea
Interview Type: In-Person
#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;
}
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
A tester
- aonecoding May 06, 2018