又听了两遍萤火虫 - 未名空间MITBBS历史存档

b*22015-02-28 08:02

1 楼

４个interviewer 有２个印度人. 其中一个出了一道题:
string A and string B, convert string A to string B with at most one
deletion and one insertion.
事后觉得其间被误导了。按理说Google中印度人也不是很多,来面人是不是volunteered.
祝好运.

e*t2015-02-28 08:02

2 楼

太棒了
谁把歌词记下来

TN2015-02-28 08:02

3 楼

cmft//

volunteered.

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

: ４个interviewer 有２个印度人. 其中一个出了一道题:
: string A and string B, convert string A to string B with at most one
: deletion and one insertion.
: 事后觉得其间被误导了。按理说Google中印度人也不是很多,来面人是不是volunteered.
: 祝好运.

t*a2015-02-28 08:02

4 楼

我觉得是你听漏了，我瞧着题目应该是 -
generate a minimal set of steps to convert string A to string B, you
can use at most one deletion or one insertion (or replacement) in
each step.

volunteered.

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

: ４个interviewer 有２个印度人. 其中一个出了一道题:
: string A and string B, convert string A to string B with at most one
: deletion and one insertion.
: 事后觉得其间被误导了。按理说Google中印度人也不是很多,来面人是不是volunteered.
: 祝好运.

z*92015-02-28 08:02

5 楼

what do you mean for converting string A to string B? give an example,
please?

a*n2015-02-28 08:02

6 楼

我之前面试也碰到印度人讲题目不讲清楚
然后过程中就是觉得自己很牛的态度，只说no,no,no
完了最后才发现他要问的东西很简单
不知道是他的态度问题还是他的语言表达问题或者是我的理解能力问题。。。

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

: 我觉得是你听漏了，我瞧着题目应该是 -
: generate a minimal set of steps to convert string A to string B, you
: can use at most one deletion or one insertion (or replacement) in
: each step.
:
: volunteered.

t*a2015-02-28 08:02

7 楼

比如 ABC -> BZ 如果只允许增减，不允许替换的话最少需要三步
ABC -> BC -> B -> BZ
如果允许增减和替换的话最少需要两步
ABC -> BC -> BZ
瞎猜的，觉得这样问可能更像是一道编程题

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

: what do you mean for converting string A to string B? give an example,
: please?

m*i2015-02-28 08:02

8 楼

Google is infested with 三儿。

p*u2015-02-28 08:02

9 楼

我理解的意思是：
找出string A和string B的公共子串string C，然后把A - C的delete，然后把B - C的
insert。

volunteered.

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

: ４个interviewer 有２个印度人. 其中一个出了一道题:
: string A and string B, convert string A to string B with at most one
: deletion and one insertion.
: 事后觉得其间被误导了。按理说Google中印度人也不是很多,来面人是不是volunteered.
: 祝好运.

v*k2015-02-28 08:02

10 楼

one edit distance

g*n2015-02-28 08:02

11 楼

看看这个办法行不行：
先把A和B两个字符串相同的prefix和suffix去掉，因为相同的前缀、后缀不影响答案。
然后需要做
的就是要么在A'的左端insert，右端delete；要么在A'的左端delete，右端insert。尝
试2次，就
可以得到解。
举例：
str B：ABCDE
case 1-
str A：ACDEF
去掉前后缀后，A'为：CDEF，B'为BCDE,比较可知在A'左端insert，右端delete即可。
case 2-
str A:BFCDE
去掉前后缀后，A'为：BF，B'为:AB,比较可知在A'左端insert，右端delete即可。
case 3-
str A:XABCE
去掉前后缀后，A'为：XABC，B'为:ABCD,比较可知在A'左端delete，右端insert即可。
大家看看有没有返利。

volunteered.

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

: ４个interviewer 有２个印度人. 其中一个出了一道题:
: string A and string B, convert string A to string B with at most one
: deletion and one insertion.
: 事后觉得其间被误导了。按理说Google中印度人也不是很多,来面人是不是volunteered.
: 祝好运.

s*n2015-02-28 08:02

12 楼

Levenshtein edit distance
See details: http://en.wikipedia.org/wiki/Levenshtein_distance

volunteered.

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

: ４个interviewer 有２个印度人. 其中一个出了一道题:
: string A and string B, convert string A to string B with at most one
: deletion and one insertion.
: 事后觉得其间被误导了。按理说Google中印度人也不是很多,来面人是不是volunteered.
: 祝好运.

h*62015-02-28 08:02

13 楼

我记得CLRS那本书DP那章也有的，叫作edit distance，甚至比这道题还复杂一些。

I*A2015-02-28 08:02

14 楼

pat pat
理解你。。

volunteered.

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

: ４个interviewer 有２个印度人. 其中一个出了一道题:
: string A and string B, convert string A to string B with at most one
: deletion and one insertion.
: 事后觉得其间被误导了。按理说Google中印度人也不是很多,来面人是不是volunteered.
: 祝好运.

t*a2015-02-28 08:02

15 楼

classic DP problem.
dist(A[1:n], B[1:m]) = minimal (
dist(A[1:n-1], B[1:m]) + 1,
dist(A[1:n], B[1:m-1] + 1,
dist(A[1:n-1], B[1:m-1]) if A[n]==B[m],
dist(A[1:n-1], B[1:m-1]) + 1 if A[n]!=B[m]
)
the complexity is O(n*m)