Google MTV 面经

iamone14 发表于 2018-8-14 16:57
那n个杯子是两两之间都需要互相倒水么？这样一个step就是n^2了吧，m个step的话，时间复杂度高得吓人啊

就是V+E, E = V * (n^2), 用DFS才是真的exponential

scarletthln 发表于 2018-8-15 09:35
就是V+E, E = V * (n^2), 用DFS才是真的exponential

咦，难道BFS中的V不也是exponential增长的吗，每个V都会扩张成n^2个V
DFS和BFS归根到底的时间复杂度应该是一样的，都是V+E

iamone14 发表于 2018-8-14 20:28
咦，难道BFS中的V不也是exponential增长的吗，每个V都会扩张成n^2个V
DFS和BFS归根到底的时间复杂度应该 ...

并不是 DFS的复杂度有可能是V+E 也有可能是# of paths

楼主已经很强了闯入了决赛了都 希望会过

scarletthln 发表于 2018-8-15 12:34
并不是 DFS的复杂度有可能是V+E 也有可能是# of paths

# of path 不就是E吗，和BFS中的E是一样的呀，只不过两者访问的顺序不同

iamone14 发表于 2018-8-14 20:40
# of path 不就是E吗，和BFS中的E是一样的呀，只不过两者访问的顺序不同

当然不是了。。
比如
    1
     |  
    2
  /    \
3     4
# of paths 会把 1-2这条边重复访问两次, 等价于 k^V, k 是branching factor, 这才叫exponential
而V + E, 是每条边每个点的访问次数都是常数次

scarletthln 发表于 2018-8-14 12:34
第五题 如果是类似叁留舞 N个杯子求最快装满某容量水 DFS要怎么做。。
应该是标准的BFS吧 vertex是长度为N ...

讲真，不懂bfs怎么做。。。
首先这题lc365是找两两之间的gcd然后拿target去模这个gcd
那很明显拓展到n个杯子的话 应该就是backtracking枚举所有两两之间的gcd啊

不过补一句，三姐是真的差。n个杯子倒水这种数学题也问。以后你当面试官，不能给三姐手下留情啊

感谢楼主分享！
请问一下楼主可以具体讲一讲广告系统设计这题吗？

scarletthln 发表于 2018-8-15 13:01
当然不是了。。
比如
    1

原来你说的path是从起点开始的path，我想成了1-2，2-3，3-4这种Edge了，
DFS可以加cache呀，这样的话就不会重复走边了