气死咱们这帮EB了! - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>EB23 - 劳工卡

气死咱们这帮EB了!

气死咱们这帮EB了!# EB23 - 劳工卡

s*l2012-01-06 08:01

1 楼

实在没想出啥好的解法，来请假大侠们一下。。
Three allowed operations: delete a character, insert a character, replace a
character.
Now given two words - word1 and word2 - find
the minimum number of steps required to convert word1 to word2

H*i2012-01-06 08:01

2 楼

大家不要忘了研究二月新VB里面那段关于visa availability的论述，凹奔特别强调了这一点。
你知道多少美国人不交税？
咱们年年交那么多税，一年的税都够这些人用来做downpayment买一个小房子了.
却不如这些不交税的寄生虫活得自在。
...
...
...
...
...
...
48% of Americans don't pay ANY income tax at all!
http://crooksandliars.com/karoli/true-or-false-over-50-do-not-p

z*y2012-01-06 08:01

3 楼

这个是Dynamic Programming
自己想还是挺难想的
搜一下 Dynamic Programming Edit Distance

p*a2012-01-06 08:01

4 楼

spt

d*82012-01-06 08:01

5 楼

在Converting的过程中要不要保持这个word还是个词典中的单词？
如果是那样的话，好像只有对相差一个Char的单词网络中做BFS
如果要求Operations最少的话，比如insertion, replacement, deletion都有各自
的Penalty的话，就是sequence alignment，DP就可以了吧。

a

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

: 实在没想出啥好的解法，来请假大侠们一下。。
: Three allowed operations: delete a character, insert a character, replace a
: character.
: Now given two words - word1 and word2 - find
: the minimum number of steps required to convert word1 to word2

l*o2012-01-06 08:01

6 楼

拿到绿卡了，咱也办公司，避税。

n*e2012-01-06 08:01

7 楼

classic Dynamic Programming problem
you may refer the following link:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/
BTW: is this in on-site interview or phone interview?

a

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

d*u2012-01-06 08:01

8 楼

心态放好，实在放不好就和内地的比吧。

g*y2012-01-06 08:01

9 楼

这个是算法课动态规划那部分比较简单的作业题吧

replace a

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

a*r2012-01-06 08:01

10 楼

挣得真多

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

: 大家不要忘了研究二月新VB里面那段关于visa availability的论述，凹奔特别强调了这一点。
: 你知道多少美国人不交税？
: 咱们年年交那么多税，一年的税都够这些人用来做downpayment买一个小房子了.
: 却不如这些不交税的寄生虫活得自在。
: ...
: ...
: ...
: ...
: ...
: ...