谁来带头BSO? - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

谁来带头BSO?

谁来带头BSO?# Stock

M*a2010-03-29 07:03

1 楼

Given an 2D array of characters. Find words in the array (either vertical or
horizontal). a character cannot be part of 2 words. Maximize the number of
characters used. Hint: 1D variant can be solved by Dynamic programming in
linear time.
onsite都做不出来
出这题的人脑子进水了

O*L2010-03-29 07:03

2 楼

做熊的先忍忍,让这些挣钱的先高兴高兴....

f*h2010-03-29 07:03

3 楼

哥onsite时比这个描述还复杂，而且没有hint，跪了

or
of

【在 M*******a 的大作中提到】

: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal). a character cannot be part of 2 words. Maximize the number of
: characters used. Hint: 1D variant can be solved by Dynamic programming in
: linear time.
: onsite都做不出来
: 出这题的人脑子进水了

g*u2010-03-29 07:03

4 楼

知道你的3X能源发了。发包子吧。
CLF有没有又上车？

d*i2010-03-29 07:03

5 楼

@[email protected]

O*L2010-03-29 07:03

6 楼

CLF 和ANR 把我美的啊!
ERX 也就是刚水上.
还是你来BSO 吧!

【在 g*****u 的大作中提到】

: 知道你的3X能源发了。发包子吧。
: CLF有没有又上车？

M*a2010-03-29 07:03

7 楼

是不是印度人？
有没有冲他树中指。
有没有反问他我给你出个这么难得您现场做得出么。

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

: 哥onsite时比这个描述还复杂，而且没有hint，跪了
:
: or
: of

l*r2010-03-29 07:03

8 楼

CLF真牛。

f*h2010-03-29 07:03

9 楼

白人经理，应该是bar raiser，第一个面试官，还迟到10分钟，一出这题我就懵了，我
面得是entry level呀，搞懂题意就花了好长时间，后来草草写了两行时间就到了。
leetcode已刷两遍，但运气真是差到家

【在 M*******a 的大作中提到】

: 是不是印度人？
: 有没有冲他树中指。
: 有没有反问他我给你出个这么难得您现场做得出么。

O*L2010-03-29 07:03

10 楼

一般搬了...

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

: CLF真牛。

g*e2010-03-29 07:03

11 楼

or
of
这题好像cracking the coding interviews里面有。

【在 M*******a 的大作中提到】

l*r2010-03-29 07:03

12 楼

谦虚的很假

【在 O****L 的大作中提到】

: 一般搬了...

M*a2010-03-29 07:03

13 楼

您说的是最后一章最后一道把，不一样的。

【在 g*********e 的大作中提到】

:
: or
: of
: 这题好像cracking the coding interviews里面有。

O*L2010-03-29 07:03

14 楼

38时候我是免费在这里推荐,
55的时候100伪币卖出去了5个人.
现在.....

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

: 谦虚的很假

d*i2010-03-29 07:03

15 楼

请问你什么时候面的A家？小弟下星期一面onsite。害怕中。。

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

: 白人经理，应该是bar raiser，第一个面试官，还迟到10分钟，一出这题我就懵了，我
: 面得是entry level呀，搞懂题意就花了好长时间，后来草草写了两行时间就到了。
: leetcode已刷两遍，但运气真是差到家

l*r2010-03-29 07:03

16 楼

可惜，错过了，下次要大声喊，记住咯。

【在 O****L 的大作中提到】

: 38时候我是免费在这里推荐,
: 55的时候100伪币卖出去了5个人.
: 现在.....

g*e2010-03-29 07:03

17 楼

恩好像不一样

【在 M*******a 的大作中提到】

: 您说的是最后一章最后一道把，不一样的。

O*L2010-03-29 07:03

18 楼

我说过让你别烧FCX,别的我真不敢乱说啊,大牛.

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

: 可惜，错过了，下次要大声喊，记住咯。

M*a2010-03-29 07:03

19 楼

这题怎么做来着？
二维DP题我老一支不大行

l*r2010-03-29 07:03

20 楼

是的，幸亏早割肉楚剧乐。钥匙屋到现在早叫乐。
谢谢！

【在 O****L 的大作中提到】

: 我说过让你别烧FCX,别的我真不敢乱说啊,大牛.

R*d2010-03-29 07:03

21 楼

这题可以用BFS加减枝吗？

Given an 2D array of characters. Find words in the array (either vertical or
horizontal)........

【在 M*******a 的大作中提到】

C*G2010-03-29 07:03

22 楼

大牛的erx看来上周五捞底AD了，太厉害了
gxgx

【在 O****L 的大作中提到】

: CLF 和ANR 把我美的啊!
: ERX 也就是刚水上.
: 还是你来BSO 吧!

S*12010-03-29 07:03

23 楼

or
of
可以了，比Google那个密码问题简单了

【在 M*******a 的大作中提到】

O*L2010-03-29 07:03

24 楼

靠,那情况不捞就是坐以待毙.
明天就出了捞的那些价钱下来了,我就放心了.
你还是鞭尸要紧.

【在 C*G 的大作中提到】

: 大牛的erx看来上周五捞底AD了，太厉害了
: gxgx

l*12010-03-29 07:03

25 楼

这个find words是要求字母必须连续还是subsequence就算？

k*n2010-03-29 07:03

26 楼

强烈支持BSO，最近版众士气低落啊。。

