来讨论一下新版规 - 未名空间MITBBS历史存档

w*s2013-10-29 07:10

1 楼

跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
麻烦大虾解一下面试3那道题？谢
电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
何算才能比较快的拿到每个结点的等级。答案关键是把 indegree算法转成 outdegree
算法
面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
4 3 9
6 5 1
7 8 2
这个返回4，因为5，6，7，8，方向可以是上，下，左，右，不可以斜角
面试3，有好多文挡，每个文挡可能有一个或零个父文挡，每个文挡可能有零个一个或
多个子文挡。要求重排所有文挡，重排后，所有文挡的父文挡都出现在子文挡前面。自
己设计数据结构和算法。用什么数据结构，我当时用双向链表，程序写的乱七八糟。请
问大虾们这个怎么做？
面试4，有一个数组，里面都是数字，找出最大的连续增长的数字串，这个数字串中每
个数字都出现在数组里。比如
[2，9，5，8，3，7，6，0]，返回5，因为5，6，7，8，9都出现在数组中
面试5，有10个数据中心，总共有10M台机器，分布于这10个数据中心。每台机器都需要
设置(config)。有一个3rd party service,每次调用它可以得到所有机器的设置。设计
一个系统，能够每30分钟，更新所有机器的设置。
面试1&5答的不错，直接得到正面反馈。编程题就菜了。
我去之前只来得及复习了一边基本数据结构与算法（因为早就忘了）,leetcode没来及
做。现在开始做。。。

d*f2013-10-29 07:10

2 楼

以后单个段子的，我们ｍａｒｋ第一个回帖好不好啊

x*i2013-10-29 07:10

3 楼

谢谢分享！
第三题像个图，每次找没有父亲的点输出，然后，对于他的每个孩子，删除它们的对应
父亲边，继续找没有父亲的点输出。

x*o2013-10-29 07:10

4 楼

chi

x*m2013-10-29 07:10

5 楼

这个面试不简单那呀，除了4以外好多实际的东西

M*e2013-10-29 07:10

6 楼

我建议由系统自动mark随机楼层

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

: 以后单个段子的，我们ｍａｒｋ第一个回帖好不好啊

i*e2013-10-29 07:10

7 楼

谢谢分享
面试2：为什么不是345678
面试3：这个是不是就是树的preorder 遍历？
请问第5题怎么答的？

x*o2013-10-29 07:10

8 楼

我白chi了

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

: 我建议由系统自动mark随机楼层

U*y2013-10-29 07:10

9 楼

Thanks for sharing!
#3 Pre-order traversal on trees (each tree root is the topmost parent folder
)?
Could you share your solution for #1 and #5? (sorry I have to type English
on office PC)

x*o2013-10-29 07:10

10 楼

如果只有我一个re, 那随机也应该是我吃包子，对吧?
求官方解释

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

: 我建议由系统自动mark随机楼层

w*s2013-10-29 07:10

11 楼

我写错了。。。已改正

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

: 谢谢分享
: 面试2：为什么不是345678
: 面试3：这个是不是就是树的preorder 遍历？
: 请问第5题怎么答的？

M*e2013-10-29 07:10

12 楼

满20楼后系统才开始自动抽签

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

: 如果只有我一个re, 那随机也应该是我吃包子，对吧?
: 求官方解释

j*a2013-10-29 07:10

13 楼

我觉得第三个就是identify root of each tree first, then do pre-order
traversal or level by level BFS. 用的双链表？莫非要求in place？不过bfs in
place 应该也成的。
能问一下第五题吗？

x*o2013-10-29 07:10

14 楼

我擦，官字两个口啊

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

: 满20楼后系统才开始自动抽签

w*s2013-10-29 07:10

15 楼

第三题，preorder traversal,
选第一个结点，看看如果有子结点，就DFS, mark visited,
backtrack回来，然后看第二个结点，如果访问过了就过，没访问过就重复刚刚的方法？
如果访问到第三个结点时候，发现第三个结点是第一个的父结点怎么办？
这样的话空间复杂度是O(|v|)？
1&5的答案晚点送上。

