系列文章目录

第一篇：语言基础

第二篇：设计模式

第三篇：数据库

第四篇：计算机网络

第五篇：操作系统

第六篇：LInux

第七篇：数据结构

第八篇：智力题

[1]int (*s[10])(int) 中s表示的是什么？

函数指针数组，每个指针指向一个int func(int param)的函数。

[2]strcpy函数

已知strcpy函数的原型是char *strcpy(char *strDest, const char *strSrc);其中strDest是目的字符串，strSrc是源字符串。（1）不调用C++/C的字符串库函数，请编写函数 strcpy

（2）strcpy能把strSrc的内容复制到strDest，为什么还要char * 类型的返回值？为了 实现链式表达式。

错误：

正确：

strlen()

strcat()

strcmp()

[3]实现⼀个内存安全的memcpy函数

链接

[4]strcpy和memcpy的区别是什么吗

1、复制的内容不同。strcpy只能复制字符串，而memcpy可以复制任意内容，例如字符数组、整型、结构体、类等。2、复制的方法不同。strcpy不需要指定长度，它遇到被复制字符的串结束符"\0"才结束，所以容易溢出。memcpy则是根据其第3个参数决定复制的长度。3、用途不同。通常在复制字符串时用strcpy，而需要复制其他类型数据时则一般用memcpy

[5]strcpy函数和strncpy函数的区别？哪个函数更安全

strncpy

[6]static_cast比C语言中的转换强在哪里？

1. 更加安全；
2. 更直接明显，能够一眼看出是什么类型转换为什么类型，容易找出程序中的错误；
3. 可读性更好，能体现程序员的意图

[7]什么是一致性哈希？

一致性哈希是一种哈希算法，就是在移除或者增加一个结点时，能够尽可能小的改变已存在key的映射关系，，一般是沿着顺时针进行操作，

[8]用C++设计一个不能被继承的类

注 意 ： 构 造 函 数 是 继 承 实 现 的 关 键 ， 每 次 子 类 对 象 构 造 时 ， 首 先 调 用 的 是 父 类 的 构 造 函 数 ， 然 后 才 是 自 己 的 。

[9]正向拷贝和逆向拷贝copy()和copy_backward()

逆向拷贝是从源容器的结尾开始进行拷贝，拷贝完的数据顺序不变。

[10]如何在不使用额外空间的情况下，交换两个数？你有几种方法

x=x^yy=x^yx=x^yy= x^yx=x^y

[11]100层楼和两个玻璃球思路解析

链接

[12]36匹马6个跑道求前3匹：8次

[13]二叉树为什么前序和后序确定不了一棵树

linux系统上一个进程能启动的默认线程数是1024个

[14]场景设计题

链接

[15]10亿个数排序

先划分成多个小文件，送进内存排序，然后再采用多路归并排序。

[16]100亿个数据中找出最大的1000个

链接采用分区法+小顶堆法

将100亿个数据分成1000个分区，每个分区上1000万个数据，在每个分区上上再细分成100个分区，即总共分成1000*100个分区，然后启动多线程进行处理，各个分区上采用小顶堆算法取出最大的1000个数据，分层进行合并然后重新计算不同层上的最大1000个数，最终递归到最上层。

[17]有一个包含 10 亿个搜索关键词的日志文件，如何快速获取到 Top 10 最热门的搜索关键词呢相同数据经过哈希算法得到的哈希值是一样的

创建 10 个空文件 00，01，02，……，09。我们遍历这 10 亿个关键词，并且通过某个哈希算法对其求哈希值，相同则统计个数，然后哈希值同 10 取模，得到的结果就是这个搜索关键词应该被分到的文件编号。

针对每个包含 1 亿条搜索关键词的文件，利用散列表和堆，分别求出 Top 10，然后把这个 10 个 Top 10 放在一块，然后取这 100 个关键词中，出现次数最多的 10 个关键词，这就是这 10 亿数据中的 Top 10 最频繁的搜索关键词（也可以吧堆转化为归并排序）

[18]在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可内存够：

