俄亥俄州立又出事了，TA跟人打架找学生帮忙 - 未名空间MITBBS历史存档

俄亥俄州立又出事了，TA跟人打架找学生帮忙# Joke - 肚皮舞运动

g*s2010-11-22 08:11

1 楼

贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
１。８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
水。
２。二叉树给两nodes找最近公共祖先
３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
track是指从其
中一个符出发，可以向四周走，可以重复，可以回头。
e.g.
a b
c d
string: 'bdba' could be found but not for 'bcd'.

f*82010-11-22 08:11

2 楼

人家不想去就威胁说“等期末考试的时候再说”

g*s2010-11-22 08:11

3 楼

按你的描述，7只，1天。估计你漏了条件。
经典。无父指针的话，time O(N) and space O(N)比较容易。RMQ比较难，而且对多组
输入才有
优势。
将字符矩阵转换成状态图，用基于有限自动机的模式匹配。

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

: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d

c*r2010-11-22 08:11

4 楼

bs这个ta
恩

人家不想去就威胁说“等期末考试的时候再说”

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

: 人家不想去就威胁说“等期末考试的时候再说”

g*s2010-11-22 08:11

5 楼

1. It is not 7. you missed some thing from the question.
2. missed some conditions: 1) every node has the parent pointer. 2) can
only use O(1) extra space
3. DP

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

:
: 按你的描述，7只，1天。估计你漏了条件。
: 经典。无父指针的话，time O(N) and space O(N)比较容易。RMQ比较难，而且对多组
: 输入才有
: 优势。
: 将字符矩阵转换成状态图，用基于有限自动机的模式匹配。

o*12010-11-22 08:11

6 楼

可能是说考试完了就更有时间准备了打斗了

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

: 人家不想去就威胁说“等期末考试的时候再说”

l*a2010-11-22 08:11

7 楼

显然他同时希望老鼠数目最少

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

:
: 按你的描述，7只，1天。估计你漏了条件。
: 经典。无父指针的话，time O(N) and space O(N)比较容易。RMQ比较难，而且对多组
: 输入才有
: 优势。
: 将字符矩阵转换成状态图，用基于有限自动机的模式匹配。

C*y2010-11-22 08:11

8 楼

我感觉应该是问7
7的话，3只老鼠
8的话，4只
条件是可以混合

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

: 1. It is not 7. you missed some thing from the question.
: 2. missed some conditions: 1) every node has the parent pointer. 2) can
: only use O(1) extra space
: 3. DP

g*s2010-11-22 08:11

9 楼

here u have acutally 2 goals: minimize the # of days and the # of rats?
the lower bound for each is 1 and 4, but can't be achieved at the same
time, right?
then it becomes: given two lists, find the first common elements.
intuitively this is not hard even for O(1) space.
i don't see how it links to dp.

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

: 1. It is not 7. you missed some thing from the question.
: 2. missed some conditions: 1) every node has the parent pointer. 2) can
: only use O(1) extra space
: 3. DP

g*s2010-11-22 08:11

10 楼

8 的话 3 is enough.
2^3 = 8

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

: 我感觉应该是问7
: 7的话，3只老鼠
: 8的话，4只
: 条件是可以混合

C*y2010-11-22 08:11

11 楼

第八瓶水怎么encoding？
如果只有3位（3只老鼠）的话

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

: 8 的话 3 is enough.
: 2^3 = 8

g*s2010-11-22 08:11

12 楼

then we have to assume the poison is very strong that after mixing it with
water it is still lethal.

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

: 我感觉应该是问7
: 7的话，3只老鼠
: 8的话，4只
: 条件是可以混合

g*s2010-11-22 08:11

13 楼

3 rats for 1 day is the best solution.
yes, it is a simple question.
It is a DP question. space and time complexity = O (m * n * k) k is the
length of the string.

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

:
: then we have to assume the poison is very strong that after mixing it with
: water it is still lethal.

g*s2010-11-22 08:11

14 楼

yes.

with

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

:
: then we have to assume the poison is very strong that after mixing it with
: water it is still lethal.

T*o2010-11-22 08:11

15 楼

