谷歌全职电面面经

刚面完GG,399, evaluate division,就是把字母换成了币币之间的汇率,建个map 存下edge, graph dfs 或者bfs，搜索一下。
gg的风格感觉变了，不能一上来就写题，他会要求我问一些关于这个input，o

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

m30.gif" smilieid="106" border="0" alt="" />。。希望币币能大涨，面试官的心情能好些。求gg收留发个onsite！

nicemayi 发表于 2018-1-18 18:48
这道题可以用dijsktra来解吗？

面试官没说找最短路径，他只要返回最小，最大的汇率就行了，我觉得就是dfs的时候全部走一下，判断下大小就可以了

应该是要找negative loop（汇率取log作weight），可能bellman Ford可以

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这个follow up 面试官期待怎答呢?

不知道哪裡來的題目呢?

这道题可以用dijsktra来解吗？

谢谢楼主 祝好运- ps 我买的已经缩水30%了，抱抱楼主

codingsapien 发表于 2018-1-18 20:52
应该是要找negative loop（汇率取log作weight），可能bellman Ford可以

单纯对所有汇率取反变负数，保证图上同号是负值可行不？

nicemayi 发表于 2018-1-19 10:17
单纯对所有汇率取反变负数，保证图上同号是负值可行不？

关键你需要的是走一圈回到原来的币种最终的比例，就等同于每条边的汇率取log然后求寻找weight sum的负数的loop了

codingsapien 发表于 2018-1-19 10:20
关键你需要的是走一圈回到原来的币种最终的比例，就等同于每条边的汇率取log然后求寻找weight sum的负数 ...

log的sum最小的解不一定是直接sum最小的解啊 如果真要这么做得给出数学证明