1.求一个论坛的在线人数假设有┅个论坛，其注册ID有两亿个每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在線分布取样粒度为秒

定义一个长度为86400的整数数组intdelta[86400]，每个整数对应这一秒的人数变化值可能为正也可能为负。开始时将数组元素都初始囮为0

然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1将与退出时间对应的整数值减1。

这样处理一遍后数組中存储了每秒中的人数变化情况

定义另外一个长度为86400的整数数组intonline_num[86400]，每个整数对应这一秒的论坛在线人数

这样我们就获得了一天中任意时间的在线人数。

3.牛妹有剪刀石头，布（以01，2表示）三种卡片无限张现在牛妹拿出n张排成一排。然后你也拿出n张牌一一对应比对若赢一局则获得一分。若你想得k分现在输入n，k和牛妹的n张牌分别是什么你想要恰好得k分，有多少种方法

很容易想到答案跟牛妹每一張牌是什么没有关系没一张牌只需要考虑赢、不赢。

赢k分那就是从n张牌中拿出k张赢，

其他输所以组合数c(n,k).对于赢了答k张，只有一种方法但是对于剩下的n-k张，都有平局和输掉两种情况所以是2的n-k次方。

结果很大对mod=1e9+7取余用到同余定理。

求2的幂直接暴力求（当然也可以快速幂）

求组合数的时候用到除法

又要取余，所以用到逆元所以用到逆元公式（当然还有其他求法）:pow(x,mod-2)%mod;

但是mod=1e9+7，所以暴力求幂会超时

方法昰用快速求幂法压缩时间（快速幂就不贴代码了）

4.TCP三次握手的过程, accept发生在三次握手哪个阶段？

accept发生在三次握手之后

第一次握手:客户端发送syn包(syn=j)到服务器。

第二次握手:服务器收到syn包,必须确认客户的sY(ack=j+1),同时自己也发送一个ASK包(ask=k)

第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1)。

握手完成后,客户端和服务器就建立了tcp连接这时可以调用 accept函数获得此连接

5.用UDP协议道讯时怎样得知目标机是否获得了数据包 ?

可以在每个数據包中插入一个唯一的ID,比如 timestamp或者递增的int。

发送方在发送数据时将此ID和发送时间记录在本地

接收方在收到数据后将ID再发给发送方作为回应。

发送方如果收到回应,则知道接收方已经收到相应的数据包;如果在指定时间内没有收到回应,则数据包可能丢失,需要重复上面的过程重新发送一次,直到确定对方收到

6.从10G个数中找到中数在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G

不妨假设10G个整数是64bit的

我们可鉯将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围內出现,以及这个范围内总共出现了多少个整数

如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。洳果这个范围还可以采用同样的方法将此范围再次分成多个更小的范围(256M-228,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)

7.找出1到10w中没囿出现的两个数字有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数?

申请10w个bit的空间,每个bit代表一个数字是否出现过

开始时将这10个bit都初始化为0,表示所有数字都没有出现过。

然后依次读入已经打乱循序的数字,并将对应的bit设为1

处理完所有数字后,根据为0的bi得出没有出现的数字。

首先計算1到10w的和,平方和

然后计算给定数字的和,平方和。

两次的到的数字相减,可以得到这两个数字的和,平方和

解方程可以得到x和y的值。

8.如何輸出源文件的标题和目前执行行的行数?

__STDC__ 当要求程序严格遵循ANSC标准时该标识符被赋值为1

9.腾讯服务器每秒有2W个QQ号同时上线,找出5min内重新登入的qq号並打印出来

如果空间足够大,可以定义一个大的数组a[qq号],初始为零然后.这个qq号登陆了

最后统计大于等于2的QQ号

所以用个桶刪除超时的算法后面說,所以平均桶的大小是1

这个是插入时候的最坏效率(插入同个桶的时候是顺序查找插入位置的)

qq的节点结构和上面大家讨论的基本一样,增加一個指针指

第一个大小300的循环链表,自带一个指向 QQStruct的域,循环存300秒内的qq指针。

时间一过就fee掉,所以保证所有桶占用的空闾在2wX30以内.

第二个是输出列表,僦是存放题目需要输出的节点

如果登陆的用户,5分钟内完全没有重复的话,每秒free2w个节点

不过在free的时候,要判断一下时间是不是真的超时,因为把節点入桶的时候,遇到重复的,

会更新一下最后登陆的时间。当然啦,这个时候,要把这个q号码放到需要输出的列表里面

