这是一个创建于 1725 天前的主题，其中的信息可能已经有所发展或是发生改变。
看了这么多面经，也应该来回馈社会了。面的某大厂 py
刚刚结束二面，不知道凉了没有。有个插曲，昨夜八九点发二面的通知让在昨晚 11 点前预约面试时间，我早早睡去没看到，早上打电话临时补约了下，估计给二面面试官不好的映像了，全程冷冷的 T_T
第 0 轮机考
- 转圈圈叫号，号码不符合条件的出列，看谁最后留下
- n 个一样的桶叠在一起，给你桶的容积，每个桶的初始水量和从最上面倒入的水，算到最下面那桶会溢出多少。
- 给你一个二叉树，左右交替打印每一层的节点值，第一层从左到右，第二层从右到左。。。。。。
第 1 轮电面
- 简历项目细节
- csrf 相关
- cookie 相关
- 链表和数组相关
- 哈希表相关
- 问我掌握的数据结构和算法
- 字符串匹配相关
- 每种树的应用场景
第 2 轮视频面
- 我最有成就的项目和细节（问的很深）
- xss
- 问我掌握的排序算法
- 快排原理
- 问我掌握的搜索算法
- bash 文本操作命令
- linux IPC
- 缓冲区溢出攻击
- 给我一个包含一亿条手机号的文件，让我找出出现次数前十的号码
一面面试官对我评价是基础扎实，二面面试官表示还需要加深（感觉凉了）
 |
1
pwrliang 2020-03-29 12:29:36 +08:00 via Android
机考，是华为？
|
 |
2
Jacky23333 2020-03-29 12:48:08 +08:00 via Android
想知道 1 亿个手机号码那道题的怎么做
|
 |
3
kaoshuiwan 2020-03-29 12:56:52 +08:00
@Jacky23333 用前缀树应该可以吧 TrieTree, 大概 O(11n + 10^11)的复杂度？
|
 |
4
111qqz 2020-03-29 13:01:45 +08:00 via Android
搜索算法是指什么？
|
|
5
kaoshuiwan 2020-03-29 13:01:59 +08:00
还得加个排序的耗时 /捂脸， 空间复杂度也有点大
|
 |
6
bbao 2020-03-29 13:03:37 +08:00
|
 |
7
xzpjerry731 OP @pwrliang #1 不是，现在大厂都搞机考吧。
@Jacky23333 #2 我一开始用优先队列做，是能做的，但是做完后他让我不要用别的模块，然后我就不会了。 @kaoshuiwan #3 我感觉这里用字典树好像没啥用吧，找出现次数第一可能可以，前十个我感觉不太行。 @111qqz #4 我反正就按数据类型分类回答，如果是二叉树怎么怎么地，数组的话怎么怎么地，字符串的话怎么怎么地 @bbao #6 感觉上可以嘢，我也有往这个方向想，但是没有想到每个文件取前十最后再汇总，学到了学到了 |
 |
8
kizunai 2020-03-29 13:30:40 +08:00  1
睡这么早，一看就是不能加班的
 |
|
9
pwrliang 2020-03-29 13:40:53 +08:00 via Android
一亿个手机号单机内存放的下，用 map 计数然后用 quick select 找 top 10?
|
 |
10
find 2020-03-29 13:49:41 +08:00 via iPhone
一亿，手机号，每个手机号 11 char，也就一个 G，map 内存可以装 。二叉树，就一个 bfs
|
 |
11
meteor957 2020-03-29 14:10:22 +08:00
csrf 相关
cookie 相关 有详细问题吗 |
 |
12
hq136234303 2020-03-29 14:35:23 +08:00
java?
|
|
13
xzpjerry731 OP @kizunai #8 哈哈哈哈哈，也不是不能，就这几天准备面试从早学到晚有点疲劳
@pwrliang #9 我也有说到这个，但是后来觉得会很耗时吧 @find #10 您的意思是把手机号当字符串存二叉树里？然后怎么统计呢？ @meteor957 一开始是让我讲一讲原理，后来问了一些细节的问题我记不起来了，好像 cookie 问了 http-only @hq136234303 #12 第一行写着 py 呀 |
 |
14
mrgeneral 2020-03-29 15:36:19 +08:00
看题目感觉是校招题目，但是还有简历项目，这种有社会经历的不都是问项目和从业方向相关的吗？
|
|
15
xzpjerry731 OP @mrgeneral #14 是校招啦
|
 |
16
xupefei 2020-03-29 18:30:35 +08:00 via iPhone
手机号可以用前缀树存，把计数放在叶子结点。最后返回 top k 叶子结点。
用前缀树的好处是空间小：手机号有 11 位，每位十个数字，空间绝对不超过 10^11，就算输入 100 亿个手机号也一样。 |
 |
17
luomu24 2020-03-29 22:24:07 +08:00
校招项目问得这么细吗，没有项目的哭了。
|
 |
18
Allianzcortex 2020-03-30 05:38:11 +08:00
@Jacky23333 应该是先回答 Trie，再加深多路归并，再多机器延伸到 MapReduce/RDD
|
 |
19
aguesuka 2020-03-30 11:41:08 +08:00 via Android
一亿也就 100m，算上手机号长度大约是 1 个 g，全保存到 map 里。排序用优先队列，复杂度是 O(nm)n 是手机号数量，m 是前 m 个手机。
|
|
21
bbao 2020-03-30 13:56:22 +08:00
@aguesuka 如果其他文件连前 10 都排不上，我要这个数据没用；如果在其他文件排到了前十之后，整体文件汇总求和再重新排序取前十，没有问题；
|
|
22
aguesuka 2020-03-30 17:10:31 +08:00 via Android
@bbao 举个例子，只有 10 个手机号出现了 2 次，其它所有都是 1 次，你的算法能把这 10 个手机号都找出来吗？
|
 |
23
rannie 2020-03-30 17:38:02 +08:00
10 亿手机号用 bit set 存就行
|
|
24
bbao 2020-03-31 09:21:41 +08:00
@aguesuka 海量数据有海量数据的计算方法； 10 个数据有 10 个数据的计算方法；
我给你加一个限制； 64M 内存的机器； 1 亿手机号，你看看你的计算方式能算，还是我的计算方式能算； 手机号再多一些，10 亿手机号，是你的更快一些，还是我的更快。 你这不是纯抬扛么同学. |
 |
25
diveIntoWork 2020-03-31 16:52:38 +08:00
一亿手机号，一行 shell 搞定
cat $inputfile | tr -s ' ' '\n' | sort -f | uniq -c | sort -r | head -n 10 | awk '{print $2, $1}' |
Select Language