d*********g
发帖数: 38 | 1 没有一轮国人，过程感觉也没有很亲切，看来还是要中国人多才好。九月初的onsite，
一共五轮，四轮coding一轮系统设计（第一轮）
1. billion级别的raw data，怎样村在多个节点中，实现有效率的查找。给定条件是数
据是已经在那里的，而且不会被修改。
2. valid bst讨论属性，边界条件
3. 给一个排序的数组， 1 2 5 8 9 11 16，输出missing range比如3-4，6-7，10，
12-15
4. iterator of iterator，写一个iterator iterate所有的元素，例如
itr1 1 2 3 4
itr2 5 6 7 8
itr3 9 10 11 12
写一个iterator输出1 5 9 2 6 10 ...
5. 类似moving average，固定size不断update average，讨论多县城的情况。 |
h**p
发帖数: 211 | |
n******n
发帖数: 12088 | 3 系统题没看懂
【在 d*********g 的大作中提到】
: 没有一轮国人，过程感觉也没有很亲切，看来还是要中国人多才好。九月初的onsite，
: 一共五轮，四轮coding一轮系统设计（第一轮）
: 1. billion级别的raw data，怎样村在多个节点中，实现有效率的查找。给定条件是数
: 据是已经在那里的，而且不会被修改。
: 2. valid bst讨论属性，边界条件
: 3. 给一个排序的数组， 1 2 5 8 9 11 16，输出missing range比如3-4，6-7，10，
: 12-15
: 4. iterator of iterator，写一个iterator iterate所有的元素，例如
: itr1 1 2 3 4
: itr2 5 6 7 8
|
d*********g
发帖数: 38 | 4 工作了，不过小转了一下方向。
【在 h**p 的大作中提到】
: 赞分享！
: LZ能说下背景吗？new grad？
|
d*********g
发帖数: 38 | 5 就想象成query 的raw data吧，原题也没有说得很清楚，面试官一脸苦相不说话，我假
设的是可以排序，希望对你有帮助。
【在 n******n 的大作中提到】
: 系统题没看懂
|
r******l
发帖数: 10760 | 6 第三个有啥trick吗？直接比较相邻的两个数，如果相差不是1就输出？
【在 d*********g 的大作中提到】
: 没有一轮国人，过程感觉也没有很亲切，看来还是要中国人多才好。九月初的onsite，
: 一共五轮，四轮coding一轮系统设计（第一轮）
: 1. billion级别的raw data，怎样村在多个节点中，实现有效率的查找。给定条件是数
: 据是已经在那里的，而且不会被修改。
: 2. valid bst讨论属性，边界条件
: 3. 给一个排序的数组， 1 2 5 8 9 11 16，输出missing range比如3-4，6-7，10，
: 12-15
: 4. iterator of iterator，写一个iterator iterate所有的元素，例如
: itr1 1 2 3 4
: itr2 5 6 7 8
|
g*******d
发帖数: 495 | 7 第一题，比方说根据hash放在多个存储节点（每个节点可以把数据全放RAM里），然后
在放一个或多个查询节点。查询节点根据query判断该找哪个存储节点查询，同时可以
放个cache在查询节点上。这样能通过么？（如果是45分钟面试，这样也未免有点简单
吧，是不是要进一步问细节或者有更多的条件？）
第五题，是不是说求最后插入的k个数的平均，然后有个插入函数？
前几天被面了两个类似的，就是一个插入函数，一个查询函数，问完了还问如何多线程。
这题我觉得维护一个最近k个数的和，还有一个最长为k的队列。每次插入时，减去k个
数之前的数（即队列的队尾），然后加上新插入的数，再求平均。
不知道lz对多线程是如何回答的。我当时回答说一个线程专门用于插入，其他线程向这
个线程发送要插入的数据，这样加锁的部分可以尽量小，等待时间就相比“每个线程都
可以插入但都有锁”要短。 |
e****x
发帖数: 148 | 8 我电面时候也面了第五题，然后跪了
面试官最后说用类似sliding window的方法做 |
|
c******w
发帖数: 1108 | 9 binary search的变种。
If a[0]==0, a[n/2]==n/2 then no need to check 0 through n/2
【在 r******l 的大作中提到】
: 第三个有啥trick吗？直接比较相邻的两个数，如果相差不是1就输出？
|
m******a
发帖数: 34 | 10 保存当前window的sum,然后更新就可以了吧,sum=sum-old_to_delete+new_to_insert.
程。
【在 g*******d 的大作中提到】
: 第一题，比方说根据hash放在多个存储节点（每个节点可以把数据全放RAM里），然后
: 在放一个或多个查询节点。查询节点根据query判断该找哪个存储节点查询，同时可以
: 放个cache在查询节点上。这样能通过么？（如果是45分钟面试，这样也未免有点简单
: 吧，是不是要进一步问细节或者有更多的条件？）
: 第五题，是不是说求最后插入的k个数的平均，然后有个插入函数？
: 前几天被面了两个类似的，就是一个插入函数，一个查询函数，问完了还问如何多线程。
: 这题我觉得维护一个最近k个数的和，还有一个最长为k的队列。每次插入时，减去k个
: 数之前的数（即队列的队尾），然后加上新插入的数，再求平均。
: 不知道lz对多线程是如何回答的。我当时回答说一个线程专门用于插入，其他线程向这
: 个线程发送要插入的数据，这样加锁的部分可以尽量小，等待时间就相比“每个线程都
|
|
|
d********i
发帖数: 582 | |
i****k
发帖数: 668 | 12 说没重复了嘛？或者说没重复是默认的么？
【在 c******w 的大作中提到】
: binary search的变种。
: If a[0]==0, a[n/2]==n/2 then no need to check 0 through n/2
|
i****k
发帖数: 668 | 13 第四题的坑在哪里呀，为啥我觉得很简单....
【在 d********i 的大作中提到】
: LZ第四题做出来了吗？
|
m******3
发帖数: 346 | 14 设计题我思路跟你想的类似，假设是类似KV存储，key比较小，但是value比较大，做一
个hash(key)返回key对应的data存放的node, 这个hash表应该可以存放在RAM中，如果
RAM够大，也可以放一个cache之类，如果需要查询的key对应的元素在cache中存在，直
接返回，不用去storage layer查询，另外象你说的，storage node本身也可以有cache
, 另外是不是还可以说说consistent hashing之类的，因为单个storage node存储容量
有限，当数据多的时候，需要增加storage node, 如果不是consitant hashing, 在加
入新结点或者有结点坏的时候会造成大量数据移动。还是有就是一份数据应该多存几个
copy,如果在读数据时候，从hash得到的storage node坏了，应该怎么处理，怎么找到
存放这个数据的其他结点之类的。
程。
【在 g*******d 的大作中提到】
: 第一题，比方说根据hash放在多个存储节点（每个节点可以把数据全放RAM里），然后
: 在放一个或多个查询节点。查询节点根据query判断该找哪个存储节点查询，同时可以
: 放个cache在查询节点上。这样能通过么？（如果是45分钟面试，这样也未免有点简单
: 吧，是不是要进一步问细节或者有更多的条件？）
: 第五题，是不是说求最后插入的k个数的平均，然后有个插入函数？
: 前几天被面了两个类似的，就是一个插入函数，一个查询函数，问完了还问如何多线程。
: 这题我觉得维护一个最近k个数的和，还有一个最长为k的队列。每次插入时，减去k个
: 数之前的数（即队列的队尾），然后加上新插入的数，再求平均。
: 不知道lz对多线程是如何回答的。我当时回答说一个线程专门用于插入，其他线程向这
: 个线程发送要插入的数据，这样加锁的部分可以尽量小，等待时间就相比“每个线程都
|
s******k
发帖数: 6659 | 15 算法复杂度是多少？O(log(n))?
【在 c******w 的大作中提到】
: binary search的变种。
: If a[0]==0, a[n/2]==n/2 then no need to check 0 through n/2
|
k******a
发帖数: 44 | 16 我的考虑：
1. billion级别的raw data，怎样村在多个节点中，实现有效率的查找。给定条件是数
据是已经在那里的，而且不会被修改。
这里需要很多交流的地方，个人觉得是排序 + B树的思路。可以按照key来shard，然后
每个节点按照B数组织数据
2. valid bst讨论属性，边界条件
3. 给一个排序的数组， 1 2 5 8 9 11 16，输出missing range比如3-4，6-7，10，
12-15
这个直接扫一遍，看看a[i]和a[i+1]的关系。
4. iterator of iterator，写一个iterator iterate所有的元素，例如
itr1 1 2 3 4
itr2 5 6 7 8
itr3 9 10 11 12
写一个iterator输出1 5 9 2 6 10 ...
这个用一个LinkedList>吧，每次remove(0), 处理这个Iterator,
然后把这个iterator加到list最后。
5. 类似moving average，固定size不断update average，讨论多县城的情况
这个是sliding window. 每次averge * k = sum, sum = sum - a[0], sum = sum + a[
k], average = sum / k。多线程要看具体有哪些操作，什么样的overlap。最简单就是
加synchronized修饰符在方法上。 |
