f*****6
发帖数: 61 | 1 看了版上很多面经了，也来回馈下。
第一轮三哥，给一个list里面都是string，每个string是有字母和‘.'组成，然后给另
外的一些string，判断在不在字典里。
第二轮还是三哥，给一个integer的array，给个element代表柱子的高度，下雨后能
capture多少水，优化到O(n) time, O(1) space.
第三轮华裔abc的hiring manager聊了半小时，好像不算在面试流程里。。。
第四轮system design白人大叔， 有个function是List getNearest(int x, int y
){}, 假设从mobile上在地图上点一下，然后返回改点附近的所有建筑location。怎么
设计data structure以及data scheme
第五轮behaviour白人，半个多小时behavior加两数相除不用除号。 |
A*******e
发帖数: 2419 | 2
.是通配符？
这个是LC hard吧。
y
quad-tree？
【在 f*****6 的大作中提到】
: 看了版上很多面经了，也来回馈下。
: 第一轮三哥，给一个list里面都是string，每个string是有字母和‘.'组成，然后给另
: 外的一些string，判断在不在字典里。
: 第二轮还是三哥，给一个integer的array，给个element代表柱子的高度，下雨后能
: capture多少水，优化到O(n) time, O(1) space.
: 第三轮华裔abc的hiring manager聊了半小时，好像不算在面试流程里。。。
: 第四轮system design白人大叔， 有个function是List getNearest(int x, int y
: ){}, 假设从mobile上在地图上点一下，然后返回改点附近的所有建筑location。怎么
: 设计data structure以及data scheme
: 第五轮behaviour白人，半个多小时behavior加两数相除不用除号。
|
J*******o
发帖数: 741 | 3 算法题好像没有很难， design应该怎么分析呀？ |
s********l
发帖数: 998 | 4 赞面经
能说说第四轮是怎么设计的吗？
谢谢
y
【在 f*****6 的大作中提到】
: 看了版上很多面经了，也来回馈下。
: 第一轮三哥，给一个list里面都是string，每个string是有字母和‘.'组成，然后给另
: 外的一些string，判断在不在字典里。
: 第二轮还是三哥，给一个integer的array，给个element代表柱子的高度，下雨后能
: capture多少水，优化到O(n) time, O(1) space.
: 第三轮华裔abc的hiring manager聊了半小时，好像不算在面试流程里。。。
: 第四轮system design白人大叔， 有个function是List getNearest(int x, int y
: ){}, 假设从mobile上在地图上点一下，然后返回改点附近的所有建筑location。怎么
: 设计data structure以及data scheme
: 第五轮behaviour白人，半个多小时behavior加两数相除不用除号。
|
w****3
发帖数: 232 | 5 第二题要O(1)的空间啊，这个怎么搞？
【在 A*******e 的大作中提到】
:
: .是通配符？
: 这个是LC hard吧。
: y
: quad-tree？
|
m********o
发帖数: 26 | |
f*****6
发帖数: 61 | 7 感觉基本要挂。说最晚这周有消息。。
【在 m********o 的大作中提到】
: 大神结果如何？
|
w****3
发帖数: 232 | 8 能说说第二题吗？怎么样做到O(1)的空间复杂度啊？
【在 f*****6 的大作中提到】
: 感觉基本要挂。说最晚这周有消息。。
|
A*********c
发帖数: 430 | 9 第一题什么意思？
y
【在 f*****6 的大作中提到】
: 看了版上很多面经了，也来回馈下。
: 第一轮三哥，给一个list里面都是string，每个string是有字母和‘.'组成，然后给另
: 外的一些string，判断在不在字典里。
: 第二轮还是三哥，给一个integer的array，给个element代表柱子的高度，下雨后能
: capture多少水，优化到O(n) time, O(1) space.
: 第三轮华裔abc的hiring manager聊了半小时，好像不算在面试流程里。。。
: 第四轮system design白人大叔， 有个function是List getNearest(int x, int y
: ){}, 假设从mobile上在地图上点一下，然后返回改点附近的所有建筑location。怎么
: 设计data structure以及data scheme
: 第五轮behaviour白人，半个多小时behavior加两数相除不用除号。
|
f*****6
发帖数: 61 | 10 design还是不行。主要就分析怎么存data能够更快拿到near location，key是坐标，
value是location的一系列property，以及高并发后怎么能设计cache使响应更快，
cache里维护一个堆，问题是这个nearest定义很模糊不是要求多少范围内，所以我说要
设计一个active的heap来，但是坐标x和y可以是整数或小数，所以我说按照整数的范围
来aggregate所有location然后合并成key是(x,y)value是一个list含有很多location，
总之答的很乱，最后还是写了些简单的数学公式。。。存粹乱写的。。
【在 J*******o 的大作中提到】
: 算法题好像没有很难， design应该怎么分析呀？
|
|
|
f*****6
发帖数: 61 | 11 就是给你很多string，建个trie tree，然后给你一些另外的string，里面包含'.'点可
以match任何字幕，判断给的string在不在trie里
【在 A*********c 的大作中提到】
: 第一题什么意思？
:
: y
|
f*****6
发帖数: 61 | 12 找到最高的那根柱子，把array分成左右两部分，分别从左往右到最高的那根柱子为止
，然后从右往左到最高的柱子为止，然后计算的结果累加起来。
【在 w****3 的大作中提到】
: 能说说第二题吗？怎么样做到O(1)的空间复杂度啊？
|
f*****6
发帖数: 61 | 13 第二题还有个follow up如果array里面有0表示从左右高点到0处包含的水会留空，求所
有能包含的水 |
k******a
发帖数: 44 | 14 设计题就是F常见的POI吧，我的思路。
看过以前的文章，主要是用geohash将二维坐标转换为一维的数值或者字符串。
以后就好办了，将所有已知数据（key-value）保存在distriubted key-value map
这样，取某个点所在区域，以及周边区域的数据都是可以并行进行的。
用 cache 提高存取速度。利用LRU算法维护，保证热点地区的数据总在cache。
用map/reduce同时查找多个周边地区，然后汇总。 |
s********l
发帖数: 998 | 15 请问是什么文章啊？ 什么名吗？
谢谢
【在 k******a 的大作中提到】
: 设计题就是F常见的POI吧，我的思路。
: 看过以前的文章，主要是用geohash将二维坐标转换为一维的数值或者字符串。
: 以后就好办了，将所有已知数据（key-value）保存在distriubted key-value map
: 这样，取某个点所在区域，以及周边区域的数据都是可以并行进行的。
: 用 cache 提高存取速度。利用LRU算法维护，保证热点地区的数据总在cache。
: 用map/reduce同时查找多个周边地区，然后汇总。
|
e***i
发帖数: 231 | 16 geohash O(1)
k-d tree O(lgn)
【在 s********l 的大作中提到】
: 请问是什么文章啊？ 什么名吗？
: 谢谢
|
A*********c
发帖数: 430 | 17 阿三真尼玛会玩，还带上下水道了。
【在 f*****6 的大作中提到】
: 第二题还有个follow up如果array里面有0表示从左右高点到0处包含的水会留空，求所
: 有能包含的水
|
s********l
发帖数: 998 | 18 请问这个怎么解的？这个还要O(1)吗？
【在 f*****6 的大作中提到】
: 第二题还有个follow up如果array里面有0表示从左右高点到0处包含的水会留空，求所
: 有能包含的水
|
l******s
发帖数: 3045 | 19 第二轮的题的水是积在Bar上？还是Bar只是拦水用的？ |
m******3
发帖数: 346 | 20 同问，楼主能说说么？
【在 s********l 的大作中提到】
: 请问这个怎么解的？这个还要O(1)吗？
|
|
|
l*****z
发帖数: 3022 | 21 我感觉这根原题一样啊。就是多一步一开始扫描一遍，把0的地方当作分段线，原数组
分成多个被0隔开的数组处理就好了。
【在 s********l 的大作中提到】
: 请问这个怎么解的？这个还要O(1)吗？
|
f*****6
发帖数: 61 | 22 嗯是的
【在 l*****z 的大作中提到】
: 我感觉这根原题一样啊。就是多一步一开始扫描一遍，把0的地方当作分段线，原数组
: 分成多个被0隔开的数组处理就好了。
|
m******3
发帖数: 346 | 23 这个是不是就是对trie尝试DFS啊，如果遇到.就是沿着所有的child尝试？
【在 f*****6 的大作中提到】
: 就是给你很多string，建个trie tree，然后给你一些另外的string，里面包含'.'点可
: 以match任何字幕，判断给的string在不在trie里
|
m******g
发帖数: 3924 | |
s******x
发帖数: 417 | 25 不是文章，而是一本书，叫做HBase in Action，第八章还是第几章，专门有讲这个。
【内心独白】我这算是为马上要到来的FB面试攒人品了吧。。。。 |
s********l
发帖数: 998 | 26 是啊是啊~
祝妹纸 拿offer~
【在 s******x 的大作中提到】
: 不是文章，而是一本书，叫做HBase in Action，第八章还是第几章，专门有讲这个。
: 【内心独白】我这算是为马上要到来的FB面试攒人品了吧。。。。
|
b*****n
发帖数: 618 | 27 如果你的意思是用mapreduce framwork
这个应该是不work的。。
这个我猜题目的要求应该是realtime system不是batch system
如果用mapreduce做precomputation还勉强可以
【在 k******a 的大作中提到】
: 设计题就是F常见的POI吧，我的思路。
: 看过以前的文章，主要是用geohash将二维坐标转换为一维的数值或者字符串。
: 以后就好办了，将所有已知数据（key-value）保存在distriubted key-value map
: 这样，取某个点所在区域，以及周边区域的数据都是可以并行进行的。
: 用 cache 提高存取速度。利用LRU算法维护，保证热点地区的数据总在cache。
: 用map/reduce同时查找多个周边地区，然后汇总。
|
