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 | |