原来2是google的题啊，经典题啊。

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

: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d

g*s2010-11-22 08:11

16 楼

mark the bottles with 0..7. giving three rats x,y,z.
x y z #
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7
x,y,z分别喝列上对应是1的瓶号的水。
x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,5,7

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

: 第八瓶水怎么encoding？
: 如果只有3位（3只老鼠）的话

l*a2010-11-22 08:11

17 楼

how do u hold the two lists with O(1) memory?

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

:
: then we have to assume the poison is very strong that after mixing it with
: water it is still lethal.

s*c2010-11-22 08:11

18 楼

1.
3只老鼠，测一轮：第一只老鼠喝一口编号为001，011，101和111的水（最低位为1）；
第二只老鼠喝一口中间位为1的4瓶水；第三只老鼠喝最高位为1的水。第二天，从3只老
鼠的生死能推出有毒的水的编号。
2.
如果给了parent指针的话，应该就是向上trace就可以了吧？把visit过的node mark一
下，第一个被mark两次的node就是公共祖先了吧？
3.
求详解。。。。

g*s2010-11-22 08:11

19 楼

it's already exists in the tree implicitly through parent pointers.

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

: how do u hold the two lists with O(1) memory?

g*s2010-11-22 08:11

20 楼

interesting puzzle. i think this links to some test coverage
theory/algorithms.

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

: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7

l*a2010-11-22 08:11

21 楼

if so
u can say search node in BST is also O(1) for time complexity,
doesn't it???
search in BT is also O(1)

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

: it's already exists in the tree implicitly through parent pointers.

C*y2010-11-22 08:11

22 楼

如果第0瓶有毒的话？
哪只老鼠死？
还是你有个附加条件，肯定有瓶是有毒的?

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

: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7

g*s2010-11-22 08:11

23 楼

can u give ur solution to show why it is dp?

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

: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7

g*s2010-11-22 08:11

24 楼

then no rat die.

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

: 如果第0瓶有毒的话？
: 哪只老鼠死？
: 还是你有个附加条件，肯定有瓶是有毒的?

g*s2010-11-22 08:11

25 楼

none.
yes, already mentioned: one of the eight is poisoned.

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

: 如果第0瓶有毒的话？
: 哪只老鼠死？
: 还是你有个附加条件，肯定有瓶是有毒的?

g*s2010-11-22 08:11

26 楼

how could search gives u O(1)? bt is O(N) while bst is O(h).

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

: if so
: u can say search node in BST is also O(1) for time complexity,
: doesn't it???
: search in BT is also O(1)

g*s2010-11-22 08:11

27 楼

define
f(x,y,z) x,y means the position in the matrix
z means the right z-length sub string of orig search string.
f(x,y,z) true if from x,y, we can find the right z-length sub string of
orig search string; otherwise false
t(z) means the z-th char from the right.
f(x,y,z) =

f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||
f(x , y - 1, z -1) && isValidY(y-1) && mtx[x,y-1] == t(z) ||
f(x , y + 1, z -1) && isValidY(y+1) && mtx[x,y+1] == t(z)

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

: how could search gives u O(1)? bt is O(N) while bst is O(h).

l*a2010-11-22 08:11

28 楼

then why u can say the path from node to root is O(1)???
even for comparing two paths,it is also O(1)?

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

: how could search gives u O(1)? bt is O(N) while bst is O(h).

g*s2010-11-22 08:11

29 楼

The requirement for this question is using extra O(1) space.
the key idea for this question is: calculate the depth of the two nodes
first(dx,dy, assume dx>dy). then move one node for (dx-dy) steps. then
they are in the same level. then both move together until reach the same
node.

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

: then why u can say the path from node to root is O(1)???
: even for comparing two paths,it is also O(1)?

s*c2010-11-22 08:11

30 楼

恍然大雾。。。

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

: The requirement for this question is using extra O(1) space.
: the key idea for this question is: calculate the depth of the two nodes
: first(dx,dy, assume dx>dy). then move one node for (dx-dy) steps. then
: they are in the same level. then both move together until reach the same
: node.

l*a2010-11-22 08:11

31 楼

u r right,
no need to store them
think too much...

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

