征GG - 未名空间MITBBS历史存档

g*s2011-01-20 08:01

1 楼

1. word edit distance.
i know it's dp. but what are the legal edit moves?
say, "abcdefg" -> "gabcdef", the distance is 2 or not?
if it's allowed to delete/insert @ any pos, we just delete @ tail and
insert @ head. but the dp recursion definition seems not to cover this
case.
2. longest palindrome substring.
O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
give a clear description of this solution?

m*c2011-01-20 08:01

2 楼

【以下文字转载自 Sex 讨论区】
发信人: laday (laday), 信区: Sex
标题: 征GG
关键字: AZNK
发信站: BBS 未名空间站 (Thu Jan 20 20:22:12 2011, 美东)
小女子23，聪慧秀丽。奈何近来拮据，想找个大叔或者大哥包养我一段。
我在美西部。

r*e2011-01-20 08:01

3 楼

1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
deletion and the addtion are counted as 2 edits, not a single one
2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
is a special terminator for txt1 and `#' is a special terminator for txt2.
The longest common substring is indicated by the deepest fork node that has
both `$...' and `...#' (no $) beneath it.
The longest palindrome of txt[1..n] can be found in O(n) time, by building
the suffix tree for txt$reverse(txt)#
see http://www.allisons.org/ll/AlgDS/Tree/Suffix/

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

: 1. word edit distance.
: i know it's dp. but what are the legal edit moves?
: say, "abcdefg" -> "gabcdef", the distance is 2 or not?
: if it's allowed to delete/insert @ any pos, we just delete @ tail and
: insert @ head. but the dp recursion definition seems not to cover this
: case.
: 2. longest palindrome substring.
: O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
: give a clear description of this solution?

c*o2011-01-20 08:01

4 楼

价钱几何？

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

: 【以下文字转载自 Sex 讨论区】
: 发信人: laday (laday), 信区: Sex
: 标题: 征GG
: 关键字: AZNK
: 发信站: BBS 未名空间站 (Thu Jan 20 20:22:12 2011, 美东)
: 小女子23，聪慧秀丽。奈何近来拮据，想找个大叔或者大哥包养我一段。
: 我在美西部。

g*s2011-01-20 08:01

5 楼

then how to build the dp table?
`$'
txt2.
has
building

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

: 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
: deletion and the addtion are counted as 2 edits, not a single one
: 2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
: is a special terminator for txt1 and `#' is a special terminator for txt2.
: The longest common substring is indicated by the deepest fork node that has
: both `$...' and `...#' (no $) beneath it.
: The longest palindrome of txt[1..n] can be found in O(n) time, by building
: the suffix tree for txt$reverse(txt)#
: see http://www.allisons.org/ll/AlgDS/Tree/Suffix/

x*s2011-01-20 08:01

6 楼

老大你要包养啊？

b*r2011-01-20 08:01

7 楼

`$'
txt2.
has
building
for the case:
abcdxyzdcba
What's the longest palindrome?, the longest common string for txt and
reverse(txt) is abcd, but it's not palindrome

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

: 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
: deletion and the addtion are counted as 2 edits, not a single one
: 2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
: is a special terminator for txt1 and `#' is a special terminator for txt2.
: The longest common substring is indicated by the deepest fork node that has
: both `$...' and `...#' (no $) beneath it.
: The longest palindrome of txt[1..n] can be found in O(n) time, by building
: the suffix tree for txt$reverse(txt)#
: see http://www.allisons.org/ll/AlgDS/Tree/Suffix/

c*o2011-01-20 08:01

8 楼

了解一下市场。

老大你要包养啊？

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

: 老大你要包养啊？

g*e2011-01-20 08:01

9 楼

第一题上班没空仔细看，第二题，看这个link，俺搞了一个星期才写出完整的代码
http://blog.csdn.net/g9yuayon/archive/2008/06/21/2574781.aspx

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

: 1. word edit distance.
: i know it's dp. but what are the legal edit moves?
: say, "abcdefg" -> "gabcdef", the distance is 2 or not?
: if it's allowed to delete/insert @ any pos, we just delete @ tail and
: insert @ head. but the dp recursion definition seems not to cover this
: case.
: 2. longest palindrome substring.
: O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
: give a clear description of this solution?

x*s2011-01-20 08:01

10 楼

老大，我在你地盘上post了一条，你帮我照着点

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

: 了解一下市场。
:
: 老大你要包养啊？

r*e2011-01-20 08:01

11 楼

