笔试加两轮面试总结

[xzpjerry731]

看了这么多面经，也应该来回馈社会了。面的某大厂 py

刚刚结束二面，不知道凉了没有。有个插曲，昨夜八九点发二面的通知让在昨晚 11 点前预约面试时间，我早早睡去没看到，早上打电话临时补约了下，估计给二面面试官不好的映像了，全程冷冷的 T_T

第 0 轮机考

• 转圈圈叫号，号码不符合条件的出列，看谁最后留下
• n 个一样的桶叠在一起，给你桶的容积，每个桶的初始水量和从最上面倒入的水，算到最下面那桶会溢出多少。
• 给你一个二叉树，左右交替打印每一层的节点值，第一层从左到右，第二层从右到左。。。。。。

第 1 轮电面

• 简历项目细节
• csrf 相关
• cookie 相关
• 链表和数组相关
• 哈希表相关
• 问我掌握的数据结构和算法
• 字符串匹配相关
• 每种树的应用场景

第 2 轮视频面

• 我最有成就的项目和细节（问的很深）
• xss
• 问我掌握的排序算法
• 快排原理
• 问我掌握的搜索算法
• bash 文本操作命令
• linux IPC
• 缓冲区溢出攻击
• 给我一个包含一亿条手机号的文件，让我找出出现次数前十的号码

一面面试官对我评价是基础扎实，二面面试官表示还需要加深（感觉凉了）

[pwrliang]

机考，是华为？

[Jacky23333]

想知道 1 亿个手机号码那道题的怎么做

[kaoshuiwan]

@Jacky23333 用前缀树应该可以吧 TrieTree, 大概 O(11n + 10^11)的复杂度？

[111qqz]

搜索算法是指什么？

[kaoshuiwan]

还得加个排序的耗时 /捂脸， 空间复杂度也有点大

[bbao]

@Jacky23333

1 亿个手机号，需要用到归并排序；
分 100 （ N)个文件，每个文件平均分配手机号；每个文件里面取前 10 名；
然后根据最终结果合并，再排序后前 10 名就是最终结果了；

[xzpjerry731]

@pwrliang #1 不是，现在大厂都搞机考吧。


@Jacky23333 #2 我一开始用优先队列做，是能做的，但是做完后他让我不要用别的模块，然后我就不会了。


@kaoshuiwan #3 我感觉这里用字典树好像没啥用吧，找出现次数第一可能可以，前十个我感觉不太行。

@111qqz #4 我反正就按数据类型分类回答，如果是二叉树怎么怎么地，数组的话怎么怎么地，字符串的话怎么怎么地

@bbao #6 感觉上可以嘢，我也有往这个方向想，但是没有想到每个文件取前十最后再汇总，学到了学到了

[kizunai]

睡这么早，一看就是不能加班的

[pwrliang]

一亿个手机号单机内存放的下，用 map 计数然后用 quick select 找 top 10?

[find]

一亿，手机号，每个手机号 11 char，也就一个 G，map 内存可以装 。二叉树，就一个 bfs

[meteor957]

csrf 相关
cookie 相关 有详细问题吗

[hq136234303]

java?

[xzpjerry731]

@kizunai #8 哈哈哈哈哈，也不是不能，就这几天准备面试从早学到晚有点疲劳

@pwrliang #9 我也有说到这个，但是后来觉得会很耗时吧

@find #10 您的意思是把手机号当字符串存二叉树里？然后怎么统计呢？

@meteor957 一开始是让我讲一讲原理，后来问了一些细节的问题我记不起来了，好像 cookie 问了 http-only

@hq136234303 #12 第一行写着 py 呀

[mrgeneral]

看题目感觉是校招题目，但是还有简历项目，这种有社会经历的不都是问项目和从业方向相关的吗？

[xzpjerry731]

@mrgeneral #14 是校招啦

[xupefei]

手机号可以用前缀树存，把计数放在叶子结点。最后返回 top k 叶子结点。

用前缀树的好处是空间小：手机号有 11 位，每位十个数字，空间绝对不超过 10^11，就算输入 100 亿个手机号也一样。

[luomu24]

校招项目问得这么细吗，没有项目的哭了。

[Allianzcortex]

@Jacky23333 应该是先回答 Trie，再加深多路归并，再多机器延伸到 MapReduce/RDD

[aguesuka]

一亿也就 100m，算上手机号长度大约是 1 个 g，全保存到 map 里。排序用优先队列，复杂度是 O(nm)n 是手机号数量，m 是前 m 个手机。

[aguesuka]

@bbao 这个方法是有问题的，每个文件必须取全部才能保证数据的正确性