M*e2013-10-29 07:10

16 楼

都是老刑请的民工业务水平低

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

: 我擦，官字两个口啊

h*n2013-10-29 07:10

17 楼

第四题 leetcode原题吧 Longest Consecutive Sequence

outdegree

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

: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如

x*o2013-10-29 07:10

18 楼

这样啊，这些民工一定也是两个口

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

: 都是老刑请的民工业务水平低

w*s2013-10-29 07:10

19 楼

good idea. 这样的时间复杂度是？
worst case O(n^2)?

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

: 谢谢分享！
: 第三题像个图，每次找没有父亲的点输出，然后，对于他的每个孩子，删除它们的对应
: 父亲边，继续找没有父亲的点输出。

l*t2013-10-29 07:10

20 楼

随机吃个

j*a2013-10-29 07:10

21 楼

不是说只能有0个或者一个父节点，这样的花应该没有环吧，是个forest，只需要
identify indegree为0的点为root。如果是有环graph，就直接toplogical sort就好了
。

m*d2013-10-29 07:10

22 楼

今天好运气
老狼随机请吃包子

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

: 满20楼后系统才开始自动抽签

F*12013-10-29 07:10

23 楼

请问楼主，你是怎么知道每一轮的feedback的？是recruiter 直接说的吗？谢谢

R*d2013-10-29 07:10

24 楼

这个包子好像已经让我吃了

i*m2013-10-29 07:10

25 楼

第二题，把每个数字看成一个节点，每对相邻的连续数字看成一条权为1的有向边。问
题等价于求最长路径。因为没有环，用floyd算法，最坏情况O(n^4)就可以了，不知道
有没有更好的方法。

outdegree

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

: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如

M*n2013-10-29 07:10

26 楼

最终解释权归橙子

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

: 我擦，官字两个口啊

f*x2013-10-29 07:10

27 楼

outdegree
第三题这种不是topo排序么？

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

: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如

m*d2013-10-29 07:10

28 楼

橙+官=3个口
终于可以找到回家的路了

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

: 最终解释权归橙子

w*s2013-10-29 07:10

29 楼

谢谢大侠关于第三题的指点
第五题，答假设只更新一台机器，问考官数据传输多少时间，数据处理多少时间。得到
解答后，计算更新一台机器多久，多少台机器能在30分钟内更新所有。
Get config from 3rd party service方法有trigger or polling, 跟考官讨论什么情
况用什么方法，考官补充assumption，最后用确定polling。
因为要设计的系统需要负责所有机器的设置，所以要保证不能当机，举常用的方法，
load balance，主仆cluster,讨论区别，用什么比较好。确定用主仆，讨论主仆中，主
死了怎么办，怎样进行数据同步，等等。
最后讨论这个系统摆在哪里，总共有10个数据中心。可以摆在美国某个数据中心，也可
以每个大陆摆一个。如果第二种选择，就继续讨论利弊，怎么数据同步，converge什么
的。
总之，没有固定解答，关键就是讨论，考虑各种因素。希望对大家有帮助。

w*s2013-10-29 07:10

30 楼

1和5考官当时说的。recruiter据我的时候，说我有的表现好，有的不好。

【在 F**********1 的大作中提到】

: 请问楼主，你是怎么知道每一轮的feedback的？是recruiter 直接说的吗？谢谢

z*82013-10-29 07:10

31 楼

面试1：是dfs/bfs 一遍，算每个节点的indegree，然后按indegree排序吗？
面试3：先扫一遍建图，同时把没有父文档的分档保存在一个queue里，然后在一起做
bfs，记录访问顺序。
谢谢lz面筋

x*02013-10-29 07:10

32 楼

mark

w*r2013-10-29 07:10

33 楼

看来这辈子进google无望了，没一个会的

c*p2013-10-29 07:10

34 楼