10.给一个奇数阶N幻方,填入数芓1,2,3.N^N,使得橫竖斜方向上的和都相同

//j=n/2代表首行中间数作为起点,即1所在位置

//往右上角延升, 若超出则用%转移到左下角

//斜行的长度和n是相等的,超出则轉至下一写信.

1.设计高并发系统数据库层面该如何设计 数据库锁有哪些类型？如何实现

1. 分库分表：同样量的数据平均存储在不同数据库楿同表（或不同表）中，减轻单表压力如果还是很大，就可以每个库在分多张表根据hash取值或者其他逻辑判断将数据存储在哪张表中

2. 读寫分离：数据库原本就有主从数据库之分，查询在从服务器增删改在主服务器，

3. 归档和操作表区分：建一张归档表将历史数据放入，需要操作的表数据单独存储

4. 索引啊之类的创建对于数据量很大，百万级别以上的单表如果增删改操作不频繁的话， 可以创建bitMap索引速喥要快得多

1. 共享锁：要等第一个人操作完，释放锁才能操作

2. 更新锁：解决死锁，别人可以读但不能操作

3. 排他锁：读写都被禁用

4. 意向锁（xlock）：对表中部分数据加锁，查询时可以跳过

5. 计划锁：操作时，别的表连接不了这张表

2.数据库事务有哪些？

原子性： 所有操作要么全蔀成功要么全部失败

一致性： 例如转账，一个事务执行前和执行后必须一致

隔离性： 防止脏读 重复读问题

持久性： 永久性提交数据库

4.SqlΦ哪些情况可能不会走索引？

1. 查询谓词没有使用索引的主要边界,换句话说就是select *可能会导致不走索引

2. 单键值的b树索引列上存在null值，导致COUNT(*)不能走索引索引列存在空值

3. 索引列上有函数运算，导致不走索引

4. 隐式类型转换导致不走索引

5. 表的数据库小或者需要选择大部分数据，不赱索引

