你们有sygic自己偷偷启动的吗？ - 未名空间MITBBS历史存档

你们有sygic自己偷偷启动的吗？# PDA - 掌中宝

z*c2013-03-05 08:03

1 楼

F的：
1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
2 单链表倒序输出
3. Dutch Flag Problem
4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
中出现且仅出现一次，比如两个人，
初始 {}
move(1): {1}
move{2}: {1, 2}
move{1}: {2}
G的：
1. BST求某个节点的next节点，有parent指针
2. 两个BST，求他们merge后的BST
3. 一个硬盘上全是文件，求把同样文件不同文件名去重怎么做
4. 一堆数求最大1000个
5. sleep sort，跟我讨论os kernel进程调度的实现和复杂度
6. 拓扑排序
7. scramble string，对一个string，比如tiger，可以随便找一个partition tree
tiger
/ \
ti ger
/ \ / \
t i g er
/ \
e r
你可以选择在每个非叶子节点翻转或者不翻转两个儿子的顺序，比如可以变成
itreg
/ \
it reg
/ \ / \
t i g re
/ \
e r
那么就称itreg是可以通过tiger串scramble得到的
给s1, s2，求是否能找到s1一颗partition tree和翻转方案，使得得到s2

a*s2013-03-05 08:03

2 楼

怎么算什么时候能付清mortgage，如果每年多放两个月payment的话
哪有这样的软件呀。

w*u2013-03-05 08:03

3 楼

看看电池里面，sygic竟然用了2%的电池。这段时间，不仅没有用过sygic，连location
service都关了，谁把它调起来的？

l*82013-03-05 08:03

4 楼

赞！

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

s*l2013-03-05 08:03

5 楼

google一下就有很多mortgage calculator:
http://www.bankrate.com/calculators/mortgages/mortgage-calculat

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

: 怎么算什么时候能付清mortgage，如果每年多放两个月payment的话
: 哪有这样的软件呀。

a92013-03-05 08:03

6 楼

有自动启动的服务吧。

location

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

: 看看电池里面，sygic竟然用了2%的电池。这段时间，不仅没有用过sygic，连location
: service都关了，谁把它调起来的？

l*82013-03-05 08:03

7 楼

BTree 指的是binary tree还是B-tree?

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

p*y2013-03-05 08:03

8 楼

不过，具体这种算法的不多。大部分是每月固定多还本金的算法。
可以按1年pay 14个月来估算。

w*u2013-03-05 08:03

9 楼

background data sync也关了。

z*c2013-03-05 08:03

10 楼

B-tree我就跪了。。

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

: BTree 指的是binary tree还是B-tree?

s*l2013-03-05 08:03

11 楼

下面这个calculator就可以呀，它有几种extra payment的选择，比如每月多付、每年
多付或者一次性多付:
http://www.bankrate.com/calculators/mortgages/mortgage-calculat

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

: 不过，具体这种算法的不多。大部分是每月固定多还本金的算法。
: 可以按1年pay 14个月来估算。

a92013-03-05 08:03

12 楼

so what?

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

: background data sync也关了。

A*l2013-03-05 08:03

13 楼

赞！

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

d*22013-03-05 08:03

14 楼

an easy way to estimate.
你每个月的利息是从你剩余的principle算出来的。
所以简单计算。
譬如你下个月帐单里 $1000是principle, 其他是利息。
那么你追加$2000, 差不多就减少两个月的payment.
相当于你从2个月以后的time table开始付你的mortgage.

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

: 怎么算什么时候能付清mortgage，如果每年多放两个月payment的话
: 哪有这样的软件呀。

w*u2013-03-05 08:03

15 楼

奇怪的是以前没有这个问题的，以前达到过一晚上还是99%的水平。

【在 a9 的大作中提到】

: so what?

l*82013-03-05 08:03

16 楼

呵呵，我觉得也是binary tree。
另， google第七题有些难啊。我只想到一个递归解法，时间复杂度有些高啊。有DP
解法吗？

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

: B-tree我就跪了。。

d*22013-03-05 08:03

17 楼

所以还是我上次跟你说的。
1. 你决定提早还清mortgage作为你的投资目标
2. 你手头有一部分闲钱，那么越早投入进去越好。一次性投入你现在能动用闲钱的
comfortable比例。至于孩子和其他花销，以后可以用equity loan和攒钱。
不需要把追加的principle打散到每个月， lump sum就可以了。关键是你要make ur
mind.
3. once again. 追加principle不算很好的理财选择。

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

: 怎么算什么时候能付清mortgage，如果每年多放两个月payment的话
: 哪有这样的软件呀。

d*32013-03-05 08:03

18 楼

有可能是自动更新，no big deal。。。

g*y2013-03-05 08:03

19 楼

