P*******y 发帖数: 168 | 1 电面一面:
给一堆F的用户,以及朋友关系,朋友之间的关系是双向的。问能否将朋友的关系图分
成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。
电面二面:
leetcode的手机键盘给数字,求各种字母组合的题。但是让给出recursive和iterative
方法。recursive很简单,iterative之前没写过,比较难想,当时卡了一会儿。后来写
出来了。
onsite五轮,每轮45分钟:
第一轮coding为主:先聊了下他的项目和我的research,几分钟的样子,然后写了个二
进制字符串相加的。另外一题是一个直角坐标系,上面和N个点,找出离原点最近的k个
点,就是top k问题
第二轮系统设计:让设计分布式的large scale的producer和consumer问题。就是有一
堆机器是producer,一堆机器是consumer。后来顺便写了一道coding题,范围变成是单
机的producer和consumer,实现produce和consume函数,其实就是相当于fix size的
cache的add和pop问题,不用考虑多线程
第三轮coding为主:写了道regular expression匹配的,leetcode原题。但是让优化,
当时刚开始没想出来,后来经提醒知道用memorize的方法。以前DP的题知道用这个方法
,这题从来没去想过,差点出差子
第四轮culture fit:主要讨论了research。后来写了个简单的题,三个数组,从三个
数组各取一数,找出和为某个值的组合
第五轮coding为主:三个color排序的题,leetcode原题。另一道是平面上一堆点,找
出四个点,使得四边形面积最大。刚开始想不出,后来问题简化成找三个点,使得三角
形面积最大。这题挺难的。后来没有coding这题 |
g*******s 发帖数: 2963 | 2 lz看上去面的不错。lz背景是graphics么?貌似最后一题涉及求convex hull啊~ |
x*********w 发帖数: 533 | 3 ”使得任何有直接朋友关系的两个人必须处在不同的partition里“
如果a,b,c互为朋友该怎么分?
你的面经好难 |
g**G 发帖数: 767 | 4 第一题没读懂,LZ的面经确实好难,fb都是这难度么? |
x*********w 发帖数: 533 | 5 regular expression不用dp吧,太难了,是不是用cached DFS?
最后一题怎么连计算几何都上来了,太偏了! |
b****g 发帖数: 192 | 6 最后一题实在想不出来,能给个提示吗?
iterative
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 电面一面: : 给一堆F的用户,以及朋友关系,朋友之间的关系是双向的。问能否将朋友的关系图分 : 成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。 : 电面二面: : leetcode的手机键盘给数字,求各种字母组合的题。但是让给出recursive和iterative : 方法。recursive很简单,iterative之前没写过,比较难想,当时卡了一会儿。后来写 : 出来了。 : onsite五轮,每轮45分钟: : 第一轮coding为主:先聊了下他的项目和我的research,几分钟的样子,然后写了个二 : 进制字符串相加的。另外一题是一个直角坐标系,上面和N个点,找出离原点最近的k个
|
M******7 发帖数: 30 | |
P*******y 发帖数: 168 | 8 就是问你能否分,output是个Boolean值
【在 x*********w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ”使得任何有直接朋友关系的两个人必须处在不同的partition里“ : 如果a,b,c互为朋友该怎么分? : 你的面经好难
|
|
P*******y 发帖数: 168 | 9 背景是system的
【在 g*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : lz看上去面的不错。lz背景是graphics么?貌似最后一题涉及求convex hull啊~
|
P*******y 发帖数: 168 | 10 算是cached DFS,我以前都只是DFS,没有用cache
【在 x*********w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : regular expression不用dp吧,太难了,是不是用cached DFS? : 最后一题怎么连计算几何都上来了,太偏了!
|
|
|
p*****2 发帖数: 21240 | 11
这题dfs就可以了。
【在 x*********w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ”使得任何有直接朋友关系的两个人必须处在不同的partition里“ : 如果a,b,c互为朋友该怎么分? : 你的面经好难
|
p*****2 发帖数: 21240 | 12
RE的DP还好吧?
【在 x*********w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : regular expression不用dp吧,太难了,是不是用cached DFS? : 最后一题怎么连计算几何都上来了,太偏了!
|
p*****2 发帖数: 21240 | 13
用BF解
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后一题实在想不出来,能给个提示吗? : : iterative
|
r*******e 发帖数: 7583 | 14 类似于顶点着色问题,两种不同颜色,如果冲突就说明不能分?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 用BF解
|
p*****2 发帖数: 21240 | 15
感觉差不多。不过不太清楚你说的顶点着色具体是什么题。
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 类似于顶点着色问题,两种不同颜色,如果冲突就说明不能分?
|
p*****2 发帖数: 21240 | 16 范围变成是单
机的producer和consumer,实现produce和consume函数,其实就是相当于fix size的
cache的add和pop问题,不用考虑多线程
这题不考虑多线程有什么考点呀? |
F********9 发帖数: 44 | 17
iterative
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 电面一面: : 给一堆F的用户,以及朋友关系,朋友之间的关系是双向的。问能否将朋友的关系图分 : 成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。 : 电面二面: : leetcode的手机键盘给数字,求各种字母组合的题。但是让给出recursive和iterative : 方法。recursive很简单,iterative之前没写过,比较难想,当时卡了一会儿。后来写 : 出来了。 : onsite五轮,每轮45分钟: : 第一轮coding为主:先聊了下他的项目和我的research,几分钟的样子,然后写了个二 : 进制字符串相加的。另外一题是一个直角坐标系,上面和N个点,找出离原点最近的k个
|
r*******e 发帖数: 7583 | 18 哦,我说的不是专指某一道题,是图的顶点着色问题
m-coloring, 这题是m=2的特例
http://en.wikipedia.org/wiki/Graph_coloring
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 范围变成是单 : 机的producer和consumer,实现produce和consume函数,其实就是相当于fix size的 : cache的add和pop问题,不用考虑多线程 : 这题不考虑多线程有什么考点呀?
|
x*********w 发帖数: 533 | 19
限定定点的convex hull??
这题有几个人能做出来?...
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后一题实在想不出来,能给个提示吗? : : iterative
|
p*****2 发帖数: 21240 | 20
看了一下。差不多。这题感觉差不多是hackercup那题。不过hackercup那题我也忘差不
多了。
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哦,我说的不是专指某一道题,是图的顶点着色问题 : m-coloring, 这题是m=2的特例 : http://en.wikipedia.org/wiki/Graph_coloring
|
|
|
P*******y 发帖数: 168 | 21 没太多考点,重点是前面的系统设计
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 范围变成是单 : 机的producer和consumer,实现produce和consume函数,其实就是相当于fix size的 : cache的add和pop问题,不用考虑多线程 : 这题不考虑多线程有什么考点呀?
|
p*****2 发帖数: 21240 | 22
多机的话如何设计是最优化的?
message queue
master node
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没太多考点,重点是前面的系统设计
|
x*********w 发帖数: 533 | 23
BFS吧
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 多机的话如何设计是最优化的? : message queue : master node
|
c*********m 发帖数: 43 | 24 手机键盘给数字的iteration怎么写啊?
那道producer , consumer的题往zookeeper上靠就行了,可以实现分布式队列。 |
p*****2 发帖数: 21240 | 25
去看一下匈牙利算法。
【在 x*********w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : BFS吧
|
P*******y 发帖数: 168 | 26 我也不太懂,我当时就说了decentralized的方法。因为master node会有bottle neck
,reliability等各种问题
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 去看一下匈牙利算法。
|
p*****2 发帖数: 21240 | 27
neck
decentralize具体怎么搞?如果producer直接给consumer的话也很麻烦呀。
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也不太懂,我当时就说了decentralized的方法。因为master node会有bottle neck : ,reliability等各种问题
|
P*******y 发帖数: 168 | 28 我参考了cassandra的方法,每个node都是同等的,需要维护map信息啥的,需要通信之
类的
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : neck : decentralize具体怎么搞?如果producer直接给consumer的话也很麻烦呀。
|
n****i 发帖数: 9 | |
a**********t 发帖数: 20 | |
|
|
f*******t 发帖数: 7549 | |
p*****2 发帖数: 21240 | 32
你的意思是把producer和consumer等同起来?
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我参考了cassandra的方法,每个node都是同等的,需要维护map信息啥的,需要通信之 : 类的
|
p*****2 发帖数: 21240 | 33
20%工资不是白涨的呀。
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目难度挺高的
|
b****g 发帖数: 192 | 34 BF是指brute force吗?
难道是是多层循环计算面积?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 20%工资不是白涨的呀。
|
p*****2 发帖数: 21240 | 35
是。面试只能这样了。
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : BF是指brute force吗? : 难道是是多层循环计算面积?
|
b****g 发帖数: 192 | 36 如果三人互为朋友,那就说明无法二分partition,就回答否就可以了。
要是能二分partition,就回答是。
这题是不是就递归或者iterative搜索,见到一个点染一个色,其实就黑白两色间隔着
染,万一发现一个点被染成两种颜色了,就返回否。
【在 x*********w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ”使得任何有直接朋友关系的两个人必须处在不同的partition里“ : 如果a,b,c互为朋友该怎么分? : 你的面经好难
|
b****g 发帖数: 192 | 37 第一次看到BF这个缩写我心头一颤,想必是某种艰深豪华的算法,上网搜了一下发现时
暴力破解,哈哈哈
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是。面试只能这样了。
|
b****g 发帖数: 192 | 38 我昨天看了LZ面经于是写了个iterative的手机键盘数字,通过了leetcode测试。
我写的是最幼稚的那种,就是比如输入是"29",就建个
vector["abc","wxyz"]
然后把另一个vector从[0,0]做像数数一样的累加
[0,0] [0,1] [0,2] [0,3] [1,0] [1,1] [1,2]... [2,3]
每个vector都对应一种输出。比如[1,2]对应"by"
其实就是数数,有点像bitmap的感觉。
【在 c*********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 手机键盘给数字的iteration怎么写啊? : 那道producer , consumer的题往zookeeper上靠就行了,可以实现分布式队列。
|
b****g 发帖数: 192 | 39 producer consumer的题能具体解答一下吗?
【在 c*********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 手机键盘给数字的iteration怎么写啊? : 那道producer , consumer的题往zookeeper上靠就行了,可以实现分布式队列。
|
J*****5 发帖数: 69 | 40
这题目不是求 undirected graph 里面有没有 cycle 而已吗? 怎么会出现别的高级数
学算法?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是。面试只能这样了。
|
|
|
J*****5 发帖数: 69 | 41
不好意思 发现我说错了, 这个可以有 cycle, my bad :P
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是。面试只能这样了。
|
P*******y 发帖数: 168 | 42 不是
所有的producer node之间同等的
所有的consumer node之间也是同等的
producer可以跟任意一个consumer talk,然后那个consumer帮他redirect到一个最合
适的consumer node进行处理,大概是这个想法
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是。面试只能这样了。
|
p*****2 发帖数: 21240 | 43
感觉很麻烦。
每个producer如何保存最新的consumer list, 如何选择跟哪一个talk。
consumer如何选择去direct到哪个
如何做统计?比如produce多少,consume了多少?如果producer all dead 或者
consumer all dead怎么办?
如果consumer还没有redirect出去就dead了,怎么办?
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是 : 所有的producer node之间同等的 : 所有的consumer node之间也是同等的 : producer可以跟任意一个consumer talk,然后那个consumer帮他redirect到一个最合 : 适的consumer node进行处理,大概是这个想法
|
P*******y 发帖数: 168 | 44 是很麻烦,面试应该不用回答到这么细。问啥答啥
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 感觉很麻烦。 : 每个producer如何保存最新的consumer list, 如何选择跟哪一个talk。 : consumer如何选择去direct到哪个 : 如何做统计?比如produce多少,consume了多少?如果producer all dead 或者 : consumer all dead怎么办? : 如果consumer还没有redirect出去就dead了,怎么办?
|
e***s 发帖数: 799 | |
l**********g 发帖数: 426 | 46 从外围找4个点连成四边形;
所有的点分成2部分:在四边形里,和外;
只需考虑四边形外的点,连成新四边形,如果大于原四边形则替换原四边形;goto top
do again
iterative
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 电面一面: : 给一堆F的用户,以及朋友关系,朋友之间的关系是双向的。问能否将朋友的关系图分 : 成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。 : 电面二面: : leetcode的手机键盘给数字,求各种字母组合的题。但是让给出recursive和iterative : 方法。recursive很简单,iterative之前没写过,比较难想,当时卡了一会儿。后来写 : 出来了。 : onsite五轮,每轮45分钟: : 第一轮coding为主:先聊了下他的项目和我的research,几分钟的样子,然后写了个二 : 进制字符串相加的。另外一题是一个直角坐标系,上面和N个点,找出离原点最近的k个
|
w******j 发帖数: 185 | |
c********p 发帖数: 1969 | |
b***e 发帖数: 1419 | 49 第五个,求凸包,然后根据直径DP。O(n^2)。
iterative
【在 P*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 电面一面: : 给一堆F的用户,以及朋友关系,朋友之间的关系是双向的。问能否将朋友的关系图分 : 成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。 : 电面二面: : leetcode的手机键盘给数字,求各种字母组合的题。但是让给出recursive和iterative : 方法。recursive很简单,iterative之前没写过,比较难想,当时卡了一会儿。后来写 : 出来了。 : onsite五轮,每轮45分钟: : 第一轮coding为主:先聊了下他的项目和我的research,几分钟的样子,然后写了个二 : 进制字符串相加的。另外一题是一个直角坐标系,上面和N个点,找出离原点最近的k个
|
z*********8 发帖数: 2070 | 50 不是一回事吧
A - B - C - D - A 是个cycle, 但是还是可以分成两个partition{A,C} 和 {B, D}
【在 J*****5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不好意思 发现我说错了, 这个可以有 cycle, my bad :P
|
|
|
w**********0 发帖数: 214 | |
c******o 发帖数: 534 | 52 是不是可以转化成求所有的subsets的问题?
【在 z*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是一回事吧 : A - B - C - D - A 是个cycle, 但是还是可以分成两个partition{A,C} 和 {B, D}
|
n**s 发帖数: 2230 | 53 bipartite的充要条件是没有odd cycle
【在 z*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是一回事吧 : A - B - C - D - A 是个cycle, 但是还是可以分成两个partition{A,C} 和 {B, D}
|
x*****0 发帖数: 452 | |
P**********0 发帖数: 412 | |