Groupon新鲜面经 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Groupon新鲜面经

Groupon新鲜面经# JobHunting - 待字闺中

z*82013-09-24 07:09

1 楼

resume talk
算法:
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词，并给出所有
的答案。
没答好，用了recursion没想到DP.
问：怎么知道某个问题可以用DP做？

w*j2013-09-24 07:09

2 楼

这个是常见的题啊
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
http://www.geeksforgeeks.org/dynamic-programming-set-32-word-br

z*82013-09-24 07:09

3 楼

嗯我也看到了。。。事情太多准备不够，脑子也不够活络了

w*j2013-09-24 07:09

4 楼

安拉....
看看，记住了，下次就好了 :)

l*n2013-09-24 07:09

5 楼

有subproblem overlap的递归都是dp。

【在 z*********8 的大作中提到】

: resume talk
: 算法:
: 给一个bool IsWord(string)的API, 判断能否把一个string分割成单词，并给出所有
: 的答案。
: 没答好，用了recursion没想到DP.
: 问：怎么知道某个问题可以用DP做？

c*p2013-09-24 07:09

6 楼

mark

f*b2013-09-24 07:09

7 楼

对，一看就知道是上DP

【在 l*n 的大作中提到】

: 有subproblem overlap的递归都是dp。

p*22013-09-24 07:09

8 楼

LZ解的不错，这个帖子太误导了，这题一看就是DFS。

l*n2013-09-24 07:09

9 楼

计算是否能split直接dfs & backtrack是不错。不过需要输出所有组合的话，还是需要
memoization的。比如feelink，可以是fee+link也可以是feel+ink，所以dp还是要的。

【在 p*****2 的大作中提到】

: LZ解的不错，这个帖子太误导了，这题一看就是DFS。

p*22013-09-24 07:09

10 楼

感觉你说反了。

【在 l*n 的大作中提到】

: 计算是否能split直接dfs & backtrack是不错。不过需要输出所有组合的话，还是需要
: memoization的。比如feelink，可以是fee+link也可以是feel+ink，所以dp还是要的。

s*u2013-09-24 07:09

11 楼

感觉比唯一解的那个题目复杂好多。因为是要输出所有组合，如果说dp的话，也就是说
要建立一个 map< string, vector >，然后再把这个vector里的string都遍历
一遍，和prefix的单词组合起来，组成新的vector？想想就头大。。。

m*k2013-09-24 07:09

12 楼

http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
the OP 居然划掉了
memoized.put(input, prefix + " " + segSuffix);
，搞错没有哦。

【在 w******j 的大作中提到】

: 这个是常见的题啊
: http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
: http://www.geeksforgeeks.org/dynamic-programming-set-32-word-br

s*u2013-09-24 07:09

13 楼

不需要吧？递归的返回值是一个 vector就可以了吧？
只是DP应该能降低time cost，因为的确是有重复的subproblems，只是感觉也会增加许
多 space cost。

【在 l*n 的大作中提到】

p*22013-09-24 07:09

14 楼

(def dict #{"i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream",
"icecream",
"man", "go", "mango"})
(def input "ilikesamsung")
(defn dfs [str, start, curr, list]
(if (= curr (count str))
(when (= start (count str))
(println (reverse list)))
(let [next (inc curr) sub (subs str start next)]
(when (contains? dict sub)
(dfs input next next (cons sub list)))
(dfs input start next list))
))
(dfs input 0 0 ())

A*o2013-09-24 07:09

15 楼

output sensitive，用动态规划改变不了指数复杂度的本质，recursion就好了

f*w2013-09-24 07:09

16 楼

这种要列出所有答案的，明显recursion啊
DP没用

f*t2013-09-24 07:09

17 楼

用DP存的都是答案，输出的每一条path都是答案，而直接recursion大部分path可能都
不是答案。
不过像楼上说的，output sensitive，用动态规划改变不了指数复杂度的本质，
recursion就好了。理论上复杂度是一样的。
写起来的话，肯定是直接dfs简单。
面试官的要求是关键。上次半海不是说写了个dp的，结果面试官不懂dp。

【在 f*******w 的大作中提到】

: 这种要列出所有答案的，明显recursion啊
: DP没用

s*u2013-09-24 07:09

18 楼

C++写了一个，如果不用DP的话，把这个map去掉即可，试了一两个字符串似乎没问题。
vector wordBreak( string s, map< string, vector >& cache){

vector vs;
vector suffixSet;
string tmp;

if( s.size() == 0 ){

vs.push_back(s);
return vs;
}

if(cache.count(s) > 0)
return cache[s];

string prefix, suffix;

for(int i = 1; i <= s.size(); i++){

prefix = s.substr(0,i);

if( isWord(prefix) ){

suffix = s.substr(i);
suffixSet = wordBreak(suffix,cache);

for(vector::iterator it = suffixSet.begin(); it !=
suffixSet.end(); it++){
tmp = prefix + ' ' + (*it);
vs.push_back(tmp);
}

}

}
cache[s] = vs;

return vs;
}

s*u2013-09-24 07:09

19 楼

不过似乎很多人说的dp跟我理解的不是一回事。好像很多人说到DP，实际上是用非递归
的方法？我理解的dp就是careercup书上写的，把已经算过的结果存起来。。汗