Google电面Intern面经【挂】

匿名用户-RZSLG *2021-12-12 14:00:15* · 2021-12-12 14:00:15

求问第二题，看起来就是分别求A, B 到 D 的shortest path，然后相加？求问还有什么别的条件吗？

匿名用户-PMYYO *2021-12-13 02:13:30* · 2021-12-13 02:13:30

nullFrank 发表于 2021-12-11 15:59
第二题感觉直接吧树转化成一个graph然后从target出发bfs 知道吧两个node都走到然后停止记录走到每个node ...

匿名用户-PMYYO *2021-12-13 02:14:41* · 2021-12-13 02:14:41

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

匿名用户-PMYYO *2021-12-13 02:15:36* · 2021-12-13 02:15:36

匿名者发表于 2021-12-11 22:00
求问第二题，看起来就是分别求A, B 到 D 的shortest path，然后相加？求问还有什么别的条件吗？

A 和B可能会有一段共同的path，这段路只能加一份

匿名用户-L977O *2021-12-31 05:58:22* · 2021-12-31 05:58:22

请问楼主，第一题如果求不同path的frequency的话，怎么能用hashmap呢？请问是key为string 是path so far吗？那么如果用memo的话就是每回遇到一样path的+=1吗？但是这样的话，怎么能把recursion下面几层的path的freq也加一呢？谢谢楼主已加米

宋宇航11

LZ请问第一题的暴力法是怎么做，我能想到的是DFS

水山木木

宋宇航11 发表于 2021-12-31 15:53:07
LZ请问第一题的暴力法是怎么做，我能想到的是DFS

我是直接暴力for loop的后来想到感觉可以dp 不过具体没有想到

水山木木

宋宇航11 发表于 2021-12-31 15:53:07
LZ请问第一题的暴力法是怎么做，我能想到的是DFS

？？我刚刚好像莫名其妙加个米笑死我是暴力forloop的后来想到可能可以dp做…不过当场是没写完

helloworld1997

第一题 dp可以展开讲讲吗？
第二题可以dijkstra算法我觉得

Google电面Intern面经 【挂】