Bloomberg面试题 分析

问大家一道Bloomberg面试题， 给一个string (''applea

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

间复杂度是多少？我用递归做的， 但分析不出复杂度

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):
我还在刷题中，有错误请务必狠喷

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

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

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

119018682 发表于 2017-9-19 02:47
请问楼主是java选手么

是Java选手， 面个实习第一题就是word break, 今天才知道， 在我写两遍做出来后， 烙印送上奇招， BST to Double Linked List, 心满意足地将我挂掉

大家不要用set去递归啊， 因为有说set里有 百万的string

请参考 利口 word break, 用dp 做

补充内容 (2017-9-19 02:31):
if( input[i...j] belongs in dictionary) T[i][j] = i
else{
     T[i][j] = k if T[i][k-1] != -1 && T[k][j] != -1

seannaes 发表于 2017-9-19 02:28
请参考 利口 word break, 用dp 做

我会做，但我问的是 时空复杂度

wxl3691 发表于 2017-9-19 02:29
我会做，但我问的是 时空复杂度

二维dp, 都是O(N^2)

seannaes 发表于 2017-9-19 02:33
二维dp, 都是O(N^2)

我没用什么DP，就DFS， 时间复杂度答 O(N^2), 烙印当场说我是错的， 说比O(N^2) 高

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

DFS 的话, 时间O(2^n)

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

请问楼主是java选手么

seannaes 发表于 2017-9-19 02:47
DFS 的话, 时间O(2^n)

能解释下吗，我遇到递归， DFS就无法分析了， 为什么是2啊？