g家面经 - 未名空间MITBBS历史存档

g*r2015-07-22 07:07

1 楼

1.一个字符串，从字典查出字符串所有单词，然后怎么提升效率
2.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
杂度
3.树里的所有duplicated子树，O（n)遍历一次
4.BST，给定一个数值，返回BST中最接近的节点， lg n
5.Minors one
6.一个整数链表，返回最长连续数字长度 o(n)
7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
节点为M[a+x][b+y],求从一点出发是否可以遍历矩阵
8.判断任意两个人是否有血缘关系

s*32015-07-22 07:07

2 楼

on site interview?

h*p2015-07-22 07:07

3 楼

多谢分享！

s*l2015-07-22 07:07

4 楼

赞面经~
问一下
这道题是用minimum spanning tree?
.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短,
Minors one 这道题是什么意思啊？
这道题我只想到Bf方法有更好的解法吗？
7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
这道题怎么定义子树？从某个node 以下到叶子还是说不用包括叶子呢？
树里的所有duplicated子树，O（n)遍历一次

n*n2015-07-22 07:07

5 楼

什么叫字符串所有单词？
duplicated 子树能一次遍历全部找出？用hash吗？

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

: 1.一个字符串，从字典查出字符串所有单词，然后怎么提升效率
: 2.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
: 杂度
: 3.树里的所有duplicated子树，O（n)遍历一次
: 4.BST，给定一个数值，返回BST中最接近的节点， lg n
: 5.Minors one
: 6.一个整数链表，返回最长连续数字长度 o(n)
: 7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
: 节点为M[a+x][b+y],求从一点出发是否可以遍历矩阵
: 8.判断任意两个人是否有血缘关系

n*n2015-07-22 07:07

6 楼

minus 1吧
子树当然包括叶子

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

: 赞面经~
: 问一下
: 这道题是用minimum spanning tree?
: .N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短,
: Minors one 这道题是什么意思啊？
: 这道题我只想到Bf方法有更好的解法吗？
: 7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
: 这道题怎么定义子树？从某个node 以下到叶子还是说不用包括叶子呢？
: 树里的所有duplicated子树，O（n)遍历一次

b*w2015-07-22 07:07

7 楼

第二题是manhatton距离？

p*d2015-07-22 07:07

8 楼

第二题log不可能吧？顶多O(n)求median

s*l2015-07-22 07:07

9 楼

re~
如果要lg 那肯定有别的附加条件
不过
求谁的median? 怎么求？

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

: 第二题log不可能吧？顶多O(n)求median

g*r2015-07-22 07:07

10 楼

这个2D和1D意思是差不多的，因为xy是彼此独立的，1D怎么做呢，我觉得是二分法，从
中间取，然后比较左边和右边的和当前的大小，都比当前大，当前就是最小，要不然向
比当前小的一侧取中间，因为是二分，所以我说是log的。

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

: re~
: 如果要lg 那肯定有别的附加条件
: 不过
: 求谁的median? 怎么求？

g*r2015-07-22 07:07

11 楼

就是用了hash存，key是一个可以唯一确定子树的字符串， value可以是出现的次数。
字符串是类似in order search的结果，不过没有子节点的地方，填一个字符，以保证
唯一性，所以基本上func（left） + root + func（right）是新的key，这样走一边，
就把duplicated的找出来了

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

: 什么叫字符串所有单词？
: duplicated 子树能一次遍历全部找出？用hash吗？

s*l2015-07-22 07:07

12 楼

你是说 x上2分的同时 y上也2分
这样每次去掉3/4 ？

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

: 这个2D和1D意思是差不多的，因为xy是彼此独立的，1D怎么做呢，我觉得是二分法，从
: 中间取，然后比较左边和右边的和当前的大小，都比当前大，当前就是最小，要不然向
: 比当前小的一侧取中间，因为是二分，所以我说是log的。

l*s2015-07-22 07:07

13 楼

