Bloomberg面试题 分析

wxl3691 发表于 2017-9-19 02:51
能解释下吗，我遇到递归， DFS就无法分析了， 为什么是2啊？

set里每个string都有选和不选两种情况，一共n个，所以2^n

wxl3691 发表于 2017-9-19 02:51
能解释下吗，我遇到递归， DFS就无法分析了， 为什么是2啊？

对不起，其实我只是猜测的。
我不确定你是不是这么做的：
每次把target string 分成， 0 到 i, 和 i 到 n 两个部分
然后判断 0到i 这一部分有没有，之后DFS(i到n）的部分
如果是这么做的话。当你遍历target string的时候，每次都会将剩下的i到n 分成两个部分
所以 2*2*2*2......... = 2^n


补充内容 (2017-9-19 03:04):
我还在刷题中，有错误请务必狠喷

seannaes 发表于 2017-9-19 03:02
对不起，其实我只是猜测的。
我不确定你是不是这么做的：
每次把target string 分成， 0 到 i, 和 i 到 ...

我就是这个思路， 应该是对的。谢谢你

wxl3691 发表于 2017-9-19 02:36
我没用什么DP，就DFS， 时间复杂度答 O(N^2), 烙印当场说我是错的， 说比O(N^2) 高

DFS的复杂度不可能是N^2。。。我觉得是2^N吧

westcoastboy 发表于 2017-9-19 03:29
DFS的复杂度不可能是N^2。。。我觉得是2^N吧

是的，当时口误，说错了，尴尬

谢谢分享~

求问lz啥时投的啊。。。一点消息都没有

cxw111 发表于 2017-10-10 00:55
求问lz啥时投的啊。。。一点消息都没有

投的早，赶的第一波，今年坑少，大家都是地狱模式

wxl3691 发表于 2017-10-10 00:56
投的早，赶的第一波，今年坑少，大家都是地狱模式

估计我没戏了
今年怎么感觉好难啊。。。

cxw111 发表于 2017-10-10 00:58
估计我没戏了
今年怎么感觉好难啊。。。

去年亚麻超额招，FB招2倍intern，今年google内部项目破产，大公司级联下来小公司也不好过，再加上新总统上台，budget变少，所以今年的名额会很少

补充内容 (2017-10-10 01:03):
今年的关键应该在 亚麻 这条船了，上不去估计就危险了