1、腾讯 2019 秋招后台研发工程师面试经验后台研发工程师，C+和 Java 方向。腾讯先是腾讯云，存储方向的部门面的，全程在问 C+，我说明自己很久不用 C+了，面试官开始问我很多基础，不过当我说到 Java 一些术语，面试官一脸懵逼，他说的一些术语，我也一脸懵逼，就这么尴尬了一个小时，哈哈，不过算法题和基础知识答得还不错。字符串判断包含判断一棵树是不是另一个子树大头传输和小头传输三次握手，滑动窗口epoll，select 模型TCP 和 UDP Linux top 和 ps操作日志的一些指令红黑树SortSet进程通信的方式，哪种方式速度最快后来部门转到了 TEG，直播方向，这次是 Java
2、，全程很顺利，面试官的问题基本答得都不错。主要是 Java 相关的技术，包括 JVM，还有 hashmap 原理，1.7 和 1.8 的区别，字节移位，主要涉及一道 bitmap 的题目。MapReduce 是一种编程模型，用于大规模数据集（大于 1TB）的并行运算。概念Map（映射）和Reduce（归约）Bit-map 空间压缩和快速排序去重1. Bit-map 的基本思想32 位机器上，对于一个整型数，比如 int a=1 在内存中占 32bit 位，这是为了方便计算机的运算。但是对于某些应用场景而言，这属于一种巨大的浪费，因为我们可以用对应的 32bit 位对应存储十进制的 0-31 个
3、数，而这就是 Bit-map 的基本思想。Bit-map 算法利用这种思想处理大量数据的排序、查询以及去重。Bitmap 在用户群做交集和并集运算的时候也有极大的便利。2. Bit-map 应用之快速排序假设我们要对 0-7 内的 5 个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）,我们就可以采用 Bit-map 的方法来达到排序的目的。要表示 8 个数，我们就只需要 8 个 Bit （1Bytes），首先我们开辟 1Byte 的空间，将这些空间的所有 Bit 位都置为 0，对应位设置为 1:遍历一遍 Bit 区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序
4、的目的，时间复杂度 O(n)。优点：运算效率高，不需要进行比较和移位；占用内存少，比如 N=10000000；只需占用内存为 N/8=1250000Byte=1.25M。缺点：所有的数据不能重复。即不可对重复的数据进行排序和查找。3. Bit-map 应用之快速去重2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这 2.5 亿个整数。首先，根据“内存空间不足以容纳这 2.5 亿个整数”我们可以快速的联想到 Bit-map。下边关键的问题就是怎么设计我们的 Bit-map 来表示这 2.5 亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。
5、因此，我们只需要 2bits 就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为 00，存在一次 01，存在两次及其以上为 11。那我们大概需要存储空间几十兆左右。接下来的任务就是遍历一次这 2.5 亿个数字，如果对应的状态位为 00，则将其变为01；如果对应的状态位为 01，则将其变为 11；如果为 11，,对应的转态位保持不变。最后，我们将状态位为 01 的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。4. Bit-map 应用之快速查询同样，我们利用 Bit-map 也可以进行快速查询，这种情况下对于一个数字只需要一个 bit 位就可以了，0 表示不存在，1 表示
6、存在。假设上述的题目改为，如何快速判断一个数字是够存在于上述的 2.5 亿个数字集合中。同之前一样，首先我们先对所有的数字进行一次遍历，然后将相应的转态位改为 1。遍历完以后就是查询，由于我们的 Bit-map 采取的是连续存储（整型数组形式，一个数组元素对应 32bits），我们实际上是采用了一种分桶的思想。一个数组元素可以存储 32 个状态位，那将待查询的数字除以 32，定位到对应的数组元素（桶），然后再求余（%32），就可以定位到相应的状态位。如果为 1，则代表改数字存在；否则，该数字不存在。5. Bit-map 扩展Bloom Filter(布隆过滤器)当一个元素被加入集合中时,通过
7、k 各散列函数将这个元素映射成一个位数组中的 k 个点,并将这 k 个点全部置为 1.有一定的误判率-在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误判为属于这个集合.因此,它不适合那些零误判的应用场合.在能容忍低误判的应用场景下,布隆过滤器通过极少的误判换区了存储空间的极大节省.Bloom Filter 使用 k 个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到1,m,的范围中。对任意一个元素 x，第 i 个哈希函数映射的位置 hi(x)就会被置为 1（1ik）。注：如果一个位置多次被置为 1，那么只有第一次会起作用，后面几次将没有任何效
8、果。在判断 y 是否属于这个集合时，对 y 应用 k 次哈希函数，若所有 hi(y)的位置都是 1（1ik），就认为 y 是集合中的元素，否则就认为 y 不是集合中的元素。6. 总结使用 Bit-map 的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。Bloom Fliter 是 Bit-map 思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构。7. 应用适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是 int 的 10 倍以下基本原理及要点：使用 bit 数组来表示某些元素是否存在，比如 8 位
9、电话号码扩展：bloom filter 可以看做是对 bit-map 的扩展问题实例：1、已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。8 位最多 99 999 999，大概需要 99m 个 bit，大概 10 几 M 字节的内存即可。2、在 2.5 亿个整数中找出不重复的整数，内存不足以容纳这 2.5 亿个整数。方案 1：采用 2-Bitmap（每个数分配 2bit，00 表示不存在，01 表示出现一次，10 表示多次，11 无意义）进行，共需内存 232*2bit=1GB 内存，还可以接受。然后扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，如果是 00 变 01，01 变 10，10 保持不变。所描完事后，查看 bitmap，把对应位是 01 的整数输出即可。