http://en.wikipedia.org/wiki/Levenshtein_distance
the pseudo code listed on the page works for ur case

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

:
: then how to build the dp table?
: `$'
: txt2.
: has
: building

h*12011-01-20 08:01

12 楼

第二题能写出N^2 的算法就可以了吧。至于那个N的算法，我觉得知道就可以了。要真
考那个Ukkonen的suffix tree 算法，那真是太疯狂了。

r*e2011-01-20 08:01

13 楼

the longest common string of txt and reverse(txt) is not necessarily the
longest palindrome (I didn't say that in my last post)
we still need to check the positions
the length of the common string plus the lengths of the portions before $/#
in the two child nodes should be equal to strlen(txt).

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

:
: `$'
: txt2.
: has
: building
: for the case:
: abcdxyzdcba
: What's the longest palindrome?, the longest common string for txt and
: reverse(txt) is abcd, but it's not palindrome

s*y2011-01-20 08:01

14 楼

同问，suffix tree和trie的要当场写吗？

g*e2011-01-20 08:01

15 楼

面试的人没几个知道suffix tree和trie的
某投行的一个哥们还问我两遍我trie是不是拼错了，应该是tree

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

: 同问，suffix tree和trie的要当场写吗？

g*s2011-01-20 08:01

16 楼

i think i missed this one:
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required

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

: http://en.wikipedia.org/wiki/Levenshtein_distance
: the pseudo code listed on the page works for ur case

s*y2011-01-20 08:01

17 楼

那就好，还以为自己太弱了，同事说他phd的时候就把trie用硬件语言写进FPGA里面做
routing table look up。

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

: 面试的人没几个知道suffix tree和trie的
: 某投行的一个哥们还问我两遍我trie是不是拼错了，应该是tree

g*e2011-01-20 08:01

18 楼

某大牛告诉我，很多时候坐你对面面试你的人都不如你。 take it easy
这样想我面试的时候就轻松多了，呵呵

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

: 那就好，还以为自己太弱了，同事说他phd的时候就把trie用硬件语言写进FPGA里面做
: routing table look up。

g*s2011-01-20 08:01

19 楼

i don't care if the interviewer is better than me or not. but i do care if
they correctly understand and respond my points.

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

: 某大牛告诉我，很多时候坐你对面面试你的人都不如你。 take it easy
: 这样想我面试的时候就轻松多了，呵呵

g*e2011-01-20 08:01

20 楼

care or not, there is nothing you can do about it. My point is that we don't
have to bash ourselves if we don't know all the algorithms or data
structures or can't solve all the problems in this forum. Confidence helps a
lot in an interview.

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

: i don't care if the interviewer is better than me or not. but i do care if
: they correctly understand and respond my points.

g*s2011-01-20 08:01

21 楼

1. word edit distance.
i know it's dp. but what are the legal edit moves?
say, "abcdefg" -> "gabcdef", the distance is 2 or not?
if it's allowed to delete/insert @ any pos, we just delete @ tail and
insert @ head. but the dp recursion definition seems not to cover this
case.
2. longest palindrome substring.
O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
give a clear description of this solution?

r*e2011-01-20 08:01

22 楼

1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
deletion and the addtion are counted as 2 edits, not a single one
2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
is a special terminator for txt1 and `#' is a special terminator for txt2.
The longest common substring is indicated by the deepest fork node that has
both `$...' and `...#' (no $) beneath it.
The longest palindrome of txt[1..n] can be found in O(n) time, by building
the suffix tree for txt$reverse(txt)#
see http://www.allisons.org/ll/AlgDS/Tree/Suffix/

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

: 1. word edit distance.
: i know it's dp. but what are the legal edit moves?
: say, "abcdefg" -> "gabcdef", the distance is 2 or not?
: if it's allowed to delete/insert @ any pos, we just delete @ tail and
: insert @ head. but the dp recursion definition seems not to cover this
: case.
: 2. longest palindrome substring.
: O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
: give a clear description of this solution?

g*s2011-01-20 08:01

23 楼

then how to build the dp table?
`$'
txt2.
has
building

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

: 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
: deletion and the addtion are counted as 2 edits, not a single one
: 2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
: is a special terminator for txt1 and `#' is a special terminator for txt2.
: The longest common substring is indicated by the deepest fork node that has
: both `$...' and `...#' (no $) beneath it.
: The longest palindrome of txt[1..n] can be found in O(n) time, by building
: the suffix tree for txt$reverse(txt)#
: see http://www.allisons.org/ll/AlgDS/Tree/Suffix/