二维数组的这种二分不是lg（n）甚至lg(n2)，因为每次divide是将matrix分成了四份
去conquer。面试官的要求是做出lg的算法么？

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

: 这个2D和1D意思是差不多的，因为xy是彼此独立的，1D怎么做呢，我觉得是二分法，从
: 中间取，然后比较左边和右边的和当前的大小，都比当前大，当前就是最小，要不然向
: 比当前小的一侧取中间，因为是二分，所以我说是log的。

E*e2015-07-22 07:07

14 楼

赞一个

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

: 就是用了hash存，key是一个可以唯一确定子树的字符串， value可以是出现的次数。
: 字符串是类似in order search的结果，不过没有子节点的地方，填一个字符，以保证
: 唯一性，所以基本上func（left） + root + func（right）是新的key，这样走一边，
: 就把duplicated的找出来了

b*b2015-07-22 07:07

15 楼

first thing need clarification is, whether the distance is Manhattan
distance, if the answer is yes, then the point in question is (median(x1, x2
, ...xm), median(y1, y2, ...ym)), there is logM algorithm to find the median
value from unsorted array, so the answer is O(logM).
If the answer is no, then we need to partition the 2D space, but need to
calculate the distance every time, so it will be M*O(logM).

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

: 二维数组的这种二分不是lg（n）甚至lg(n2)，因为每次divide是将matrix分成了四份
: 去conquer。面试官的要求是做出lg的算法么？

s*l2015-07-22 07:07

16 楼

there is logM algorithm to find the median value from unsorted array?
这个怎么logm? 我就知道用partition o(m)

x2
median

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

: first thing need clarification is, whether the distance is Manhattan
: distance, if the answer is yes, then the point in question is (median(x1, x2
: , ...xm), median(y1, y2, ...ym)), there is logM algorithm to find the median
: value from unsorted array, so the answer is O(logM).
: If the answer is no, then we need to partition the 2D space, but need to
: calculate the distance every time, so it will be M*O(logM).

s*l2015-07-22 07:07

17 楼

他说的lg(n) 的n是边吧~

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

: 二维数组的这种二分不是lg（n）甚至lg(n2)，因为每次divide是将matrix分成了四份
: 去conquer。面试官的要求是做出lg的算法么？

l*s2015-07-22 07:07

18 楼

嗯。
backstab说得有道理，如果是曼哈顿距离，那么其实很简单，只要横向找出中值（不过
这个中值是指最短横向距离到各点的那个x，而不是一般理解的数组中的中值），然后
找出
纵向“中值“y就好了。首先要确定的是问题是否是曼哈顿距离。

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

: 他说的lg(n) 的n是边吧~

b*b2015-07-22 07:07

19 楼

是我记错了，是partition o(m)。

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

: there is logM algorithm to find the median value from unsorted array?
: 这个怎么logm? 我就知道用partition o(m)
:
: x2
: median

e*32015-07-22 07:07

20 楼

,4
6. 一个整数链表，返回最长连续数字长度 o(n)，例如输入[10,6,2,15,5,9,1,3,100,
4
没看懂...怎么个连续法
7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问.
..
暴力解.从任意一点出发,一直走,直到走到某一点已经走过的.如果已经走了N*M的格子
就结束.要O(N^2).有更好的解法吗?

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

: 1.一个字符串，从字典查出字符串所有单词，然后怎么提升效率
: 2.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
: 杂度
: 3.树里的所有duplicated子树，O（n)遍历一次
: 4.BST，给定一个数值，返回BST中最接近的节点， lg n
: 5.Minors one
: 6.一个整数链表，返回最长连续数字长度 o(n)
: 7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
: 节点为M[a+x][b+y],求从一点出发是否可以遍历矩阵
: 8.判断任意两个人是否有血缘关系

Q*F2015-07-22 07:07

21 楼

树里的所有duplicated子树，O（n)遍历一次
能否举个例子？不是很懂这个题目要干什么。

