狗狗厂昂赛

cser017

Tristan 发表于 2017-9-26 06:11
楼主求问MTV指的是？我经常看到这个一直不知道什么意思。。。。

mountain view 也是山景城，谷歌总部

Tristan

cser017 发表于 2017-9-26 06:13
mountain view 也是山景城，谷歌总部

噢哈哈哈哈这样多谢啦~

szyyn95

399 我猜面试官是不是说从一种货币到另一种货币有多种换的方式，然后要求找最佳的方法？那这个难道是用Floyd-Warshall做吗？（稍微改一下对于最短路径的定义）

cser017

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

szyyn95

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

cser017

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

szyyn95

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

cser017

szyyn95 发表于 2017-9-28 01:29
楼主你这么一说我都吓得不敢面谷歌了，怕面试雪崩直接黑名单了

总部好点吧毕竟波士顿牛校多
面试雪崩会进黑名单？

szyyn95

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

codemonk

第三轮我写了个dijikstra + binary heap的方法 O(ElogV)时间。。
不过这题要是有环怎么办？比如在环里面不停换钱，钱会越来越多，知道无穷大。。。这种情况面试官可能就会让写 bellman ford 检测环了吧。。

typedef pair<double, string> p;
int run(vector<pair<string, string>>& countries, vector<double>& ratio, string A, string B) {
unordered_map<string, unordered_map<string, double>> m;
unordered_map<string, double> type2ratio;
for(int i = 0; i < countries.size(); i++) {
m[countries[i].first][countries[i].second] = ratio[i];
m[countries[i].second][countries[i].first] = ratio[i];
type2ratio[countries[i].first] = type2ratio[countries[i].second] = 0.0;
}
priority_queue<p, vector<p>, function<bool(const p&, const p&)> > pq([](const p&a, const p&b){
return a.first < b.first;
});
pq.push({1.0, A});
type2ratio[A] = 1.0;
while(!pq.empty()) {
string curr = pq.top().second;
double r = pq.top().first;
pq.pop();
for(auto adj : m[curr]) {
if(r * adj.second > type2ratio[adj.first]) {
type2ratio[adj.first] = r * adj.second;
if(adj.first != B) pq.push({r * adj.second, adj.first});
}
}
}
return type2ratio[B];
}
int main(int argc, const char * argv[]) {
// insert code here...
vector<pair<string, string>> countries = {
{"A", "B"},
{"B", "C"},
{"A", "D"},
{"D", "E"},
{"E", "C"}
};
vector<double> ratio = {0.5, 1.2, 0.1, 0.2, 300};
cout << run(countries, ratio, "A", "C") << endl;
return 0;
}
[code]6
Program ended with exit code: 0

复制代码

[/code]

狗狗厂 昂赛