l****i
发帖数: 230 | 1 上周的onsite在这里：http://www.mitbbs.com/article_t0/JobHunting/32165741.html
周一committee meeting之后说positive，要了推荐信，昨天突然又要求加一轮设计题
的follow up面试。刚刚面的，感觉不是很好：
题目一：single machine,，给一个dictionary(key->value),每个entry takes 1KB，
总共10 Million个entry，single mutex protecting the dictionary，mutex takes
512 Byte，What potential problems do you see and how would you address them?
我直接告知我没有multi-thread programming的经历
然后问了第二个问题
题目二：给一个list的phrases，找最长的有如下规律的sequence
George Washington
Washington Park
Park Avenue
Avenue America
Suppose I give you a list of these phrases, but not in order
Q: How would you determine the longest possible chain among the set of
phrases?
问数据结构和算法。可是这个问题貌似是NP complete的
悲催啊，看来很多面FB的死在设计试题上确实不假 |
H****r
发帖数: 2801 | 2 第二题难道不是BFS?
them?
【在 l****i 的大作中提到】
: 上周的onsite在这里：http://www.mitbbs.com/article_t0/JobHunting/32165741.html
: 周一committee meeting之后说positive，要了推荐信，昨天突然又要求加一轮设计题
: 的follow up面试。刚刚面的，感觉不是很好：
: 题目一：single machine,，给一个dictionary(key->value),每个entry takes 1KB，
: 总共10 Million个entry，single mutex protecting the dictionary，mutex takes
: 512 Byte，What potential problems do you see and how would you address them?
: 我直接告知我没有multi-thread programming的经历
: 然后问了第二个问题
: 题目二：给一个list的phrases，找最长的有如下规律的sequence
: George Washington
|
w****x
发帖数: 2483 | 3 10G太大了，一个操作可能take太长的时间（内存和disk经常swap）导致其他的操作卡
在mutex上等待，是不是一个可以用读写锁缓解，再一个用多台机器做hash |
w****x
发帖数: 2483 | |
r********g
发帖数: 1351 | 5 这个DFS应该也可以吧？如果图太大BFS好像有内存的问题。。
【在 w****x 的大作中提到】
: 第二题就是图论吧，找出一个有向图的最长路径
|
w****x
发帖数: 2483 | 6
表示这个图呢， matrix?
【在 r********g 的大作中提到】
: 这个DFS应该也可以吧？如果图太大BFS好像有内存的问题。。
|
r********g
发帖数: 1351 | 7 看情况吧，稀疏图的话用adjacent list不好吗？好像还有别的存储方法更节省空间的
。。忘记了
【在 w****x 的大作中提到】
:
: 表示这个图呢， matrix?
|
r********g
发帖数: 1351 | 8 刚才想了下，发现图太大的找最长路径很麻烦啊。。绕了一会把自己绕晕了。。
【在 w****x 的大作中提到】
:
: 表示这个图呢， matrix?
|
c****m
发帖数: 11 | 9 看不明白第二个题目...
既然list是unorder的，那就用sequence里面的元素从list里面一个一个找呗？不可以
么？
them?
【在 l****i 的大作中提到】
: 上周的onsite在这里：http://www.mitbbs.com/article_t0/JobHunting/32165741.html
: 周一committee meeting之后说positive，要了推荐信，昨天突然又要求加一轮设计题
: 的follow up面试。刚刚面的，感觉不是很好：
: 题目一：single machine,，给一个dictionary(key->value),每个entry takes 1KB，
: 总共10 Million个entry，single mutex protecting the dictionary，mutex takes
: 512 Byte，What potential problems do you see and how would you address them?
: 我直接告知我没有multi-thread programming的经历
: 然后问了第二个问题
: 题目二：给一个list的phrases，找最长的有如下规律的sequence
: George Washington
|
l*****a
发帖数: 14598 | 10 就是一个个找啊
但是你怎么知道下一个不是已经出现过的呢？
【在 c****m 的大作中提到】
: 看不明白第二个题目...
: 既然list是unorder的，那就用sequence里面的元素从list里面一个一个找呗？不可以
: 么？
:
: them?
|
|
|
S*******e
发帖数: 379 | 11 我的想法是
1) mutex应该改read-write lock吧
2) 应该partition data，而不是用single mutex
3) 应该用write 到一个buffer而不是直接write的final destination来improve write
performance.这样dictionary本身就不需要lock了。nosql db基本都这么干。
不知道是不是面试官想要的方向。那个mutex takes 512B不知道有什么关系。
them?
【在 l****i 的大作中提到】
: 上周的onsite在这里：http://www.mitbbs.com/article_t0/JobHunting/32165741.html
: 周一committee meeting之后说positive，要了推荐信，昨天突然又要求加一轮设计题
: 的follow up面试。刚刚面的，感觉不是很好：
: 题目一：single machine,，给一个dictionary(key->value),每个entry takes 1KB，
: 总共10 Million个entry，single mutex protecting the dictionary，mutex takes
: 512 Byte，What potential problems do you see and how would you address them?
: 我直接告知我没有multi-thread programming的经历
: 然后问了第二个问题
: 题目二：给一个list的phrases，找最长的有如下规律的sequence
: George Washington
|
h**e
发帖数: 446 | 12 第一题就是要用多个mutex, 每一个mutex保护一段key range. mutex 大小是512B， 就
是提醒你需要考虑mutex的个数
跟内存的使用量的关系：mutex个数越多，dictionary的存取等待越短，但是同时意味
着更多的内存消耗量。
them?
【在 l****i 的大作中提到】
: 上周的onsite在这里：http://www.mitbbs.com/article_t0/JobHunting/32165741.html
: 周一committee meeting之后说positive，要了推荐信，昨天突然又要求加一轮设计题
: 的follow up面试。刚刚面的，感觉不是很好：
: 题目一：single machine,，给一个dictionary(key->value),每个entry takes 1KB，
: 总共10 Million个entry，single mutex protecting the dictionary，mutex takes
: 512 Byte，What potential problems do you see and how would you address them?
: 我直接告知我没有multi-thread programming的经历
: 然后问了第二个问题
: 题目二：给一个list的phrases，找最长的有如下规律的sequence
: George Washington
|
i**d
发帖数: 357 | 13 第一个题主要问题是high contention吧。应该是改成 micro-sharding + rwlock |
l***i
发帖数: 1309 | 14 2nd problem, if there is a cycle and you want longest path, then it is
Hamitonian path problem and no good solution. If a DAG, then you can use DP
to solve it in linear time. |
C***y
发帖数: 2546 | 15 第三点能详细讲讲不？
write到一个buffer的话，如果一个entry在buffer中，后续的read是否需要先查buffer
？还有就是多个write如何保护？
何时flush buffer？
谢谢！
write
【在 S*******e 的大作中提到】
: 我的想法是
: 1) mutex应该改read-write lock吧
: 2) 应该partition data，而不是用single mutex
: 3) 应该用write 到一个buffer而不是直接write的final destination来improve write
: performance.这样dictionary本身就不需要lock了。nosql db基本都这么干。
: 不知道是不是面试官想要的方向。那个mutex takes 512B不知道有什么关系。
:
: them?
|
p*****2
发帖数: 21240 | 16
有说不能重复吗？
【在 l*****a 的大作中提到】
: 就是一个个找啊
: 但是你怎么知道下一个不是已经出现过的呢？
|
J*********n
发帖数: 8 | 17
them?
都没看懂的怎么办？
【在 l****i 的大作中提到】
: 上周的onsite在这里：http://www.mitbbs.com/article_t0/JobHunting/32165741.html
: 周一committee meeting之后说positive，要了推荐信，昨天突然又要求加一轮设计题
: 的follow up面试。刚刚面的，感觉不是很好：
: 题目一：single machine,，给一个dictionary(key->value),每个entry takes 1KB，
: 总共10 Million个entry，single mutex protecting the dictionary，mutex takes
: 512 Byte，What potential problems do you see and how would you address them?
: 我直接告知我没有multi-thread programming的经历
: 然后问了第二个问题
: 题目二：给一个list的phrases，找最长的有如下规律的sequence
: George Washington
|
