狗家VO

刚面的L5，趁着还记得赶紧上面经，还热乎的
1. Coding 华人大哥，上来二话不说直接做题，很好很直接，帮我省时间了
Given a stream of prices from transactions: 79.20, 20.05, 96.82, ...
Implement 2 methods:
  1) insert(price)
  2) query(percentile) - e.g.: query(0.2) should give a price that 20% of prices is lower than it, 80% of prices should be higher than it
演了一下，讲了一下insertion sort还有BST的解法，大哥开始提示了，心领神会上segment tree然后卡着点写完。

2. Coding 印度大哥，也是上来直接做题
N cities from 1 to N, each city has either landmark A or B
return true if there is a path from x to y so that path has either A or B landmark, otherwise return false
example:
Landmarks: 1:A,2:B,3:B,4:A,5:A
Paths:
1-2
1-5
3-4
3-5
4-5
from 1 to 4 -> 1,5,4 (x) but 1,5,3,4 (y) so return true
差不多就是DFS把可能的path都找一遍，写完和面试官dry run一下，修了俩小bug然后到时间

3. Design 毛子口音的大哥，不确定哪里人，不敢问
Design a key-value store
50 billion key-value pairs
1000 QPS
No writes
key: string - 20 bytes
value: string - 1

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

D message过来，后来发现要“尽快”，也就是在time=5的时候要能determine RPC2 timeout。修修改改最后用PriorityQueue去存endTime。

题都跌跌爬爬做出来了，design自觉也还行，希望能有好结果吧。


补充内容 (2022-03-08 11:41 +8:00):
额，晚上recruiter来邮件说可以move forward了，是送HC的意思吗？现在狗家都这么快了吗？

魔群月光 发表于 2022-03-08 06:35:16
想问下如果用价格做区间的话，query怎么求任意ratio的price呢？一般我用segment tree都是求最值或者是和。

和之前BST的方法一样还是数节点…比如根节点告诉我一共有100个价格，现在percentile是0.2的话就找20个最小的然后输出第21个价格。所以我也没懂为啥要用到segment tree

Bencat 发表于 2022-03-07 16:27:22
Segment Tree已经是必须掌握还能写出来的要求了吗？

我感觉是的，不然凭空现场撸一个出来实在不人道…

匿名者 发表于 2022-3-24 16:49
想问一下第一题为啥不能用treemap之类的做啊？直接每次insert进去就是sorted，然后找百分之二十，百分之三 ...

可以这么做呀，我就是这么做的，但是也不知道为啥面试官不太满意的样子，问我有没有更好的办法
我能想到的treemap可能有的问题就是如果input里面重复很多的话，treemap会不太有效，所以我后来用的方法就是treemap<node>, node里面有value和一个counter用来记录重复次数。
但是面试官还是让我再想想，想不出来了

Segment Tree已经是必须掌握还能写出来的要求了吗？

楼主太强了。。膜拜。能问下这题用segment tree怎么写吗？

一个segment代表一个percentile range吗？但是update number这一步好难写啊。

不太懂第一题为啥是segment tree。没看到区间啊？我觉得bst或者跳表之类的搜索不好吗？

sccnju 发表于 2022-3-7 19:16
楼主太强了。。膜拜。能问下这题用segment tree怎么写吗？

一个segment代表一个percentile range吗？但 ...

没有。。。我完全是临时抱佛脚，昨天才在看花花酱讲这个。。。
我大概的思路其实就是extend一个BST，只不过每个节点记一下子树的节点数，这样的话根节点里面就是所有price的个数了，query的时候根据percentile和总个数可以知道要找第几个节点上的价格，然后binary search找过去就好。我自己都不确定这算不算segment tree。。。

羡慕LZ，面完一周了还说在收集feedback...可能有一轮面的不好吧

魔群月光 发表于 2022-3-7 19:36
不太懂第一题为啥是segment tree。没看到区间啊？我觉得bst或者跳表之类的搜索不好吗？

哎呀兄弟你可算是说到点子上了，我也是一开始用bst做的，结果面试官大哥还在问有没有其他办法，我给整没辙了就写了个segment tree，我真心觉得和bst完全没差。。。

eggrice 发表于 2022-3-7 19:50
羡慕LZ，面完一周了还说在收集feedback...可能有一轮面的不好吧

谢谢，可能各个recruiter风格不同吧，祝你好运！

lz厉害，加米了，
第一个直接用个priority queue之类的不行吗。线段树啥的完全不会。