w***s
发帖数: 17 | 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没来及
做。现在开始做。。。 |
x******i
发帖数: 374 | 2 谢谢分享！
第三题像个图，每次找没有父亲的点输出，然后，对于他的每个孩子，删除它们的对应
父亲边，继续找没有父亲的点输出。 |
x****m
发帖数: 1084 | |
i*****e
发帖数: 63 | 4 谢谢分享
面试2： 为什么不是345678
面试3： 这个是不是就是树的preorder 遍历？
请问第5题怎么答的？ |
U*********y
发帖数: 54 | 5 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) |
w***s
发帖数: 17 | 6 我写错了。。。已改正
【在 i*****e 的大作中提到】
: 谢谢分享
: 面试2： 为什么不是345678
: 面试3： 这个是不是就是树的preorder 遍历？
: 请问第5题怎么答的？
|
j******a
发帖数: 55 | 7 我觉得第三个就是identify root of each tree first, then do pre-order
traversal or level by level BFS. 用的双链表？莫非要求in place？不过bfs in
place 应该也成的。
能问一下第五题吗？ |
w***s
发帖数: 17 | 8 第三题，preorder traversal,
选第一个结点，看看如果有子结点，就DFS, mark visited,
backtrack回来，然后看第二个结点，如果访问过了就过，没访问过就重复刚刚的方法？
如果访问到第三个结点时候，发现第三个结点是第一个的父结点怎么办？
这样的话空间复杂度是O(|v|)？
1&5的答案晚点送上。 |
h****n
发帖数: 1093 | 9 第四题 leetcode原题吧 Longest Consecutive Sequence
outdegree
【在 w***s 的大作中提到】
: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是 把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
|
w***s
发帖数: 17 | 10 good idea. 这样的时间复杂度是？
worst case O(n^2)?
【在 x******i 的大作中提到】
: 谢谢分享！
: 第三题像个图，每次找没有父亲的点输出，然后，对于他的每个孩子，删除它们的对应
: 父亲边，继续找没有父亲的点输出。
|
|
|
j******a
发帖数: 55 | 11 不是说只能有0个或者一个父节点，这样的花应该没有环吧，是个forest，只需要
identify indegree为0的点为root。如果是有环graph，就直接toplogical sort就好了
。 |
F**********1
发帖数: 50 | 12 请问楼主，你是怎么知道每一轮的feedback的？ 是recruiter 直接说的吗？ 谢谢 |
i******m
发帖数: 375 | 13 第二题，把每个数字看成一个节点，每对相邻的连续数字看成一条权为1的有向边。问
题等价于求最长路径。因为没有环，用floyd算法，最坏情况O(n^4)就可以了，不知道
有没有更好的方法。
outdegree
【在 w***s 的大作中提到】
: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是 把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
|
f********x
发帖数: 2086 | 14
outdegree
第三题这种不是topo排序么？
【在 w***s 的大作中提到】
: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是 把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
|
w***s
发帖数: 17 | 15 谢谢大侠关于第三题的指点
第五题，答假设只更新一台机器，问考官数据传输多少时间，数据处理多少时间。得到
解答后，计算更新一台机器多久，多少台机器能在30分钟内更新所有。
Get config from 3rd party service方法有trigger or polling, 跟考官讨论什么情
况用什么方法，考官补充assumption，最后用确定polling。
因为要设计的系统需要负责所有机器的设置，所以要保证不能当机，举常用的方法，
load balance，主仆cluster,讨论区别，用什么比较好。确定用主仆，讨论主仆中，主
死了怎么办，怎样进行数据同步，等等。
最后讨论这个系统摆在哪里，总共有10个数据中心。可以摆在美国某个数据中心，也可
以每个大陆摆一个。如果第二种选择，就继续讨论利弊，怎么数据同步，converge什么
的。
总之，没有固定解答，关键就是讨论，考虑各种因素。希望对大家有帮助。 |
w***s
发帖数: 17 | 16 1和5考官当时说的。recruiter据我的时候，说我有的表现好，有的不好。
【在 F**********1 的大作中提到】
: 请问楼主，你是怎么知道每一轮的feedback的？ 是recruiter 直接说的吗？ 谢谢
|
z****8
发帖数: 7 | 17 面试1： 是dfs/bfs 一遍， 算每个节点的indegree，然后按indegree排序吗？
面试3：先扫一遍建图，同时把没有父文档的分档保存在一个queue里，然后在一起做
bfs，记录访问顺序。
谢谢lz面筋 |
x*****0
发帖数: 452 | |
w****r
发帖数: 15252 | |
c********p
发帖数: 1969 | |
|
|
t*********7
发帖数: 255 | |
b*****c
发帖数: 1103 | 22 2nd q: 排序後動態規劃 o(n*n*lgn) |
b*****c
发帖数: 1103 | 23 第四題leetcode 只有offline算法，需要online的就加disjoint set |
V*******x
发帖数: 54 | 24 第二题有O(n^2) 解法。可以先建立一个 value－》coordinate 的hashmap，然后利用
value是连续的特点直接O(1)查询。 |
S******6
发帖数: 55 | 25 面试2，recursive上下左右4方向，有更好的办法么？ |
S******6
发帖数: 55 | |
d*****d
发帖数: 180 | 27 面试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
4<-3 9
6<-5 1
|
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*****8
发帖数: 1083 | 28 mark
★ 发自iPhone App: ChineseWeb 8.7
【在 w***s 的大作中提到】
: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是 把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
|
f*******5
发帖数: 52 | 29
还有个做法不知道对不对，另开一个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****l
发帖数: 3394 | |
|
|
y**********a
发帖数: 824 | |
c**z
发帖数: 669 | |
s**x
发帖数: 7506 | |
d*******y
发帖数: 31 | |
s***g
发帖数: 257 | 35 面试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; i
for (int j=0; j
count = 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)
&& (j
return;
//up
if (i>0 && board[i-1][j] == next){
count++;
helper(board, i-1, j);
}
//down
if (i
count++;
helper(board, i+1, j);
}
//right
if (j>0 && board[i][j-1] == next){
count++;
helper(board, i, j-1);
}
//left
if (j
count++;
helper(board, i, j+1);
}
return;
} |
w******e
发帖数: 1621 | |
c*******n
发帖数: 442 | 37 第三题是不是用tree来表示更好一点啊？
加个root做所有没有父文档的节点的Parent
然后输出结果的时候直接做个BFS就好了？
outdegree
【在 w***s 的大作中提到】
: 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
: 麻烦大虾解一下面试3那道题？谢
: 电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
: 电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
: 面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
: 面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
: 引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
: 何算才能比较快的拿到每个结点的等级。答案关键是 把 indegree算法转成 outdegree
: 算法
: 面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
|
l**********1
发帖数: 415 | |
m*******g
发帖数: 410 | |
