Google 实习面经

hhcctvwwa 发表于 2018-1-20 23:57
感谢题主，第二题BFS的话，初始长度为n，T(n) = nT(n - 1) =...=n!, 应该是factorial的复杂度吧

我也觉得是时间复杂度是 n!... 但好像没跟面试官说清楚。哭

哦哦，请问楼主一下第二题用什么思路做呢，如果recursion那么每个string删除一个字母，call check，然后对得出的string 再删除每个字母，这样复杂度太高了吧，谢谢楼主

麻烦请问一下楼主，第一题有重复的情况下，怎么用暴力搜索？是不是需要一个visited数组来保存b是否被访问过？

dafeiyang 发表于 2018-1-22 00:38
麻烦请问一下楼主，第一题有重复的情况下，怎么用暴力搜索？是不是需要一个visited数组来保存b是否被访问过 ...

是的。字数字数

面的不太好 不过还是拿到加面了。

楼主加油！沾沾仙气

楼主您好，谢谢您的分享。第一题您提到了暴力解，但是暴力解要怎么才能做到是mn呢？如果for for loop的话，怎么知道某个元素有多少个呢？如果要是记录元素个数的话，那么这种解法也就是o（m+n）吧。还有就是list里怎么能存各种type呢？还是说就是Character或者是String呢？

谢谢楼主

楼主加面加油！！！

第一问O(nlogn)的时候，list是已经sort好了吗？还是要自己sort?虽然复杂度是没差的哈哈

第二问bfs 和dfs应该都是 O(n!)吧

ja0b 发表于 2018-2-4 07:16
楼主加面加油！！！

第一问O(nlogn)的时候，list是已经sort好了吗？还是要自己sort?虽然复杂度是没差的 ...

第一问sort好的，第二问是 O（！n）没错

rogerlin1234 发表于 2018-2-4 07:23
第一问sort好的，第二问是 O（！n）没错

好嘞～

楼主加面啥时候啊？好好准备呀！