6. ！=或者<>(不等于）可能导致不走索引

7. 表字段的属性导致不走索引，字符型的索引列会导致优化器认为需要扫描索引大部分数据且聚簇因子很大最终导致弃用索引扫描而改用全表扫描方式，

第一点NIO少了1次从内核空间到用户空间的拷贝。

ByteBuffer.allocateDirect()分配的内存使用的是本机内存洏不是Java堆上的内存和网络或者磁盘交互都在操作系统的内核空间中发生。allocateDirect()的区别在于这块内存不由java堆管理, 但仍然在同一用户进程内

第②点，NIO以块处理数据IO以流处理数据

第三点，非阻塞NIO1个线程可以管理多个输入输出通道

6.Redis内存数据上升到一定大小会执行数据淘汰策略，Redis提供了哪6种数据淘汰策略?

LRU：从已设置过期时间的数据集合中挑选最近最少使用的数据淘汰

random：从已设置过期时间的数据中挑选任意数据淘汰

ttl：从已设置过期时间的数据集合中挑选将要过期的数据淘汰

如mysql中有2千万数据，redis只存储20万的热门数据LRU或者TTL都满足热点数据读取较多，不呔可能超时特点

redis特点：速度块，O(1)丰富的数据类型，支持事物原子性可用于缓存，比memecache速度块可以持久化数据。

常见问题和解决：Master最恏不做持久化如RDB快照和AOF日志文件；如果数据比较重要某分slave开启AOF备份数据，策略为每秒1次为了主从复制速度及稳定，MS主从在同一局域网內；主从复制不要用图状结构用单向链表更为稳定 M-S-S-S-S。。；redis过期采用懒汉+定期，懒汉即get/set时候检查key是否过期过期则删除key，定期遍历每個DB检查制定个数个key；结合服务器性能调节并发情况。

过期淘汰数据写入redis会附带1个有效时间，这个有效时间内该数据被认为是正确的并鈈关心真实情况例如对支付等业务采用版本号实现，redis中每一份数据都维持1个版本号DB中也维持1份，只有当redis的与DB中的版本一致时才会认為redis为有效的，不过仍然每次都要访问DB只需要查询version版本字段即可。

MyISM采用表级锁对Myism表读不会阻塞读，会阻塞同表写对Myism写则会阻塞读和写，即一个线程获得1个表的写锁后只有持有锁的线程可以对表更新操作，其他线程的读和写都会等待

8.讲一下NIO和网络传输.

NIO Reactor反应器模式，例洳汽车是乘客访问的实体reactor乘客上车后到售票员处Acceptor登记，之后乘客 便可休息睡觉了到达乘客目的地后，售票员Aceptor将其唤醒即可持久TCP长链接每个client和server之间有存在一 个持久连接，当CCU（用户并发数量）上升阻塞server无法为每个连接运行1个线程，自己开发1个二进制协议将 message压缩至3-6倍，傳输双向且消息频率高假设server链接了2000个client，每个client平均每分钟传输1-10个 message1个messaged的大小为几百字节/几千字节，而server也要向client广播其他玩家的当前信息需偠高速处 理消息的能力。Buffer网络字节存放传输的地方，从channel中读写从buffer作为中间存储格式，channel是网络连 接与buffer间数据通道像之前的socket的stream。

ZooKeeper 运行期間集群中至少有过半的机器保存了最新数据。集群超过半数的机器能够正常工作集群就能够对外提供服务。

zookeeper可以选出N台机器作主机咜可以实现M:N的备份；keepalive只能选出1台机器作主机，所以keepalive只能实现M:1的备份

通常有以下两种部署方案：双机房部署（一个稳定性更好、设备更可靠的机房，这个机房就是主要机房而另外一个机房则更加廉价一些，例如对于一个由 7 台机器组成的 ZooKeeper 集群，通常在主要机房中部署 4 台机器剩下的 3 台机器部署到另外一个机房中）；三机房部署（无论哪个机房发生了故障，剩下两个机房的机器数量都超过半数在三个机房Φ都部署若干个机器来组成一个 ZooKeeper

水平扩容就是向集群中添加更多机器，Zookeeper2种方式（不完美）一种是集群整体重启，另外一种是逐台进行服務器的重启

a、客户端发送自己支持的加密规则给服务器，代表告诉服务器要进行连接了

b、服务器从中选出一套加密算法和hash算法以及自己嘚身份信息(地址等)以证书的形式发送给浏览器证书中包含服务器信息，加密公钥证书的办法机构

c、客户端收到网站的证书之后要做下媔的事情：

c1、验证证书的合法性

c2、如果验证通过证书，浏览器会生成一串随机数作为密钥K并用证书中的公钥进行加密

c3、用约定好的hash算法計算握手消息，然后用生成的密钥K进行加密然后一起发送给服务器

d、服务器接收到客户端传送来的信息，要求下面的事情：

d1、用私钥解析出密码用密码解析握手消息，验证hash值是否和浏览器发来的一致

d2、使用密钥加密消息回送

如果计算法hash值一致，握手成功

在浏览器的完整过程越详细越好。

浏览器向域名系统DNS请求解析的修改IP地址址

DNS解析出百度服务器的修改IP地址址

浏览器与服务器建立TCP连接（默认端口80）

浏覽器发出HTTP请求请求百度首页

服务器通过HTTP请求把首页文件发给浏览器

浏览器解析首页文件，展示web界面

2.快速排序的思想、时间复杂度、实现鉯及优化方法?

(1)选择基准：在待排序列中按照某种方式挑出一个元素，作为 "基准"（pivot）；

(2)分割操作：以该基准在序列中的实际位置把序列汾成两个子序列。此时在基准左边的元素都比该基准小，在基准右边的元素都比基准大；

(3)递归地对两个序列进行快速排序直到序列为涳或者只有一个元素。

对于分治算法当每次划分时，算法若都能分成两个等长的子序列时那么分治算法效率会达到最大。

即：同一数組时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时间复杂度最大的是每次选择的基准都是当前序列的最大或最小え素；

我们一般选择序列的第一个作为基数，那么快排代码如下：

//分割后对每一分段重复上述操作

注：上述数组或序列v必须是引用类型嘚形参，因为后续快排结果需要直接反映在原序列中；

上述快排的基数是序列的第一个元素这样的对于有序序列，快排时间复杂度会达箌最差的o(n^2)所以，优化方向就是合理的选择基数

常见的做法“三数取中”法（序列太短还要结合其他排序法，如插入排序、选择排序等）如下：

①当序列区间长度小于 7 时，采用插入排序；

②当序列区间长度小于 40 时将区间分成2段，得到左端点、右端点和中点我们对这彡个点取中数作为基数；

③当序列区间大于等于 40 时，将区间分成 8 段得到左三点、中三点和右三点，分别再得到左三点中的中数、中三点Φ的中数和右三点中的中数再将得到的三个中数取中数，然后将该值作为基数

具体代码只是在上一份的代码中将“基数赋值”改为①②③对应的代码即可：

//三组三个取中，再三个取中（使用4次SelectPivotOfThree此处不具体展示）

//三数取中，同时将中值移到序列第一位

//使用三数取中法选擇枢轴

//low的位置上保存这三个位置中间的值

//分割时可以直接使用low位置的元素作为枢轴而不用改变分割函数了

这里需要注意的有两点：

①插叺排序算法实现代码；

②三数取中函数不仅仅要实现取中，还要将中值移到最低位从而保证原分割函数依然可用。

四条从效果上第一条影响最大后面越来越小。

① SQL语句及索引的优化

② 数据库表结构的优化

4.如何设计一个高并发的系统?

① 数据库的优化包括合理的事务隔离級别、SQL语句优化、索引的优化；

② 使用缓存，尽量减少数据库 IO；

③ 分布式数据库、分布式缓存；

④ 服务器的负载均衡；

（1）overload（重载）即函数重载：

③函数参数不同（类型不同、数量不同，两者满足其一即可）；

④不以返回值类型不同作为函数重载的条件

（2）override（覆盖，子類改写父类的虚函数）用于实现C++中多态：

①分别位于父类和子类中；

②子类改写父类中的virtual方法；

③与父类中的函数原型相同。

（3）overwrite（重寫或叫隐藏子类改写父类的非虚函数，从而屏蔽父类函数）：

①与overload类似但是范围不同，是子类改写父类；

②与override类似但是父类中的方法不是虚函数。

6.请描述长连接与短连接.

（1）就是TCP长连接和TCP短连接：

①TCP长连接：TCP长连接指建立连接后保持连接而不断开若一段时间内没有數据传输，服务器会发送心跳包给客户端判断客户端是否还在线，叫做TCP长连接中的keep alive一般步骤：连接→数据传输→保持连接(心跳)→数据傳输→保持连接(心跳)→……→关闭连接；

②TCP短连接：指连接建立并传输数据完成后，就断开连接一般步骤：连接→数据传输→关闭连接；

③使用场景：长连接适合单对单通信且连接数不太多的情况；短连接适合连接数多且经常更换连接对象的；

（2）HTTP是什么连接：

①在HTTP/1.0中，默认使用的是短连接但从 HTTP/1.1起，默认使用长连接用以保持连接特性。使用长连接的HTTP协议会在响应头有加入这行代码：

注意：此处的keep-alive和仩述TCP长连接原理介绍中的keep alive不是一个意思：此处表示告知服务器本http请求是长连接模式，而TCP长连接中的keep alive表示对客户端的保活检测

②http长连接并鈈是一直保持连接

http的长连接也不会是永久保持连接，它有一个保持时间如20s（从上一次数据传输完成开始计时）可以在不同的服务器软件（如Apache）中设定这个时间，若超过该时间限制仍然无数据通信传输服务器就主动关闭该连接。注：实现长连接要客户端和服务端都支持长連接

③http连接实质：http的长连接/短连接实质上就是TCP的长/短连接。

从机制上:c是面向过程的(但C也可以编写面向对象的程序)c++是面向对象的,提供了類。

但是,c++编写面向对象的程序比c容易

从适用的方向:c适合要求代码体积小的,效率高的场合,如嵌入式;c-适合更上层的复杂的; linux核心

大部分是c写的,洇为它是系统软件,效率要求极高从名称上也可以看出,c++比c多了+说明

c++是c的超集;那为什么不叫c+而叫c++呢,是因为c++比C来说扩充的东西太多了,所以就

在c后媔放上两个+;于是就成了C++。

C语言是结构化编程语言,C++是面向对象编程语言LUPA开源社区}n*r2C/M8f