翻转树那个没见过，直接递归可以做；提高效率可以用DP保存中间计算结果。
不知道还有什么更好更直接的办法没有。

z*c2013-03-05 08:03

20 楼

F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
则如果存在k，使得要么
1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
F[l1 + k][u1][l2 + k][u2]
2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
F[l1 + k][u1][l2][l2 + k - 1]
两者有一个真，则F[l1][u1][l2][u2]为真
因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3
决策为o(n), 总复杂度o(N^4)

DP

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

: 呵呵，我觉得也是binary tree。
: 另， google第七题有些难啊。我只想到一个递归解法，时间复杂度有些高啊。有DP
: 解法吗？

n*o2013-03-05 08:03

21 楼

room move 这个的函数原型是什么？

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

z*c2013-03-05 08:03

22 楼

void move (int person)

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

: room move 这个的函数原型是什么？

g*y2013-03-05 08:03

23 楼

最后决定去哪家了？

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: void move (int person)

m*s2013-03-05 08:03

24 楼

Zan

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

C*r2013-03-05 08:03

25 楼

赞！

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

z*c2013-03-05 08:03

26 楼

今晚Google HR说跟我谈谈。。。

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

: 最后决定去哪家了？
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

g*y2013-03-05 08:03

27 楼

呵呵，要给个大的，把人才抢过来。G，F分别是哪个组？

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 今晚Google HR说跟我谈谈。。。

z*c2013-03-05 08:03

28 楼

没说，说招进去再双向选择。。。

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

: 呵呵，要给个大的，把人才抢过来。G，F分别是哪个组？
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

s*n2013-03-05 08:03

29 楼

第5题move是gray code啊，没预先看过想不出来吧

O*i2013-03-05 08:03

30 楼

是最后一轮的压轴题目么？面试官是老中还是老印？
面试被考DP是运气不好，有没有给提示？
如果没有DP的语感，真的不容易一下子想到。
感觉思路和那个DP找最长回文有点相似。

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

: F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
: 则如果存在k，使得要么
: 1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
: F[l1 + k][u1][l2 + k][u2]
: 2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
: F[l1 + k][u1][l2][l2 + k - 1]
: 两者有一个真，则F[l1][u1][l2][u2]为真
: 因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3
: 决策为o(n), 总复杂度o(N^4)
:

h*l2013-03-05 08:03

31 楼

partition 是binary的话
为什么不是这样：
一定从t开始，然后第一个长度从1到len(s1)
第二个分区是确定的，如果第一个确定的话
这样第一个分区有n种
判断同时翻转两个区间看能不能得到s2，翻转复杂度n，一共n^2
还是我题意没理解对？

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

: F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
: 则如果存在k，使得要么
: 1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
: F[l1 + k][u1][l2 + k][u2]
: 2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
: F[l1 + k][u1][l2][l2 + k - 1]
: 两者有一个真，则F[l1][u1][l2][u2]为真
: 因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3
: 决策为o(n), 总复杂度o(N^4)
:

O*i2013-03-05 08:03

32 楼

G的：
3. 一个硬盘上全是文件，求把同样文件不同文件名去重怎么做
是否要hash一下比如用MD5?

O*i2013-03-05 08:03

33 楼

两个BST，求他们merge后的BST
这题有什么trick? merge结果是唯一的么？
总不是trival的遍历一棵，依次插入到另一棵吧？

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

s*n2013-03-05 08:03

34 楼