b*r2011-01-20 08:01

24 楼

`$'
txt2.
has
building
for the case:
abcdxyzdcba
What's the longest palindrome?, the longest common string for txt and
reverse(txt) is abcd, but it's not palindrome

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

: 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
: deletion and the addtion are counted as 2 edits, not a single one
: 2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
: is a special terminator for txt1 and `#' is a special terminator for txt2.
: The longest common substring is indicated by the deepest fork node that has
: both `$...' and `...#' (no $) beneath it.
: The longest palindrome of txt[1..n] can be found in O(n) time, by building
: the suffix tree for txt$reverse(txt)#
: see http://www.allisons.org/ll/AlgDS/Tree/Suffix/

g*e2011-01-20 08:01

25 楼

第一题上班没空仔细看，第二题，看这个link，俺搞了一个星期才写出完整的代码
http://blog.csdn.net/g9yuayon/archive/2008/06/21/2574781.aspx

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

: 1. word edit distance.
: i know it's dp. but what are the legal edit moves?
: say, "abcdefg" -> "gabcdef", the distance is 2 or not?
: if it's allowed to delete/insert @ any pos, we just delete @ tail and
: insert @ head. but the dp recursion definition seems not to cover this
: case.
: 2. longest palindrome substring.
: O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
: give a clear description of this solution?

r*e2011-01-20 08:01

26 楼

http://en.wikipedia.org/wiki/Levenshtein_distance
the pseudo code listed on the page works for ur case

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

:
: then how to build the dp table?
: `$'
: txt2.
: has
: building

h*12011-01-20 08:01

27 楼

第二题能写出N^2 的算法就可以了吧。至于那个N的算法，我觉得知道就可以了。要真
考那个Ukkonen的suffix tree 算法，那真是太疯狂了。

r*e2011-01-20 08:01

28 楼

the longest common string of txt and reverse(txt) is not necessarily the
longest palindrome (I didn't say that in my last post)
we still need to check the positions
the length of the common string plus the lengths of the portions before $/#
in the two child nodes should be equal to strlen(txt).

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

:
: `$'
: txt2.
: has
: building
: for the case:
: abcdxyzdcba
: What's the longest palindrome?, the longest common string for txt and
: reverse(txt) is abcd, but it's not palindrome

s*y2011-01-20 08:01

29 楼

同问，suffix tree和trie的要当场写吗？

g*e2011-01-20 08:01

30 楼

面试的人没几个知道suffix tree和trie的
某投行的一个哥们还问我两遍我trie是不是拼错了，应该是tree

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

: 同问，suffix tree和trie的要当场写吗？

g*s2011-01-20 08:01

31 楼

i think i missed this one:
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required

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

: http://en.wikipedia.org/wiki/Levenshtein_distance
: the pseudo code listed on the page works for ur case

s*y2011-01-20 08:01

32 楼

那就好，还以为自己太弱了，同事说他phd的时候就把trie用硬件语言写进FPGA里面做
routing table look up。

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

: 面试的人没几个知道suffix tree和trie的
: 某投行的一个哥们还问我两遍我trie是不是拼错了，应该是tree

g*e2011-01-20 08:01

33 楼

某大牛告诉我，很多时候坐你对面面试你的人都不如你。 take it easy
这样想我面试的时候就轻松多了，呵呵

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

: 那就好，还以为自己太弱了，同事说他phd的时候就把trie用硬件语言写进FPGA里面做
: routing table look up。

g*s2011-01-20 08:01

34 楼

i don't care if the interviewer is better than me or not. but i do care if
they correctly understand and respond my points.

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

: 某大牛告诉我，很多时候坐你对面面试你的人都不如你。 take it easy
: 这样想我面试的时候就轻松多了，呵呵

g*e2011-01-20 08:01

35 楼

care or not, there is nothing you can do about it. My point is that we don't
have to bash ourselves if we don't know all the algorithms or data
structures or can't solve all the problems in this forum. Confidence helps a
lot in an interview.

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

: i don't care if the interviewer is better than me or not. but i do care if
: they correctly understand and respond my points.

b*g2011-01-20 08:01

36 楼

working on more problems is the way to be confidence.

't
a

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

: care or not, there is nothing you can do about it. My point is that we don't
: have to bash ourselves if we don't know all the algorithms or data
: structures or can't solve all the problems in this forum. Confidence helps a
: lot in an interview.