: The requirement for this question is using extra O(1) space.
: the key idea for this question is: calculate the depth of the two nodes
: first(dx,dy, assume dx>dy). then move one node for (dx-dy) steps. then
: they are in the same level. then both move together until reach the same
: node.

p*g2010-11-22 08:11

32 楼

一定要指向父节点的指针么？做post-order traverse，用两个bool表示那两个点是否
被traversed，返回第一个both bool are true的点。

g*s2010-11-22 08:11

33 楼

这用了超过O(1)的空间

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

: 一定要指向父节点的指针么？做post-order traverse，用两个bool表示那两个点是否
: 被traversed，返回第一个both bool are true的点。

p*g2010-11-22 08:11

34 楼

只用了两个bool啊

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

: 这用了超过O(1)的空间

g*s2010-11-22 08:11

35 楼

post-order traverse实际上是用recursive的方式实现了一个栈。额外空间是tree的深
度。
而且，这个算法，如果两个结点在最右边，那么要遍历玩所有节点。时间复杂度是O(n).
而用同时向parent移动找的方式，算法时间是树的深度。

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

: 只用了两个bool啊

g*s2010-11-22 08:11

36 楼

父指针本身也是O(N)的开销。
不带父指针的LCA可以做到T O(N) and S O(N).
带父指针的看似T O(N), S O(1)，算上父指针本身开销，其实复杂度是一样的。

n).

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

: post-order traverse实际上是用recursive的方式实现了一个栈。额外空间是tree的深
: 度。
: 而且，这个算法，如果两个结点在最右边，那么要遍历玩所有节点。时间复杂度是O(n).
: 而用同时向parent移动找的方式，算法时间是树的深度。

g*e2010-11-22 08:11

37 楼

would somebody explain question 3?
how is dp used here?

g*s2010-11-22 08:11

38 楼

怪我题目没有说好。父指针是题目已经给的。

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

: 父指针本身也是O(N)的开销。
: 不带父指针的LCA可以做到T O(N) and S O(N).
: 带父指针的看似T O(N), S O(1)，算上父指针本身开销，其实复杂度是一样的。
:
: n).

g*s2010-11-22 08:11

39 楼

我给出DP公式了。

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

: would somebody explain question 3?
: how is dp used here?

y*m2010-11-22 08:11

40 楼

1.1只老鼠1天
joke办法:
1只老鼠每隔1分钟(不是说一天么,就24小时呗)从7瓶子中每瓶中喝一点，记下瓶子先后
次序，如果第二天老鼠死了就按时间推算拿瓶有毒,没死就是剩下一瓶...
2.
p1,p2
while(true){
p1= p1->parent
p2=p2->parent
if(p1=p2) break;
}

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

: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d

y*m2010-11-22 08:11

41 楼

类似方法用4只老鼠1天也行吧
1234 A
2345 B
3456 C
4567 D
x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,4,5
这里 xy都死了，那67那瓶有毒?
thx!

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

: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7

g*s2010-11-22 08:11

42 楼

2.
你这个只有在同一层才行。这就是为什么要先分别算深度。

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