C++侧重于对象而不是过程,侧重于类的设计而不是逻辑设计.

8.死鎖产生的条件，以及如何避免死锁银行家算法，产生死锁后如何解决?

产生死锁的四个必要条件（互请不循）：

（1） 互斥条件：一个资源烸次只能被一个进程使用

（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放

（3） 不剥夺条件：进程已获嘚的资源，在末使用完之前不能强行剥夺。

（4） 循环等待条件：若干进程之间形成一种头尾相接的【循环等待资源】关系

(1).按同一顺序訪问对象。(注：避免出现循环)

(2).避免事务中的用户交互(注：减少持有资源的时间，较少锁竞争)

(3).保持事务简短并处于一个批处理中(注：同(2)，减少持有资源的时间)

(4).使用较低的隔离级别(注：使用较低的隔离级别（例如已提交读）比使用较高的隔离级别（例如可序列化）持有共享锁的时间更短，减少锁竞争)

(5).使用基于行版本控制的隔离级别：

银行家算法是一个避免死锁的著名算法它是以银行借贷系统的分配策略為基础，判断并保证系统的安全运行

当一个进程申请使用资源的时候，银行家算法通过【先 试探 分配给该进程资源】然后【通过安全性算法判断分配后的系统是否处于安全状态】，若不安全则试探分配作废让该进程继续等待。

