马鬃五月vo

发一个上个月的马鬃虚拟现场
四轮每轮一小时，每轮都问了差不多三十分钟bq，然后才是技术题，这里有一个很有帮助的问题list，大家可以参考这个多想一想自己的小例子
https://www.youtube.com/watch?v= ... FYtGfixJDptRFGZccGQ

依 涉及题
artifacts 上传和下载系统 着重在api的设计和后端的搭建

而
蠡口 要司令 区别是直接给了一个list 要从中找到可以被break的word，比如 [rock, star, rockstar] => [[rock], [star], [rock, star, rockstar]]

散
数组 a and b, 判断b中的元素是不是都能在a中找到
第一问是如果要考虑重复怎么办 countsA[x] >= countsB[x]
第二问是如果a b不能放进内存怎么办
第三问是如果既不能放进内存 又不能排序（改变数组顺序）怎么办

肆

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

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

疫情期间找工不易 求大米！[/i][/i][/i]

mchzh 发表于 2020-6-12 02:21
你说得是布隆过滤不会出现在b中的数据？

6.给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

方案1：

分而治之/hash映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
hash_set统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
方案2：
如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
网上的这个题目好像和这个问题比较类似

mchzh 发表于 2020-6-11 12:15
三轮的第三问是不是需要hash到不同的server上处理呢？

忘记面试官具体是怎么说的了 我没有说map reduce的方法  说的是可以把b里面能放进内存的前k个keyword计数，然后在a中对这部分里的keywords 计数，找完再接下来讨论k+1个以后的keyword。方法比较笨
因为面试官好像问的是dict也很大不能一口气放进一个机器内存的情况

匿名者 发表于 2020-6-11 13:37
忘记面试官具体是怎么说的了 我没有说map reduce的方法  说的是可以把b里面能放进内存的前k个keyword计数 ...

如果a很大，对b中前k个keyboard去计数，a得不停的split成小文件再组合起来吧，跟external sort有相通的地方。那你的第二问应该是用的external sort吧

三轮的第三问是不是需要hash到不同的server上处理呢？

请问面那个组？

mchzh 发表于 2020-6-12 00:48
如果a很大，对b中前k个keyboard去计数，a得不停的split成小文件再组合起来吧，跟external sort有相通的地 ...

另外，如果涉及到外排序，还可以用布隆过滤掉。

草莓酱酱 发表于 2020-6-12 01:30
另外，如果涉及到外排序，还可以用布隆过滤掉。

你说得是布隆过滤不会出现在b中的数据？

好货，顶一个

关于第三问，如果不对精度100%， 可以用bloom filter