x*i2010-03-29 07:03

27 楼

move on, good luck!!

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

e*a2010-03-29 07:03

28 楼

靠，今天丢了半盏银灯

【在 O****L 的大作中提到】

: 做熊的先忍忍,让这些挣钱的先高兴高兴....

l*12010-03-29 07:03

29 楼

求1D DP的O（n）解法。只想出了n^2的

M*a2010-03-29 07:03

30 楼

就是，我就觉得phone interview能知道一维怎么做就不错了吧。

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

: 求1D DP的O（n）解法。只想出了n^2的

M*a2010-03-29 07:03

31 楼

就是，我就觉得phone interview能知道一维怎么做就不错了吧。

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

: 求1D DP的O（n）解法。只想出了n^2的

t*s2010-03-29 07:03

32 楼

DP的nature就是n^2，但是利用字符不能重用的条件应该可以在计算实际cost的时候降
阶到O(n)

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

: 求1D DP的O（n）解法。只想出了n^2的

g*i2010-03-29 07:03

33 楼

谁能提供个1D数组，O(n)的思路？
比如给cat,
c的时候，发现不是word，
ca的时候要看"ca",
cat的时候既要看"cat", 也要看"at", 这样就不是O(n)了。

c*m2010-03-29 07:03

34 楼

上次面一个entry level的contract的职位，onsite的时候也问了个类似的问题，没做
出来。面试官是印度人。

M*a2010-03-29 07:03

35 楼

这种做法通常都是2^n了吧，不是polynomial了吧。

or

【在 R*********d 的大作中提到】

: 这题可以用BFS加减枝吗？
:
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal)........

M*a2010-03-29 07:03

36 楼

google 密码题是哪道？

【在 S******1 的大作中提到】

:
: or
: of
: 可以了，比Google那个密码问题简单了

M*a2010-03-29 07:03

37 楼

显然要求连续么

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

: 这个find words是要求字母必须连续还是subsequence就算？

M*a2010-03-29 07:03

38 楼

我现在一想好象一维也只有O(n^2)思路么，怎么整成O(n)？

【在 g*******i 的大作中提到】

: 谁能提供个1D数组，O(n)的思路？
: 比如给cat,
: c的时候，发现不是word，
: ca的时候要看"ca",
: cat的时候既要看"cat", 也要看"at", 这样就不是O(n)了。

c*r2010-03-29 07:03

39 楼

mark

l*i2010-03-29 07:03

40 楼

dp(m,n) = max_{i,j} dp(i,j) + row_word[j]
or dp(i,j) + col_word[i]
dp(i,j) is the max number of char can be used in matrix[0..i-1][0..j-1]
row_word[j] is max number of char can be used in some row to make one word
in submatrix[0..m-1][j..n-1]
col_word[i] is max number of char can be used in some col to make one word
in submatrix[i..m-1][0..n-1]

M*a2010-03-29 07:03

41 楼

好像不大对still
要是word分布是这样的，你这做法行不行？

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

: dp(m,n) = max_{i,j} dp(i,j) + row_word[j]
: or dp(i,j) + col_word[i]
: dp(i,j) is the max number of char can be used in matrix[0..i-1][0..j-1]
: row_word[j] is max number of char can be used in some row to make one word
: in submatrix[0..m-1][j..n-1]
: col_word[i] is max number of char can be used in some col to make one word
: in submatrix[i..m-1][0..n-1]

o*g2010-03-29 07:03

42 楼

没太看懂题目
这个words有字典么？还是给定一个word？

or
of

【在 M*******a 的大作中提到】

s*B2010-03-29 07:03

43 楼

mark

M*a2010-03-29 07:03

44 楼

显然有字典的意思

【在 o***g 的大作中提到】

: 没太看懂题目
: 这个words有字典么？还是给定一个word？
:
: or
: of

s*c2010-03-29 07:03

45 楼

可以和1维那样类似的想法来2维dp
只是每隔子问题的解不能简单用dp_sol[i]来表示,
而是用一个长度n的 vector来index每个子问题的解dp_sol[i1,i2,...i_n]，
i1,i2,...i_n 描述了一个把2d矩阵切成两块的一个界面
i_k表示第k列上这个界面的坐标.
对每一个子问题, 从界面的边界开始尝试添加word
总共有n^n个子问题, 然后每个子问题的递推式可以在n^2时间搞定
(需要preprocess这个矩阵, 计算从每点出发可以cover那些word)

or
of

【在 M*******a 的大作中提到】

M*a2010-03-29 07:03

46 楼

看不大懂啊同学。
首先你这做法时间复杂度是polynomial还是指数
其次你这上就一分为二的做法如果是上面这个图的情况能不能得到最优解还？

【在 s******c 的大作中提到】

: 可以和1维那样类似的想法来2维dp
: 只是每隔子问题的解不能简单用dp_sol[i]来表示,
: 而是用一个长度n的 vector来index每个子问题的解dp_sol[i1,i2,...i_n]，
: i1,i2,...i_n 描述了一个把2d矩阵切成两块的一个界面
: i_k表示第k列上这个界面的坐标.
: 对每一个子问题, 从界面的边界开始尝试添加word
: 总共有n^n个子问题, 然后每个子问题的递推式可以在n^2时间搞定
: (需要preprocess这个矩阵, 计算从每点出发可以cover那些word)
:
: or