递归非DP做法
bool isScramble(char* str1, char* str2, int length) {
if (length==1) return *str1 == *str2;
for (int i=1; iif (isScramble(str1, str2+(length-i), i)
&& isScramble(str1+i, str2, length-i))
return true;
if (isScramble(str1, str2, i)
&& isScramble(str1+i, str2+i, length-i))
return true;
}
return false;
}
递归DP做法
class Solution {
char* str1;
char* str2;
int m;
int m2;
int m3;
int* DP;
#define dp(i,j,k) DP[m2 * (i) + m * (j) + (k) ]
public:
Solution(char* s1, char *s2) {
assert( s1 && s2 );
str1 = s1; str2 = s2;
m = strlen(str1);
assert(m && strlen(str2)==m);
m2 = m*m;
m3 = m2*m
DP = new int[m3];
for (int i=0; i}
bool isScramble() {
return isScramble(0, 0, m);
}
private:
bool isScramble(int pos1, int pos2, int length) {
if (length==1) return str1[pos1] == str2[pos2];
if (dp(pos1, pos2, length-1)!=-1) return dp(pos1, pos2, length-1);
for (int i=1; iif (isScramble(pos1, pos2+(length-i), i) && isScramble(pos1+i, pos2, length-i)
|| isScramble(pos1, pos2, i) && isScramble(pos1+i, pos2+i, length-i)) {
dp(pos1, pos2, length-1) = 1;
return true;
}
}
dp(pos1, pos2, length-1) = 0;
return false;
}
}

O*i2013-03-05 08:03

35 楼

if (isScramble(str1+i, str2+(length-i), i)) return true;
这里好像不对，应该有几种情形，象LZ那样的DP转移方程

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

: 递归非DP做法
: bool isScramble(char* str1, char* str2, int length) {
: if (length==1) return *str1 == *str2;
: for (int i=1; i: if (isScramble(str1, str2+(length-i), i)
: && isScramble(str1+i, str2, length-i))
: return true;
: if (isScramble(str1, str2, i)
: && isScramble(str1+i, str2+i, length-i))
: return true;

g*y2013-03-05 08:03

36 楼

对，这里应该嵌套递归。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: if (isScramble(str1+i, str2+(length-i), i)) return true;
: 这里好像不对，应该有几种情形，象LZ那样的DP转移方程

s*n2013-03-05 08:03

37 楼

不明白啥叫嵌套地跪，已经是地跪了

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

: 对，这里应该嵌套递归。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

t*72013-03-05 08:03

38 楼

不是吧...要考虑每个子集和只出现一次啊,不是单纯的找出所有的SUBSETS啊

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

: 第5题move是gray code啊，没预先看过想不出来吧

s*n2013-03-05 08:03

39 楼

gray code的特性：next每次只反转一个bit
0 ~ 2^n覆盖了长度为n集合的powerset

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

: 不是吧...要考虑每个子集和只出现一次啊,不是单纯的找出所有的SUBSETS啊

g*y2013-03-05 08:03

40 楼

分的两个子串满足scramble就可以

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 不明白啥叫嵌套地跪，已经是地跪了

s*n2013-03-05 08:03

41 楼

改了一下，这样对了吧？

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

: 分的两个子串满足scramble就可以
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

s*n2013-03-05 08:03

42 楼

改了好几遍。。。

c*p2013-03-05 08:03

43 楼

G的3,4是高频题。
第4题如果用heap解，是min-heap，不是max-heap
如果用quick-sort中的partition算法的话，会问到复杂度，如果输入是如stream，如
何处理。

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

O*i2013-03-05 08:03

44 楼

if (isScramble(str1, str2 + (length - i), i)
&& isScramble(str1 + i, str2, length - i))
return true;
if (isScramble(str1, str2, i)
&& isScramble(str1 + i, str2 + i, length - i))
return true;

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

: 改了一下，这样对了吧？

O*i2013-03-05 08:03

45 楼

和你最后版本一样。
LZ的DP方程也是类似思路。

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

: if (isScramble(str1, str2 + (length - i), i)
: && isScramble(str1 + i, str2, length - i))
: return true;
: if (isScramble(str1, str2, i)
: && isScramble(str1 + i, str2 + i, length - i))
: return true;

s*n2013-03-05 08:03

46 楼

和我改过的一致

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

: 和你最后版本一样。
: LZ的DP方程也是类似思路。

s*n2013-03-05 08:03

47 楼

sleep sort那题，用的红黑树吧？把wakeup time排序。
http://kernel.org/doc/Documentation/rbtree.txt

z*c2013-03-05 08:03

48 楼

恩，他跟我讨论了什么hash比较好，我说了比如k base digit modular或者MD5

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

: G的：
: 3. 一个硬盘上全是文件，求把同样文件不同文件名去重怎么做
: 是否要hash一下比如用MD5?

z*c2013-03-05 08:03

49 楼

他问我sleep sort复杂度你觉得是o(n)还是o(nlogn)，我说O(n)，他说nlogn，因为进
程调度要用个堆。。然后我跟他argu说那你这个是klogn，k是时间片的个数，然后就吵
。。。
这个题他出出来我觉得是好玩的，因为他说他前两天刚看个blog看到的，问问我有什么
想法。。

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

: sleep sort那题，用的红黑树吧？把wakeup time排序。
: http://kernel.org/doc/Documentation/rbtree.txt

z*c2013-03-05 08:03

50 楼

我当时找规律就出来了。。
n = 1, 1
n = 2, 1 2 1
n = 3, 1 2 1 3 1 2 1
n = 4, 你懂的。。

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

: gray code的特性：next每次只反转一个bit
: 0 ~ 2^n覆盖了长度为n集合的powerset

t*e2013-03-05 08:03

51 楼

赞! 楼主太强大了!

z*c2013-03-05 08:03

52 楼

google比fb:
bonus rate多5%
relocation 多给5K
RSU 市值多12K
还提了个什么US Government什么项目，Google帮你存钱进去啥的，听不懂。。。

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

: 呵呵，要给个大的，把人才抢过来。G，F分别是哪个组？
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

l*82013-03-05 08:03

53 楼

what is sleep sort?

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

: 他问我sleep sort复杂度你觉得是o(n)还是o(nlogn)，我说O(n)，他说nlogn，因为进
: 程调度要用个堆。。然后我跟他argu说那你这个是klogn，k是时间片的个数，然后就吵
: 。。。
: 这个题他出出来我觉得是好玩的，因为他说他前两天刚看个blog看到的，问问我有什么
: 想法。。

z*c2013-03-05 08:03

54 楼

这个他说不好，最后那个方法好雷。。。。
in order traversal。。得到两个list,merge list, reconstruct from the list
我说这方法跟BST有毛关系啊，硬生生把merge sorted list和construct balanced bst
from sorted list 放到一起考

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

: 两个BST，求他们merge后的BST
: 这题有什么trick? merge结果是唯一的么？
: 总不是trival的遍历一棵，依次插入到另一棵吧？

v*u2013-03-05 08:03

55 楼

a different idea
if it's scramble, there must be at least two chars that are still adjacent
to each other after scramble, reduce them to one character since they can be
within one node. Keep reducing until not able to reduce anymore or string
length is 1 (successful)
example:
itreg and tiger has it and ti, which means i and t could be within one node,
we now can delete i (or t).
it turns to treg tger, now e and g are eligible to reduce
tr(eg), t(ge)r --> tre, ter --> tr, tr --> t, t --> MATCH.
complexity is O(N3) if using linkedlist to store strings because delete is O
(1).
negative example
abcd and cadb don't have any two characters that are adjacent in original
and target string, so it's NOT scramble.

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

: 递归非DP做法
: bool isScramble(char* str1, char* str2, int length) {
: if (length==1) return *str1 == *str2;
: for (int i=1; i: if (isScramble(str1, str2+(length-i), i)
: && isScramble(str1+i, str2, length-i))
: return true;
: if (isScramble(str1, str2, i)
: && isScramble(str1+i, str2+i, length-i))
: return true;

z*c2013-03-05 08:03

56 楼

Freshing idea!
Conclusively, This is a down to top approach but DP is top to down approach.
Nice!!

be
node,

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

: a different idea
: if it's scramble, there must be at least two chars that are still adjacent
: to each other after scramble, reduce them to one character since they can be
: within one node. Keep reducing until not able to reduce anymore or string
: length is 1 (successful)
: example:
: itreg and tiger has it and ti, which means i and t could be within one node,
: we now can delete i (or t).
: it turns to treg tger, now e and g are eligible to reduce
: tr(eg), t(ge)r --> tre, ter --> tr, tr --> t, t --> MATCH.

O*i2013-03-05 08:03

57 楼

是晕了，一道题瞬间变为三道题
1) 遍历二叉树，说不定还要考非递归的方法
2）Merge two sorted list
3) Construct BST from sorted list

bst

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

: 这个他说不好，最后那个方法好雷。。。。
: in order traversal。。得到两个list,merge list, reconstruct from the list
: 我说这方法跟BST有毛关系啊，硬生生把merge sorted list和construct balanced bst
: from sorted list 放到一起考

l*82013-03-05 08:03

58 楼

Nice idea!
But what if there are multiple common adjacent characters between two
strings?
Example:
abcdfbxc can be scrambled to fbcdabcd
then we can reduce the two string to:
a(bc)dfbxc
f(bc)dabcd
now we cannot reduce the strings any more.

be
node,

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

: a different idea
: if it's scramble, there must be at least two chars that are still adjacent
: to each other after scramble, reduce them to one character since they can be
: within one node. Keep reducing until not able to reduce anymore or string
: length is 1 (successful)
: example:
: itreg and tiger has it and ti, which means i and t could be within one node,
: we now can delete i (or t).
: it turns to treg tger, now e and g are eligible to reduce
: tr(eg), t(ge)r --> tre, ter --> tr, tr --> t, t --> MATCH.

w*x2013-03-05 08:03

59 楼

问一下那个G最后一题有要求用DP吗?
Merge BST那题有要求写代码吗? 要写代码的话给多长时间, 你写完了吗?
能不能把每个题要求做到的程度说一下...
看起来F的比G的简单不少啊, F的题一扫除了最后一道外都做过.
问一下F/G的面经包括电面的吗, 怎么题目这么少

v*u2013-03-05 08:03

60 楼

When thinking of the algorithm, I assume that there is no duplicated
characters.
Still not sure if it works for du;icated characters, but your case: where
does the x go? and you can still keep reducing the strings.

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

: Nice idea!
: But what if there are multiple common adjacent characters between two
: strings?
: Example:
: abcdfbxc can be scrambled to fbcdabcd
: then we can reduce the two string to:
: a(bc)dfbxc
: f(bc)dabcd
: now we cannot reduce the strings any more.
:

l*82013-03-05 08:03

61 楼

Sorry, example should be:
abcdfbxc can be scrambled to fbcxabcd
then we can reduce the two string to:
a(bc)dfbxc
f(bc)xabcd
Now they cannot be reduced any more.

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

: When thinking of the algorithm, I assume that there is no duplicated
: characters.
: Still not sure if it works for du;icated characters, but your case: where
: does the x go? and you can still keep reducing the strings.

G*e2013-03-05 08:03

62 楼

It seems the bottom-up approach can not handle duplicate character case.

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

: Sorry, example should be:
: abcdfbxc can be scrambled to fbcxabcd
: then we can reduce the two string to:
: a(bc)dfbxc
: f(bc)xabcd
: Now they cannot be reduced any more.

v*u2013-03-05 08:03

63 楼

you're right. the algorith seems to have such limitation. The reason behind
is that they're not reducing for the same node.

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

: Sorry, example should be:
: abcdfbxc can be scrambled to fbcxabcd
: then we can reduce the two string to:
: a(bc)dfbxc
: f(bc)xabcd
: Now they cannot be reduced any more.

O*i2013-03-05 08:03

64 楼

简单不一定能答完美。
这个题怎么做？有什么trick么?
给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串

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

: 问一下那个G最后一题有要求用DP吗?
: Merge BST那题有要求写代码吗? 要写代码的话给多长时间, 你写完了吗?
: 能不能把每个题要求做到的程度说一下...
: 看起来F的比G的简单不少啊, F的题一扫除了最后一道外都做过.
: 问一下F/G的面经包括电面的吗, 怎么题目这么少

w*x2013-03-05 08:03

65 楼

说的没错, 主要是写起来还是有难度.
prefix因该是用二分吧

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

: 简单不一定能答完美。
: 这个题怎么做？有什么trick么?
: 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串

O*i2013-03-05 08:03

66 楼

prefix这题哪里有讨论过么？以前没有见过。

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

:
: 说的没错, 主要是写起来还是有难度.
: prefix因该是用二分吧

D*d2013-03-05 08:03

67 楼

第七题有点意思，我来贡献一个时间复杂度为 o(nlogn), 空间复杂度为 o(n) 的算法
以一个简单的例子说明
S1 = 12345
S2 = 15342
Initialize a public Status[n] = 0;% 0,1: check sign; -1: no need to check
TotalChangeSign = 0
i = 1;
for i = 1:n
Status[S2[i]] = 1;
TotalChangeSign = TotalChangeSign + Num of Status[S2[i]]'s neighbor
different from Status[S2[1]].
if TotalChangeSign == 1; break;
end
if TotalChangeSign == 1
separate substring by their 0/1 sign. call self-recursively with start and
end points of the substring.
else % TotalChangeSign == 0
return false
end

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

L*k2013-03-05 08:03

68 楼

zan!

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

z*c2013-03-05 08:03

69 楼

lower_bound (S, S + n, prefix)
upper_bound (S, S + n, prefix)
我用C++的。。

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

: 简单不一定能答完美。
: 这个题怎么做？有什么trick么?
: 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串

z*c2013-03-05 08:03

70 楼

不知道什么要求。。我直接写的搜索然后优化成DP，他说很好
merge写了，那一场45分钟全部用来搞这个题了。。。。
补充一下电面题把:
F:
1. int strstr (const char *haystack, const char *needle)，要你实现，
bruteforce就行
2. int strstr (const char *haystack[], const char *needle)，意思就是haystack
太长了，然后一个串存不下，变成存个数组里，把他们concatenate 以后就是
haystack，还是一样的要求，要你实现，不能有额外空间
3. 给一组字符串，按anagram分组，输出
G:
1. 找到ll里最后k个节点，把他们放到前面来
2. 那题在板上说过，一个iterator，有next和hasNext，现在要你加个wrapper，使得
支持peek操作
不少了哥。。。我问了那么多人绝对我写的码比他们都多。。

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

: 问一下那个G最后一题有要求用DP吗?
: Merge BST那题有要求写代码吗? 要写代码的话给多长时间, 你写完了吗?
: 能不能把每个题要求做到的程度说一下...
: 看起来F的比G的简单不少啊, F的题一扫除了最后一道外都做过.
: 问一下F/G的面经包括电面的吗, 怎么题目这么少

w*x2013-03-05 08:03

71 楼

haystack
哈哈, 谢谢了....

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

: 不知道什么要求。。我直接写的搜索然后优化成DP，他说很好
: merge写了，那一场45分钟全部用来搞这个题了。。。。
: 补充一下电面题把:
: F:
: 1. int strstr (const char *haystack, const char *needle)，要你实现，
: bruteforce就行
: 2. int strstr (const char *haystack[], const char *needle)，意思就是haystack
: 太长了，然后一个串存不下，变成存个数组里，把他们concatenate 以后就是
: haystack，还是一样的要求，要你实现，不能有额外空间
: 3. 给一组字符串，按anagram分组，输出

q*y2013-03-05 08:03

72 楼

赞目标。

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

: partition 是binary的话
: 为什么不是这样：
: 一定从t开始，然后第一个长度从1到len(s1)
: 第二个分区是确定的，如果第一个确定的话
: 这样第一个分区有n种
: 判断同时翻转两个区间看能不能得到s2，翻转复杂度n，一共n^2
: 还是我题意没理解对？

l*82013-03-05 08:03

73 楼

f和g，你都是一轮电面吗？

haystack

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

: 不知道什么要求。。我直接写的搜索然后优化成DP，他说很好
: merge写了，那一场45分钟全部用来搞这个题了。。。。
: 补充一下电面题把:
: F:
: 1. int strstr (const char *haystack, const char *needle)，要你实现，
: bruteforce就行
: 2. int strstr (const char *haystack[], const char *needle)，意思就是haystack
: 太长了，然后一个串存不下，变成存个数组里，把他们concatenate 以后就是
: haystack，还是一样的要求，要你实现，不能有额外空间
: 3. 给一组字符串，按anagram分组，输出

h*e2013-03-05 08:03

74 楼

赞！
- Sleep sort是第一次听到，看了网上的介绍不知道有什么用：
http://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
不过看来是要学习Linux的O(1) scheduler的时候了:
http://www.ibm.com/developerworks/linux/library/l-scheduler/
- 关于Merge 2 BSTs的题目，这里提供了几种解法：
http://www.geeksforgeeks.org/archives/18611
不过我觉得第二种解法也不够巧，感觉就是brute-force的解法。

p*n2013-03-05 08:03

75 楼

直接这样是不对的吧...
貌似应该是先二分找到lower bound；然后在lower bound到n的范围内，再二分找到最
大的以prefix为前缀的串...

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

: lower_bound (S, S + n, prefix)
: upper_bound (S, S + n, prefix)
: 我用C++的。。

w*x2013-03-05 08:03

76 楼

//Print strings with certain prefix in a sorted string array
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2);
void PrintComPrefix(const char* strs[], int n, const char* szPre)
{
assert(strs && szPre && n > 0);
const char* p = szPre;
int nIndex1 = 0;
int nIndex2 = n-1;
while (*p != 0 && nIndex1 >= 0)
{
GetIndex(strs, nIndex1, nIndex2, *p, p-szPre, nIndex1, nIndex2);
p++;
}
if (nIndex1 >= 0 && nIndex2 >= nIndex1)
{
for (int i = nIndex1; i <= nIndex2; i++)
cout<}
else cout<}
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2)
{
if (nBeg < 0 || nEnd < nBeg || nPos < 0)
{
index1 = index2 = -1;
return;
}
//left boundary
int s = nBeg;
int e = nEnd;
index1 = -1;
while (s <= e)
{
int nMid = (s + e)/2;
if (strs[nMid][nPos] == chr && (nMid == nBeg ||
strs[nMid][nPos] != strs[nMid-1][nPos]))
{
index1 = nMid;
break;
}
else if (strs[nMid][nPos] > chr || strs[nMid][nPos] == chr)
e = nMid - 1;
else s = nMid + 1;
}
//right boundary
s = nBeg;
e = nEnd;
index2 = -1;
while (s <= e)
{
int nMid = (s + e)/2;
if (strs[nMid][nPos] == chr && (nMid == nEnd ||
strs[nMid][nPos] != strs[nMid+1][nPos]))
{
index2 = nMid;
break;
}
else if (strs[nMid][nPos] < chr || strs[nMid][nPos] == chr)
s = nMid + 1;
else e = nMid - 1;
}
}

z*c2013-03-05 08:03

77 楼

都是两轮，我有同学F是一轮，Google都是两轮，back to back

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

: f和g，你都是一轮电面吗？
:
: haystack

c*a2013-03-05 08:03

78 楼

mark

z*82013-03-05 08:03

79 楼

peek 操作具体是什么？

haystack

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

: 不知道什么要求。。我直接写的搜索然后优化成DP，他说很好
: merge写了，那一场45分钟全部用来搞这个题了。。。。
: 补充一下电面题把:
: F:
: 1. int strstr (const char *haystack, const char *needle)，要你实现，
: bruteforce就行
: 2. int strstr (const char *haystack[], const char *needle)，意思就是haystack
: 太长了，然后一个串存不下，变成存个数组里，把他们concatenate 以后就是
: haystack，还是一样的要求，要你实现，不能有额外空间
: 3. 给一组字符串，按anagram分组，输出

z*c2013-03-05 08:03

80 楼

http://www.mitbbs.com/article_t0/JobHunting/32078587.html

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

: peek 操作具体是什么？
:
: haystack

k*r2013-03-05 08:03

81 楼

请问楼主，他们问的Dutch Flag Problem有要求是stable sort么？多谢

y*u2013-03-05 08:03

82 楼

这题好难。。。

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

y*u2013-03-05 08:03

83 楼

2. merge 2颗bst是不是第一个问题的后续？
第一个问题隐含inorder traversal
所以merge 2颗bst可以转换成2个linklist的merge 。。。
3. 文件名去重复，难道就用md5/sha1这样的hash?
4. os的调度，太复杂了，以前做个berkeley schedular就爆了

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

m*p2013-03-05 08:03

84 楼

菜鸟求问：
这种onsite，每个题大约多长时间？

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

g*e2013-03-05 08:03

85 楼

move那个函数了格雷码吧，想不起来格雷码怎么生成了。

w*x2013-03-05 08:03

86 楼

为啥时格雷码,我估计去面试的人没几个知道那玩艺,
不就是和next_permutation一个原理的那啥啥啥吗....

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

: move那个函数了格雷码吧，想不起来格雷码怎么生成了。

g*e2013-03-05 08:03

87 楼

每种情形只能出现一次啊
比如
1
12
2
俩种情形转换时不能有其他中间过程吧

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

:
: 为啥时格雷码,我估计去面试的人没几个知道那玩艺,
: 不就是和next_permutation一个原理的那啥啥啥吗....

g*e2013-03-05 08:03

88 楼

学过数字电路的都知道吧一般工科都学过

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

:
: 为啥时格雷码,我估计去面试的人没几个知道那玩艺,
: 不就是和next_permutation一个原理的那啥啥啥吗....

w*x2013-03-05 08:03

89 楼

你这话说得太牵强了, 大一的时候大家都学过泰勒公式呢... just kidding

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

:
: 学过数字电路的都知道吧一般工科都学过

w*x2013-03-05 08:03

90 楼

没说有其他过程啊, 就是next_permutation的思路啊, 根据当前房间的状态计算下一个
状态
12 > 1 所以1 next 就是12
2 > 12 所以12 next就是2

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

:
: 学过数字电路的都知道吧一般工科都学过

g*e2013-03-05 08:03

91 楼

不知道你的next_permutation具体指什么？能给个link吗？是一步走到下一个状态吗？

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

:
: 没说有其他过程啊, 就是next_permutation的思路啊, 根据当前房间的状态计算下一个
: 状态
: 12 > 1 所以1 next 就是12
: 2 > 12 所以12 next就是2

w*x2013-03-05 08:03

92 楼

leetcode上有吧. 思路差不多的应该, 把所有的sub set列出来其实可以排个序, 根据
当前的状态可以知道下一个状态, 可以用bool rec[number of people]来代表状态, 假
如一共3个人, 当前状态是12, 那么把没到最右头的最小位右移,变成13,然后同样逻辑
23, 然后发现都移动到最右边了, 就只有增加位数变3位, 但是保证是3位数里最小的就
是123

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

:
: 不知道你的next_permutation具体指什么？能给个link吗？是一步走到下一个状态吗？

p*22013-03-05 08:03

93 楼

终于看完了。恭喜楼主了。楼主太强大了。

c*p2013-03-05 08:03

94 楼

re

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

: 第5题move是gray code啊，没预先看过想不出来吧

h*g2013-03-05 08:03

95 楼

F 的prefix: 排好序就是每一个string 本身，还有所有string都是sorted 的吧？
比如：
vector buf;
buf.push_back("abc");
buf.push_back("abcd");
buf.push_back("acd");
buf.push_back("add");
buf.push_back("ae");
buf.push_back("aef");
buf.push_back("aefg");
buf.push_back("aefg");
buf.push_back("b");
buf.push_back("bcv");
buf.push_back("fr");

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

: //Print strings with certain prefix in a sorted string array
: void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
: OUT int& index1, int& index2);
: void PrintComPrefix(const char* strs[], int n, const char* szPre)
: {
: assert(strs && szPre && n > 0);
: const char* p = szPre;
: int nIndex1 = 0;
: int nIndex2 = n-1;
: while (*p != 0 && nIndex1 >= 0)

h*g2013-03-05 08:03

96 楼

F 的prefix: 排好序就是每一个string 本身，还有所有string都是sorted 的吧？
比如：
vector buf;
buf.push_back("abc");
buf.push_back("abcd");
buf.push_back("acd");
buf.push_back("add");
buf.push_back("ae");
buf.push_back("aef");
buf.push_back("aefg");
buf.push_back("aefg");
buf.push_back("b");
buf.push_back("bcv");
buf.push_back("fr");

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

: //Print strings with certain prefix in a sorted string array
: void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
: OUT int& index1, int& index2);
: void PrintComPrefix(const char* strs[], int n, const char* szPre)
: {
: assert(strs && szPre && n > 0);
: const char* p = szPre;
: int nIndex1 = 0;
: int nIndex2 = n-1;
: while (*p != 0 && nIndex1 >= 0)

s*f2013-03-05 08:03

97 楼

楼主给G看了F的offer？
argue后在G原offer的基础上加了多少呢？

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

: google比fb:
: bonus rate多5%
: relocation 多给5K
: RSU 市值多12K
: 还提了个什么US Government什么项目，Google帮你存钱进去啥的，听不懂。。。

i*e2013-03-05 08:03

98 楼

顶！
这个状态只需用 O(N^3) 的空间来保存就行，复杂度是 O(N^4)。
假设 (i,j) 分别为 s1 和 s2 的开始 index，n 为子串的长度，k 是把字串分成两个
子串的 pivot point (k = 1 ... n-1)：
F(i, j, n) = F(i+n-k, j, k) && F(i, j+k, n-k) ||
F(i, j, n-k) && F(i+n-k, j+n-k, k)
base case 为 F(i, j, 1) == true, iff s1[i] == s2[j]
然后 bottom-up 建立表，从所有 F(i, j, 2) --> F(i, j, len)，len = s1 长度。
那么答案就是 F(0, 0, len).
以下是非递归的 bottom-up DP 代码，空间复杂度 O(N^3)，时间复杂度 O(N^4).
bool isValid(string s1, string s2) {
int len = s1.length();
bool dp[64][64][64] = {false};
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
dp[i][j][1] = (s1[i] == s2[j]);
}
}
for (int n = 2; n <= len; n++) {
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
bool found = false;
for (int k = 1; !found && k <= n-1; k++) {
if ((dp[i+n-k][j][k] && dp[i][j+k][n-k]) ||
(dp[i][j][n-k] && dp[i+n-k][j+n-k][k])) {
found = true;
}
}
dp[i][j][n] = found;
}
}
}
return dp[0][0][len];
}
给lz个特别赞，三维dp在面试中非常非常罕见，这个对非竞赛者算是很有高难度的题目。

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