f*52015-07-22 07:07

22 楼

请问LZ第一题是如何优化的？我除了想出了O(n^2)，没有相出更好的办法。请问LZ有什
么更好的办法？

m*t2015-07-22 07:07

23 楼

第二题如果 manhattan distance 就是 median (x), median(y) 分开算。
是 euclidean distance 的话要复杂得多，是一个 convex optimization 的问题，参
见
geometric median。

h*p2015-07-22 07:07

24 楼

LZ可以讲解下第一题吗？如何提升效率？
Tries的话worst caseyeshi N^2啊

,4

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

: 1.一个字符串，从字典查出字符串所有单词，然后怎么提升效率
: 2.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
: 杂度
: 3.树里的所有duplicated子树，O（n)遍历一次
: 4.BST，给定一个数值，返回BST中最接近的节点， lg n
: 5.Minors one
: 6.一个整数链表，返回最长连续数字长度 o(n)
: 7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
: 节点为M[a+x][b+y],求从一点出发是否可以遍历矩阵
: 8.判断任意两个人是否有血缘关系

a*u2015-07-22 07:07

25 楼

key是唯一确定子树的字符串，如何保证这个字符串的唯一性？in order traverse也没
法保证唯一性。
1 21
/ 和 /
32 4 3 4

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

: 就是用了hash存，key是一个可以唯一确定子树的字符串， value可以是出现的次数。
: 字符串是类似in order search的结果，不过没有子节点的地方，填一个字符，以保证
: 唯一性，所以基本上func（left） + root + func（right）是新的key，这样走一边，
: 就把duplicated的找出来了

m*t2015-07-22 07:07

26 楼

问一下第七题怎摸解。没看明白题
判断任意两个人是否有血缘关系，自己定义person类

r*g2015-07-22 07:07

27 楼

第一题，即使用trie，好像也很慢
第三题，什么叫duplicated字数？是不是用一个很大的map，key就是每个树的表示(lc
上那种表示方法，#表示缺失的节点)，这样很耗费空间。好处是，从子节点的表示可以
得到父节点的表示。但是这样太耗费空间了，优化表示方法？
第七题，题意不清楚，a+x, b+y都可能超出index啊，超出了就mod？但是好像是道数学
题而不是编程题。直觉是只要x,y互素就行。

,4

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

: 1.一个字符串，从字典查出字符串所有单词，然后怎么提升效率
: 2.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
: 杂度
: 3.树里的所有duplicated子树，O（n)遍历一次
: 4.BST，给定一个数值，返回BST中最接近的节点， lg n
: 5.Minors one
: 6.一个整数链表，返回最长连续数字长度 o(n)
: 7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
: 节点为M[a+x][b+y],求从一点出发是否可以遍历矩阵
: 8.判断任意两个人是否有血缘关系

p*g2015-07-22 07:07

28 楼

https://en.wikipedia.org/wiki/Merkle_tree

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

: key是唯一确定子树的字符串，如何保证这个字符串的唯一性？in order traverse也没
: 法保证唯一性。
: 1 21
: / 和 /
: 32 4 3 4

p*n2015-07-22 07:07

29 楼

(median(x1, x2
在一个点既有x median, 又有 y median.
x2
median

p*n2015-07-22 07:07

30 楼

LZ 第二题，聚会地点必须是朋友家还是任意矩阵点， Manhattan distance? 另有其他
附加条件吗？
谢谢分享，但强烈建议描述清楚。

,4

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

: 1.一个字符串，从字典查出字符串所有单词，然后怎么提升效率
: 2.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
: 杂度
: 3.树里的所有duplicated子树，O（n)遍历一次
: 4.BST，给定一个数值，返回BST中最接近的节点， lg n
: 5.Minors one
: 6.一个整数链表，返回最长连续数字长度 o(n)
: 7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
: 节点为M[a+x][b+y],求从一点出发是否可以遍历矩阵
: 8.判断任意两个人是否有血缘关系