Google电面挂经 + 求助

处理完f1后应该要根据graph来建立一个HashMap来存任意两个string的ratio吧，比如HashMap<pair<str1, str2>, ratio>， 这样在处理f2时就能做到O(1)，速度就会快很多。这个hashMap跟LZ说的Map<Key1, Map<Key2, Ratio>>类似。

店面面这个 感觉好难啊。。。

这题是不是用有向图的bfs就可以解决了？ 举个例子，比如说Given A, B, 0.5,就可以建立一条边A->B,权重是0.5; 另一条边B->A,权重是1/0.5。以此类推，然后比如要求C,B,的那个ratio，其实就是等价于以C为起点，B为终点经过的所有路径权重的乘积。

yueliu2366 发表于 2016-3-29 20:48
这题是不是用有向图的bfs就可以解决了？ 举个例子，比如说Given A, B, 0.5,就可以建立一条边A->B,权重是0.5 ...

有向图 + BFS可行。但在推进的过程中，除了需要像普通的BFS需要存一个queue和一个visited的标记外，visited标记不能存成set，因为层层推进的过程中，每一个node的ratio都有不同的值，所以visited要存成map。

昨天后来又写了下这个题目，算是写出来了，没有真正地创建graph，而是将每一个Node存在一个Map<String, Map<String, Double>>里面

为了提高效率，在BFS的过程中，可以进行类似Union Find的path compression操作，就是将root和所有中间经过的node都connect起来，让graph越来越接近complete

另外union find应该也可以解这个题

waikai 发表于 2016-3-29 10:14
好详实的面经。谢谢lz。
我有一些其他思路，但没有具体码出来。先抛砖引玉了。
首先可以对f1做Union Find ...

嗯，Union Find做这个题是比较好的，尤其是在告知f2比较大的时候

我后来自己写的是在BFS的过程中不断地connect从root到每一个level经过的node，让这个graph更加complete，相当于进行了UF的path compression

lz最后怎么，有要到加面的机会吗？

仔細想想這題目不難。bfs+backtracking

感谢分享

[quote][url=forum.php?mod=redirect

bfs的话不需要backtrack

[quote][url=forum.php?mod=redirect

还没有消息