: F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
: 则如果存在k，使得要么
: 1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
: F[l1 + k][u1][l2 + k][u2]
: 2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
: F[l1 + k][u1][l2][l2 + k - 1]
: 两者有一个真，则F[l1][u1][l2][u2]为真
: 因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3
: 决策为o(n), 总复杂度o(N^4)
:

t*j2013-03-05 08:03

99 楼

如果string中没有重复字符的话，
这题可以用递归，判断如何扭转时可以cut掉不可能的路径。
复杂度可以是扭转二叉树的层数*string长度。不需要用DP
因为DP在此情况中不会减少复杂度。

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

: Nice idea!
: But what if there are multiple common adjacent characters between two
: strings?
: Example:
: abcdfbxc can be scrambled to fbcdabcd
: then we can reduce the two string to:
: a(bc)dfbxc
: f(bc)dabcd
: now we cannot reduce the strings any more.
:

H*12013-03-05 08:03

100 楼

赞
后来去了哪里啊？

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

: F的：
: 1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
: 2 单链表倒序输出
: 3. Dutch Flag Problem
: 4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
: 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
: ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
: 中出现且仅出现一次，比如两个人，
: 初始 {}
: move(1): {1}

N*82013-03-05 08:03

101 楼

哈哈，太妙了。

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