: 1.1只老鼠1天
: joke办法:
: 1只老鼠每隔1分钟(不是说一天么,就24小时呗)从7瓶子中每瓶中喝一点，记下瓶子先后
: 次序，如果第二天老鼠死了就按时间推算拿瓶有毒,没死就是剩下一瓶...
: 2.
: p1,p2
: while(true){
: p1= p1->parent
: p2=p2->parent
: if(p1=p2) break;

y*m2010-11-22 08:11

43 楼

老鼠那题不明白，请指教，xy都死了怎么区分6还是7?
thx!

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

: 2.
: 你这个只有在同一层才行。这就是为什么要先分别算深度。

g*s2010-11-22 08:11

44 楼

1天的话越少越好。
3只老鼠，有死或者不死两种状态，最多能表达的状态是8.

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

: 类似方法用4只老鼠1天也行吧
: 1234 A
: 2345 B
: 3456 C
: 4567 D
: x drinks 4,5,6,7
: y drinks 2,3,6,7
: z drinks 1,3,4,5
: 这里 xy都死了，那67那瓶有毒?
: thx!

y*m2010-11-22 08:11

45 楼

那只是二进制吧，xy110是6，但7那瓶有毒也会导致xy死吧?

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

: 1天的话越少越好。
: 3只老鼠，有死或者不死两种状态，最多能表达的状态是8.

S*z2010-11-22 08:11

46 楼

大胆请教初始条件的x,y即x0,y0在哪里？
是不是orig string的最后一个char在Matrix中所有出现过的地方？

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

: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||

S*z2010-11-22 08:11

47 楼

7有毒那都得挂？

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

: 那只是二进制吧，xy110是6，但7那瓶有毒也会导致xy死吧?

y*m2010-11-22 08:11

48 楼

也是，树结构里应该记录每个节点当前深度吧，then 加个深度平衡计算...
2.
p1,p2,lev1,lev2
while(lev1>lev2){
p1= p1->parent
lev1--
}
while(lev2>lev1){
p2= p2->parent
lev2--
}
while(p1<>p2){
p1= p1->parent
p2=p2->parent
}

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

: 2.
: 你这个只有在同一层才行。这就是为什么要先分别算深度。

y*m2010-11-22 08:11

49 楼

x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,4,5
z都没喝，怎么会挂?
grass好像排错了，ms 可以
x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,5,7

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

: 7有毒那都得挂？

g*s2010-11-22 08:11

50 楼

是的。我的typo。不过，从我给的表，应该能看出z是1，3，5，7.（读对应z的列）

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

: x drinks 4,5,6,7
: y drinks 2,3,6,7
: z drinks 1,3,4,5
: z都没喝，怎么会挂?
: grass好像排错了，ms 可以
: x drinks 4,5,6,7
: y drinks 2,3,6,7
: z drinks 1,3,5,7

g*s2010-11-22 08:11

51 楼

你这个可以。不过，更简单点，可以f(x,y,0)=true
基本上，你写出递推公式，面试官就知道你会了。

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

: 大胆请教初始条件的x,y即x0,y0在哪里？
: 是不是orig string的最后一个char在Matrix中所有出现过的地方？

z*c2010-11-22 08:11

52 楼

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

: 大胆请教初始条件的x,y即x0,y0在哪里？
: 是不是orig string的最后一个char在Matrix中所有出现过的地方？

z*c2010-11-22 08:11

53 楼

楼主说的是遍历所有的cell吧，所以才有的O(N*M*K)

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

: 大胆请教初始条件的x,y即x0,y0在哪里？
: 是不是orig string的最后一个char在Matrix中所有出现过的地方？

z*c2010-11-22 08:11

54 楼

多谢分享！
算法是对的，如果加上base case: if (0 == z) return else ...。
我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
哪了？

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

: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||

z*c2010-11-22 08:11

55 楼

多谢分享！
算法是对的，如果加上base case: if (0 == z) return else ...。
我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
哪了？

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

: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||

g*s2010-11-22 08:11

56 楼

Simple question: do you think f(n) = f(n-1) + f(n-2) is also 标准的递归?

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

: 多谢分享！
: 算法是对的，如果加上base case: if (0 == z) return else ...。
: 我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
: 哪了？

g*s2010-11-22 08:11

57 楼

我给的是递推公式，他是问DP的初始值如何设。f(x,y,0)=true

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

: 楼主说的是遍历所有的cell吧，所以才有的O(N*M*K)

z*c2010-11-22 08:11

58 楼

是吧，如果用额外空间存中间结果的话，就是dp

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

: Simple question: do you think f(n) = f(n-1) + f(n-2) is also 标准的递归?

s*a2010-11-22 08:11

59 楼

How about this?
mark the bottles with 0..7. giving three rats x,y,z.
x y z #
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7
0 means not drinking, 1 means drinking
If all alive, bottle 0 is poison,
If z died, bottle 1,
If y died, bottle 2,
If y,z died, bottle 3,
If x died, bottle 4,
If x,z died, bottle 5
If x,y died, bottle 6
If all died, bottle 7

f*42010-11-22 08:11

60 楼

实际实现的时候建表然后每次递归的时候看一看值是否已经在里面了在
里面的话就直接返回了

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

: 多谢分享！
: 算法是对的，如果加上base case: if (0 == z) return else ...。
: 我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
: 哪了？

z*c2010-11-22 08:11

61 楼

哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?

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

: 实际实现的时候建表然后每次递归的时候看一看值是否已经在里面了在
: 里面的话就直接返回了

z*c2010-11-22 08:11

62 楼

哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?

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

: 实际实现的时候建表然后每次递归的时候看一看值是否已经在里面了在
: 里面的话就直接返回了

z*c2010-11-22 08:11

63 楼

哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?

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

: 实际实现的时候建表然后每次递归的时候看一看值是否已经在里面了在
: 里面的话就直接返回了

z*c2010-11-22 08:11

64 楼

哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?

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

: 实际实现的时候建表然后每次递归的时候看一看值是否已经在里面了在
: 里面的话就直接返回了

f*42010-11-22 08:11

65 楼

对啊 LZ不是说过了么

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

: 哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
: 但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?

G*o2010-11-22 08:11

66 楼

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

: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d

z*c2010-11-22 08:11

67 楼

哈哈，对！我没仔细中间的回帖 :(

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

: 对啊 LZ不是说过了么

b*y2010-11-22 08:11

68 楼

阿，这个是(7,4)汉明码的验证矩阵阿

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

: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7

i*s2010-11-22 08:11

69 楼

No need to go to DP. If you know the start position in the matrix, it's o(n)
simple scan once, n is the length of string.

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

: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||

h*n2010-11-22 08:11

70 楼

三只都没死的话，不就是第0瓶有毒。。。

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

: 如果第0瓶有毒的话？
: 哪只老鼠死？
: 还是你有个附加条件，肯定有瓶是有毒的?

g*s2010-11-22 08:11

71 楼

不觉得能有O(k)的解即使给定你一个点作为开始点。k is the length of string.

o(n)

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

: No need to go to DP. If you know the start position in the matrix, it's o(n)
: simple scan once, n is the length of string.

i*s2010-11-22 08:11

72 楼

There IS O(k) solution obviously. If starting point is unknown, then it's O(
m)
+ (k), where m is the number of elements in the matrix.

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

: 不觉得能有O(k)的解即使给定你一个点作为开始点。k is the length of string.
:
: o(n)

g*s2010-11-22 08:11

73 楼

说来听听。

it's O(

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

: There IS O(k) solution obviously. If starting point is unknown, then it's O(
: m)
: + (k), where m is the number of elements in the matrix.