mark

t*72013-10-29 07:10

35 楼

mark

b*c2013-10-29 07:10

36 楼

2nd q: 排序後動態規劃 o(n*n*lgn)

b*c2013-10-29 07:10

37 楼

第四題leetcode 只有offline算法，需要online的就加disjoint set

V*x2013-10-29 07:10

38 楼

第二题有O(n^2) 解法。可以先建立一个 value－》coordinate 的hashmap，然后利用
value是连续的特点直接O(1)查询。

S*62013-10-29 07:10

39 楼

面试2，recursive上下左右4方向，有更好的办法么？

S*62013-10-29 07:10

40 楼

面试3用tree merge?

d*d2013-10-29 07:10

41 楼

面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
4 3 9
6 5 1
7 8 2
scan line by line, build a directed graph by looking difference (-1 or +1 )
between neighbors (left and up, this should cover 4 directions).
4 3 9
6 5 1
7 8 2
like this
46|
v
7-> 8 2
edge can be saved in a map like
3->4
5->6
6->7
7->8
then if map size is 0 the max length must 1
otherwise use the similar logic used for 最大的连续增长的数字串 to find the
max
最大的连续增长的数字串...

l*82013-10-29 07:10

42 楼

mark

★ 发自iPhone App: ChineseWeb 8.7

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

: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如

f*52013-10-29 07:10

43 楼

还有个做法不知道对不对，另开一个int矩阵M，M[i][j]第0位为1表示原矩阵N[i-1][j]
=N[i][j]+1，就是原矩阵(i,j)有个指向上的边，M[i][j]第1位为1表示有指向右的边，
2表示下，3表示左。
然后从每个(i,j) M[i][j]>0位置开始dfs找最大路径，时间复杂度O(n^2)

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

: 第二题，把每个数字看成一个节点，每对相邻的连续数字看成一条权为1的有向边。问
: 题等价于求最长路径。因为没有环，用floyd算法，最坏情况O(n^4)就可以了，不知道
: 有没有更好的方法。
:
: outdegree

l*l2013-10-29 07:10

44 楼

mark

y*a2013-10-29 07:10

45 楼

mark

c*z2013-10-29 07:10

46 楼

mark

s*x2013-10-29 07:10

47 楼

好亏，好几道都是常见题，刷题才是王道。

d*y2013-10-29 07:10

48 楼

第三题感觉是topological sort

s*g2013-10-29 07:10

49 楼

面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
4 3 9
6 5 1
7 8 2
这个返回4，因为5，6，7，8，方向可以是上，下，左，右，不可以斜角
写了下第二题的dfs思路(java),大家看下对吗？
static int count = 0;
public static int maxSequentialNumbers(int[][] board){

int len = 0;
if (board == null || board.length == 0) return len;

for (int i=0; ifor (int j=0; jcount = 1;
helper(board, i, j);
len = Math.max(len, count);
}
}

return len;
}
public static void helper(int[][] board, int i, int j){
if (i<0 || i>=board[0].length || j<0 || j>=board.length ) return;

int next = board[i][j] + 1;

if ((i>0 && board[i-1][j] != next)
&& (i&& (j>0 && board[i][j-1] != next)
&& (jreturn;
//up
if (i>0 && board[i-1][j] == next){
count++;
helper(board, i-1, j);
}

//down
if (icount++;
helper(board, i+1, j);
}

//right
if (j>0 && board[i][j-1] == next){
count++;
helper(board, i, j-1);
}

//left
if (jcount++;
helper(board, i, j+1);
}

return;
}

w*e2013-10-29 07:10

50 楼

c*n2013-10-29 07:10

51 楼

第三题是不是用tree来表示更好一点啊？
加个root做所有没有父文档的节点的Parent
然后输出结果的时候直接做个BFS就好了？

outdegree

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

: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如

l*12013-10-29 07:10

52 楼

mark

m*g2013-10-29 07:10

53 楼

嗯，题目难度数量都多啊。