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 的大作中提到】
: 电面一面：
: 给一堆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 的大作中提到】
: ”使得任何有直接朋友关系的两个人必须处在不同的partition里“
: 如果a,b,c互为朋友该怎么分？
: 你的面经好难
|
|
P*******y
发帖数: 168 | 9 背景是system的
【在 g*******s 的大作中提到】
: lz看上去面的不错。lz背景是graphics么？貌似最后一题涉及求convex hull啊～
|
P*******y
发帖数: 168 | 10 算是cached DFS，我以前都只是DFS，没有用cache
【在 x*********w 的大作中提到】
: regular expression不用dp吧，太难了，是不是用cached DFS?
: 最后一题怎么连计算几何都上来了，太偏了！
|
|
|
p*****2
发帖数: 21240 | 11
这题dfs就可以了。
【在 x*********w 的大作中提到】
: ”使得任何有直接朋友关系的两个人必须处在不同的partition里“
: 如果a,b,c互为朋友该怎么分？
: 你的面经好难
|
p*****2
发帖数: 21240 | 12
RE的DP还好吧？
【在 x*********w 的大作中提到】
: regular expression不用dp吧，太难了，是不是用cached DFS?
: 最后一题怎么连计算几何都上来了，太偏了！
|
p*****2
发帖数: 21240 | 13
用BF解
【在 b****g 的大作中提到】
: 最后一题实在想不出来，能给个提示吗？
:
: iterative
|
r*******e
发帖数: 7583 | 14 类似于顶点着色问题，两种不同颜色，如果冲突就说明不能分？
【在 p*****2 的大作中提到】
:
: 用BF解
|
p*****2
发帖数: 21240 | 15
感觉差不多。不过不太清楚你说的顶点着色具体是什么题。
【在 r*******e 的大作中提到】
: 类似于顶点着色问题，两种不同颜色，如果冲突就说明不能分？
|
p*****2
发帖数: 21240 | 16 范围变成是单
机的producer和consumer，实现produce和consume函数，其实就是相当于fix size的
cache的add和pop问题，不用考虑多线程
这题不考虑多线程有什么考点呀？ |
F********9
发帖数: 44 | 17
iterative
【在 P*******y 的大作中提到】
: 电面一面：
: 给一堆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 的大作中提到】
: 范围变成是单
: 机的producer和consumer，实现produce和consume函数，其实就是相当于fix size的
: cache的add和pop问题，不用考虑多线程
: 这题不考虑多线程有什么考点呀？
|
x*********w
发帖数: 533 | 19
限定定点的convex hull??
这题有几个人能做出来？...
【在 b****g 的大作中提到】
: 最后一题实在想不出来，能给个提示吗？
:
: iterative
|
p*****2
发帖数: 21240 | 20
看了一下。差不多。这题感觉差不多是hackercup那题。不过hackercup那题我也忘差不
多了。
【在 r*******e 的大作中提到】
: 哦，我说的不是专指某一道题，是图的顶点着色问题
: m-coloring, 这题是m=2的特例
: http://en.wikipedia.org/wiki/Graph_coloring
|
|
|
P*******y
发帖数: 168 | 21 没太多考点，重点是前面的系统设计
【在 p*****2 的大作中提到】
: 范围变成是单
: 机的producer和consumer，实现produce和consume函数，其实就是相当于fix size的
: cache的add和pop问题，不用考虑多线程
: 这题不考虑多线程有什么考点呀？
|
p*****2
发帖数: 21240 | 22
多机的话如何设计是最优化的？
message queue
master node
【在 P*******y 的大作中提到】
: 没太多考点，重点是前面的系统设计
|
x*********w
发帖数: 533 | 23
BFS吧
【在 p*****2 的大作中提到】
:
: 多机的话如何设计是最优化的？
: message queue
: master node
|
c*********m
发帖数: 43 | 24 手机键盘给数字的iteration怎么写啊？
那道producer , consumer的题往zookeeper上靠就行了，可以实现分布式队列。 |
p*****2
发帖数: 21240 | 25
去看一下匈牙利算法。
【在 x*********w 的大作中提到】
:
: BFS吧
|
P*******y
发帖数: 168 | 26 我也不太懂，我当时就说了decentralized的方法。因为master node会有bottle neck
，reliability等各种问题
【在 p*****2 的大作中提到】
:
: 去看一下匈牙利算法。
|
p*****2
发帖数: 21240 | 27
neck
decentralize具体怎么搞？如果producer直接给consumer的话也很麻烦呀。
【在 P*******y 的大作中提到】
: 我也不太懂，我当时就说了decentralized的方法。因为master node会有bottle neck
: ，reliability等各种问题
|
P*******y
发帖数: 168 | 28 我参考了cassandra的方法，每个node都是同等的，需要维护map信息啥的，需要通信之
类的
【在 p*****2 的大作中提到】
:
: neck
: decentralize具体怎么搞？如果producer直接给consumer的话也很麻烦呀。
|
n****i
发帖数: 9 | |
a**********t
发帖数: 20 | |
|
|
f*******t
发帖数: 7549 | |
p*****2
发帖数: 21240 | 32
你的意思是把producer和consumer等同起来？
【在 P*******y 的大作中提到】
: 我参考了cassandra的方法，每个node都是同等的，需要维护map信息啥的，需要通信之
: 类的
|
p*****2
发帖数: 21240 | 33
20%工资不是白涨的呀。
【在 f*******t 的大作中提到】
: 题目难度挺高的
|
b****g
发帖数: 192 | 34 BF是指brute force吗？
难道是是多层循环计算面积？
【在 p*****2 的大作中提到】
:
: 20%工资不是白涨的呀。
|
p*****2
发帖数: 21240 | 35
是。面试只能这样了。
【在 b****g 的大作中提到】
: BF是指brute force吗？
: 难道是是多层循环计算面积？
|
b****g
发帖数: 192 | 36 如果三人互为朋友，那就说明无法二分partition，就回答否就可以了。
要是能二分partition，就回答是。
这题是不是就递归或者iterative搜索，见到一个点染一个色，其实就黑白两色间隔着
染，万一发现一个点被染成两种颜色了，就返回否。
【在 x*********w 的大作中提到】
: ”使得任何有直接朋友关系的两个人必须处在不同的partition里“
: 如果a,b,c互为朋友该怎么分？
: 你的面经好难
|
b****g
发帖数: 192 | 37 第一次看到BF这个缩写我心头一颤，想必是某种艰深豪华的算法，上网搜了一下发现时
暴力破解，哈哈哈
【在 p*****2 的大作中提到】
:
: 是。面试只能这样了。
|
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 的大作中提到】
: 手机键盘给数字的iteration怎么写啊？
: 那道producer , consumer的题往zookeeper上靠就行了，可以实现分布式队列。
|
b****g
发帖数: 192 | 39 producer consumer的题能具体解答一下吗？
【在 c*********m 的大作中提到】
: 手机键盘给数字的iteration怎么写啊？
: 那道producer , consumer的题往zookeeper上靠就行了，可以实现分布式队列。
|
J*****5
发帖数: 69 | 40
这题目不是求 undirected graph 里面有没有 cycle 而已吗? 怎么会出现别的高级数
学算法?
【在 p*****2 的大作中提到】
:
: 是。面试只能这样了。
|
|
|
J*****5
发帖数: 69 | 41
不好意思 发现我说错了, 这个可以有 cycle, my bad :P
【在 p*****2 的大作中提到】
:
: 是。面试只能这样了。
|
P*******y
发帖数: 168 | 42 不是
所有的producer node之间同等的
所有的consumer node之间也是同等的
producer可以跟任意一个consumer talk，然后那个consumer帮他redirect到一个最合
适的consumer node进行处理，大概是这个想法
【在 p*****2 的大作中提到】
:
: 是。面试只能这样了。
|
p*****2
发帖数: 21240 | 43
感觉很麻烦。
每个producer如何保存最新的consumer list， 如何选择跟哪一个talk。
consumer如何选择去direct到哪个
如何做统计？比如produce多少，consume了多少？如果producer all dead 或者
consumer all dead怎么办？
如果consumer还没有redirect出去就dead了，怎么办？
【在 P*******y 的大作中提到】
: 不是
: 所有的producer node之间同等的
: 所有的consumer node之间也是同等的
: producer可以跟任意一个consumer talk，然后那个consumer帮他redirect到一个最合
: 适的consumer node进行处理，大概是这个想法
|
P*******y
发帖数: 168 | 44 是很麻烦，面试应该不用回答到这么细。问啥答啥
【在 p*****2 的大作中提到】
:
: 感觉很麻烦。
: 每个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 的大作中提到】
: 电面一面：
: 给一堆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 的大作中提到】
: 电面一面：
: 给一堆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 的大作中提到】
:
: 不好意思 发现我说错了, 这个可以有 cycle, my bad :P
|
|
|
w**********0
发帖数: 214 | |
c******o
发帖数: 534 | 52 是不是可以转化成求所有的subsets的问题？
【在 z*********8 的大作中提到】
: 不是一回事吧
: A - B - C - D - A 是个cycle， 但是还是可以分成两个partition{A,C} 和 {B, D}
|
n**s
发帖数: 2230 | 53 bipartite的充要条件是没有odd cycle
【在 z*********8 的大作中提到】
: 不是一回事吧
: A - B - C - D - A 是个cycle， 但是还是可以分成两个partition{A,C} 和 {B, D}
|
x*****0
发帖数: 452 | |
P**********0
发帖数: 412 | |