g*s2010-11-22 08:11

74 楼

肯定不能有O(k)的解.我可以给出反例。
要不就是你理解题目有问题了。贪心在这里是不对的。

it's O(

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

: There IS O(k) solution obviously. If starting point is unknown, then it's O(
: m)
: + (k), where m is the number of elements in the matrix.

z*c2010-11-22 08:11

75 楼

是O(4^N)吧?

n)

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

: No need to go to DP. If you know the start position in the matrix, it's o(n)
: simple scan once, n is the length of string.

i*s2010-11-22 08:11

76 楼

The abcd matrix example shows the matrix elements are unique, so greedy is
fine. Let me know your counter example. The original post doesn't say
replicates in the matrix.

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

: 肯定不能有O(k)的解.我可以给出反例。
: 要不就是你理解题目有问题了。贪心在这里是不对的。
:
: it's O(

g*s2010-11-22 08:11

77 楼

题目我给的只是一个简单的例子而已。里面当然可以有重复。
给一个例子
n*n, 所有左下半部(包括对角线）全是a，坐标（2，n)是b。右上全是c。
a b c .... c
a a c .... c
a a a c ... c
...
a a a a ....a
字符串是 aaa..ab (n个a）。起点是（1，1).

greedy is

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

: The abcd matrix example shows the matrix elements are unique, so greedy is
: fine. Let me know your counter example. The original post doesn't say
: replicates in the matrix.

j*x2010-11-22 08:11

78 楼

这是经典的问题，不是G家发明的。。。

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

: 原来2是google的题啊，经典题啊。