: 我当时找规律就出来了。。
: n = 1, 1
: n = 2, 1 2 1
: n = 3, 1 2 1 3 1 2 1
: n = 4, 你懂的。。

b*e2013-03-05 08:03

102 楼

我认为有O(n^2)的做法：
先把s1和s2转化成index表示：
tiger -> 12345
itreg -> 21543
第一个string总是正序的，第二个是乱序的。
那么问题转化成在s2里面找pivot index(在quicksort意义上的)。具体的说，一个
pivot index前面的数都<=这个index，它后面的数都>这个index。在上述例子中，
pivot index是1(counting from 0)。
找一个pivot index需要的时间是O(n)。找出所有的需要O(n^2)。

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

: 顶！
: 这个状态只需用 O(N^3) 的空间来保存就行，复杂度是 O(N^4)。
: 假设 (i,j) 分别为 s1 和 s2 的开始 index，n 为子串的长度，k 是把字串分成两个
: 子串的 pivot point (k = 1 ... n-1)：
: F(i, j, n) = F(i+n-k, j, k) && F(i, j+k, n-k) ||
: F(i, j, n-k) && F(i+n-k, j+n-k, k)
: base case 为 F(i, j, 1) == true, iff s1[i] == s2[j]
: 然后 bottom-up 建立表，从所有 F(i, j, 2) --> F(i, j, len)，len = s1 长度。
: 那么答案就是 F(0, 0, len).
: 以下是非递归的 bottom-up DP 代码，空间复杂度 O(N^3)，时间复杂度 O(N^4).