可以使⽤用类似quick sort的思想进行，均摊复杂度为O(n)，算法思想如下：• 随机选取一个元素，将比它小的元素放在它左边，比它大的元素放在右边• 如果它恰好在中位数的位置，那么它就是中位数，可以直接返回• 如果小于它的数超过一半，那么中位数一定在左半边，递归到左边处理• 否则，中位数一定在右半边，根据左半边的元素个数计算出中位数是右半边的第几大，然后递归 到右半边处理内存不够：若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存

堆排序在数据量很大的时候，可以实现「在线算法」，不用一下子把所有数据读入内存

（1）读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。

说明：整数范围是0 - 2^32 - 1，一共有4G种取值，映射到256M个区段，则每个区段有16(4G/256M = 16)种值，每16个值算一段， 0～15是第1段，16～31是第2段，……2^32-16 ～2^32-1是第256M段。一个64位无符号整数最大值是0～8G-1，这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。

（2）从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段(即累加停止时达到的区段，也是中位数所在的区段)的数值范围，设为[a，a+15]，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。

（3）再读一遍10G个整数，把在[a，a+15]内的每个值计数，即有16个计数。

（4）对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数

[19]如果让你来开发微信抢红包，说说你的思路是怎么样的？可能遇到什么问题，你会怎么解决因为微信群的人数有限，所以抢红包不存在高并发的情况。

一个人成功抢到红包，会在一个表示成功抢到红包的表中插入一条记录，包括用户id，金额等。每次抢红包，首先判断是否还有红包，金额、数量是否为0，为0返回失败，不为0则判断是否已经抢到红包。若没有抢到红包，利用2倍均值法生成红包金额，写入表若已经抢到红包，提示已抢到红包

额度在0.01和剩余平均值*2之间。到了最后面如果不够这么算，那么会采取如下算法：保证剩余用户能拿到最低1分钱即可。链接

微信的金额什么时候算？微信红包的金额是拆的时候实时算出来，不是预先分配的，采用的是纯内存计算，不需要预算空间存储。采取实时计算金额的考虑，是因为实时效率很高，而预算需要占存储，预算空间效率低。链接

红包的设计微信从财付通拉取金额数据过来，生成个数/红包类型/金额放到redis集群里，app端将红包ID的请求放入请求队列中，如果发现超过红包的个数，直接返回。根据红包的逻辑处理成功得到令牌请求，则由财付通进行一致性调用，通过像比特币一样，两边保存交易记录，交易后交给第三方服务审计，如果交易过程中出现不一致就强制回归。红包如何计算被抢完？

cache会抵抗无效请求，将无效的请求过滤掉，实际进入到后台的量不大。cache记录红包个数，原子操作进行个数递减，到0表示被抢光。财付通按照20万笔每秒入账准备，但实际还不到8万每秒。如何保持8w每秒的写入？多主sharding，水平扩展机器。数据容量多少？一个红包只占一条记录，有效期只有几天，因此不需要太多空间。查询红包分配，压力大不？抢到红包的人数和红包都在一条cache记录上，没有太大的查询压力。一个红包一个队列？没有队列，一个红包一条数据，数据上有一个计数器字段。有没有从数据上证明每个红包的概率是不是均等？不是绝对均等，就是一个简单的拍脑袋算法。拍脑袋算法，会不会出现两个最佳？会出现金额一样的，但是手气最佳只有一个，先抢到的那个最佳。每领一个红包就更新数据么？每抢到一个红包，就cas更新剩余金额和红包个数。红包如何入库入账？数据库会累加已经领取的个数与金额，插入一条领取记录，入账则是后台异步操作。入帐出错怎么办？比如红包个数没了，但余额还有？最后会有一个take all操作，另外还有一个对账来保障。

[20]秒杀系统相关问题

Nginx服务器并发量达到几万，tomcat访问量几百。通过nginx映射客户端请求，再分发到后台tomcat服务器集群中可以大大提升并发能力。秒杀系统的设计方案

[续]C++岗位求职面试八股文第三十九篇（综合+智力题）