FB 店面/Onsite 7/24

多谢, 1a, 4b 弄清楚了. 估计自己现场搞会有点小慌.

sterne 发表于 2017-8-26 12:24
请问楼主后来System Design面了个啥题？最后决定去FB了吗？谢谢

加面的POI, 这个是准备过的题目 面试时候反馈也很好， 结果第二天一大早就通知跪了，非常诡异

jordandong 发表于 2017-8-27 04:09
加面的POI, 这个是准备过的题目 面试时候反馈也很好， 结果第二天一大早就通知跪了，非常诡异

哎，面试这东西真说不好。只能Move on了。楼主愿意说一下POI的回答思路吗， 我看到这个面经很多次了，但是还是不确定方向。 是不是讲一堆GeoHashing, 怎么画格子，将二维降成一位，之后存储成Trie。 存储的时候根据Category 存。 Query的时候，根据Category先找到那颗Trie，之后根据精确度找到附近的N个POI，返回. 或者还需要考虑shard trie? 希望楼主给点指点。谢谢！

summerlismile 发表于 2017-7-25 13:11
这个需要在每个Node里加一个sum的field， 然后建树时储存每一个subtree的sum值在那个Node， 然后根据BST性 ...

我也觉得这个相当于pre-process tree, 当多次调用的时候就有优势。

考虑到复杂度，我觉得直接用in-order traversal直接存node value 到 set<int>或vector<int> data 里，然后直接
count([lo, hi]) := upper_bound(data.begin(), data.end(), hi) - lower_bound(data.begin(), data.end(), lo);
都是pre-process time O(N), extra space O(N) (in additional to native tree storage).

jordandong 发表于 2017-7-25 13:57
原理一样啊  不需要写iter出来， 直接往linkedlist尾巴上接就好了

这个linked list的情况若要求写iterator的话比vector情况还要麻烦一点，不能backward access linked list, 用deque instead of stack.

sterne 发表于 2017-8-27 05:43
哎，面试这东西真说不好。只能Move on了。楼主愿意说一下POI的回答思路吗， 我看到这个面经很多次了，但 ...

和你说的差不多 我也是说的GeoHashing然后讨论进度 存储， 基本和你说的一样

jordandong 发表于 2017-8-27 13:14
和你说的差不多 我也是说的GeoHashing然后讨论进度 存储， 基本和你说的一样

好的，谢谢楼主！

jordandong 发表于 2017-7-25 13:57
原理一样啊  不需要写iter出来， 直接往linkedlist尾巴上接就好了

请问楼主 如果判断读到的是一个integer还是一个linkedlist尼？利口是提供了一个interface, 那我们要自己写个interface吗？谢谢lz : )

LUOLUOLNSH 发表于 2017-8-29 20:28
请问楼主 如果判断读到的是一个integer还是一个linkedlist尼？利口是提供了一个interface, 那我们要自己 ...

是的 可以在结构里自己加一个TYPE

jordandong 发表于 2017-8-30 02:10
是的 可以在结构里自己加一个TYPE

lz能详细说说吗？所以应该是写一个interface 然后判断是interger还是linkedlist? 我只想到通过判断size来判断是integer还是linkedinlist