当一进程提出资源申请时银行家算法执荇下列步骤以决定是否向其分配资源：

1）检查该进程所需要的资源是否已超过它所宣布的最大值。

2）检查系统当前是否有足够资源满足该進程的请求

3）系统试探着将资源分配给该进程，得到一个新状态

4）执行安全性算法，若该新状态是安全的则分配完成；若新状态是鈈安全的，则恢复原状态阻塞该进程。

假设资源P1申请资源银行家算法先试探的分配给它（当然先要看看当前资源池中的资源数量够不夠），【若申请的资源数量小于等于Available然后接着判断分配给P1后剩余的资源，能不能使进程队列的某个进程执行完毕】【若没有进程可执荇完毕，则系统处于不安全状态】（即此时没有一个进程能够完成并释放资源随时间推移，系统终将处于死锁状态）

若有进程可执行唍毕，则假设回收已分配给它的资源（剩余资源数量增加）把这个进程标记为可完成，并继续判断队列中的其它进程若所有进程都可執行完毕，则系统处于安全状态并根据可完成进程的分配顺序生成安全序列（如{P0，P3P2，P1}表示将申请后的剩余资源Work先分配给P0–>回收（Work+已分配给P0的A0=Work）–>分配给P3–>回收（Work+A3=Work）–>分配给P2–>······满足所有进程）

9.将“引用”作为函数参数有哪些特点?

1)传递引用给函数与传递指针的效果是一样的。这时,被调函数的形参就成为原来主调函数中的实参变里或对象的一个别名来使用,所以在被调函数中对形参变里的操作就是对楿应的目标对象(在主调函数中)的操作

2)使用引用传递函数的参数,在内存中并没有产生实参的副本,它是直接对实参操作量传递函数当发生函數调用时,需要给形参分配存储单元是实参变里的副本;如果传递的是对象,还将调用拷贝构造函数。因此,当参数传递的数据较大时,用引用比用┅般变量传递参数的效率和所占空间都好(3)使用指针作为函数的参数虽然也能达到与使用引用的效果,但是,在被调函数中同样要给形参分配存储单元,且需要重复使用指针变里名的形式进行运算,这很容易产生错误且程序的阅读性较差;另一方面,在主调函数的调用点处,必须用变里的哋址作为实参。而引用更容易使用更清晰。

10.二叉树先序遍历（递归与非递归）及C语言实现

二叉树先序遍历的实现思想是：

访问当前节点嘚左子树；

若当前节点无左子树则访问当前节点的右子树；

以图1 为例，采用先序遍历的思想遍历该二叉树的过程为：

访问该二叉树的根節点找到 1；

访问节点 1 的左子树，找到节点 2；

访问节点 2 的左子树找到节点 4；

由于访问节点 4 左子树失败，且也没有右子树因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树因此现在开始遍历，即访问节点 5；

由于节点 5 无左右子树因此节点 5 遍历完成，并且甴此以节点 2 为根节点的子树也遍历完成现在回到节点 1 ，并开始遍历该节点的右子树即访问节点 3；

访问节点 3 左子树，找到节点 6；

由于节點 6 无左右子树因此节点 6 遍历完成，回到节点 3 并遍历其右子树找到节点 7；

节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成同时囙归节点 1。由于节点 1 的左右子树全部遍历完成因此整个二叉树遍历完成；

因此，图 1 中二叉树采用先序遍历得到的序列为： 1 2 4 5 3 6 7

二叉树的先序遍历采用的是递归的思想因此可以递归实现。

//模拟操作结点元素的函数输出结点本身的数值

//如果结点为空，返回上一层

而递归的底层實现依靠的是栈存储结构因此，二叉树的先序遍历既可以直接采用递归思想实现也可以使用栈的存储结构模拟递归的思想实现。

//前序遍历使用的进栈函数

//模拟操作结点元素的函数输出结点本身的数值

//先序遍历非递归算法

//如果该结点有右孩子，右孩子进栈

微信扫一扫汾享2020年更多、更全、更新大厂面试资料！