美团C++后端开发面试题(一）

(靠百度填补，有不对的地方请指证一下呗）

数据库部分

1. 事务的类型有哪些？

• 扁平事务(Flat Transactions)

• 带有保存点的扁平事务(Flat Transactions with Savepoints)

• 链事务(Chained Transactions)

• 嵌套事务(Nested Transactions)

• 分布式事务(Distributed Transactions)

对于InnoDB存储引擎来说，其支持扁平事务，带保存点的事务，链事务，分布式事务。对于嵌套事务，其原生不支持。因此对有并发事务需求的用户来说,MySQL数据库或InnoDB存储引擎就显得无能为力，然而用户仍可以通过带保存点的事务来模拟串行的嵌套事务。

2. 事务的隔离性是什么？

隔离性最常见在并发环境下，并发的事务是相互隔离的，一个事务的执行不能被其他事务干扰。也就是说，不同的事务并发操纵相同的数据时，每个事务都有各自完整的数据空间，即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的 各个事务之间不能互相干扰。

3.数据库的引擎说一下？

mysql-5.1版本之前默认引擎是MyISAM，之后是innoDB

MyISAM是非集聚引擎，支持全文索引;不支持事务;它是表级锁;会保存表的具体行数.
innoDB是集聚引擎，5.6以后才有全文索引;支持事务；它是行级锁;不会保存表的具体行数.
一般：不用事务的时候,count计算多的时候适合myisam引擎。对可靠性要求高就是用innodby引擎。

MYISAM	INNODB
只支持表级锁	支持行级锁(默认)和表级锁
不提供事务支持	①提供事务支持，②具有提交(commit)和回滚事务(roll back)的能力
不支持外键	支持
不支持数据库异常崩溃后的安全恢复	依赖redo log，在数据库异常崩溃后，数据库重新启动的时候会保证数据库恢复到崩溃前的状态
不支持MVCC	支持

比较常用的数据库引擎3种：
MYISAM：支持3中存储方式：静态型，动态型，压缩型
优点：占用的空间小，存储的速度快
缺点：不支持事务和并发，容错
使用场景：数据表主要做修改和查询操作
MYISAM在设计之时就考虑到数据库被查询的次数要远大于更新的次数。因此，ISAM 执行读取操作的速度很快，而且不占用大量的内存和存储资源。ISAM 的两个主要不足之处在于，它不支持事务处理，也不能够容错。如果你的硬盘崩溃了，那么数据文件就无法恢复了。如果你正在把 ISAM 用在关键任务应用程序里，那就必须经常备份你所有的实时数据，通过其复制特性，MYSQL 能够支持这样的备份应用程序。注意：使用 ISAM 时必须经常备份所有实时数据。
innoDB:
优点：提供事务的支持，回滚，崩溃修复能力，多版本事务并发控制
缺点：读写效率较差，占用的数据库空间较大
使用场景：MySQL主要引擎
Memory：内存中对数据创建表，数据全部存储在内存
缺点：生命周期短
优点：读写速度非常快，对数据的安全性要求比较低的时候可以选择memory
使用场景：MySQL中使用该引擎作为临时表

4.b树和b+树的区别

B树与B+树的区别有两个：
1、B树的非叶子节点是存储数据的，而B+树的非叶子节点只存储索引信息
2、B+树的非最右侧的叶子节点向右会指向右侧的叶子节点，形成一个有序的连表

在查找数据的时候，B树需要根据数据是比较查找,查询次数较多，
由于B+树存储的是数据的索引，所以只有一次IO就可以查找到数据
而且B+树非叶子节点只存储索引，所以能存储更多的索引，使树的高度降低

C++

(空缺的部分感觉有点难，延迟百度）

1. 知道mmap吗？

❗ ❓

2.手写一个C++单例？考虑多线程如何做？

❗❓

操作系统

1. 说一下线程和进程的区别？

进程是程序的⼀次执行过程，是⼀个动态概念，是程序在执行过程中分配和管理资源的基本单位，每⼀个进程都有⼀个自己的地址空间。
线程是CPU调度和分派的基本单位，它可与同属⼀个进程的其他的线程共享进程所拥有的全部资源。
区别
① ⼀个线程只能属于⼀个进程，而⼀个进程可以有多个线程，但至少有⼀个线程。线程依赖于进程而存在。
② 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。
③ 进程是资源分配的最小单位，线程是CPU调度的最⼩单位；
④ 系统开销： 由于在创建或撤消进程时，操作系统所付出的开销将显著地⼤于在创建或撤消线程时的开销。类似地，进程切换的开销也远大于线程切换的开销。
⑤进程间不会相互影响，而一个线程挂掉可能导致整个进程挂掉。

2.一个线程坏了，其他线程确定会坏吗？你做过实验验证过吗？

严格的说没有“线程崩溃”，只是触发了SIGSEGV (Segmentation Violation/Fault)。如果没有设置对应的Signal Handler操作系统就自动终止进程（或者说默认的Signal Handler就是终止进程）；如果设置了，理论上可以恢复进程状态继续跑（用longjmp之类的工具）

确实如此，不过捕获信号以后基本只能处理一下异常，保存一些状态。过多的事情也干不了。除了进程结束和ctrl+c那个信号，连保存工作状态都干不了。

进程与进程之间是隔离的，线程与线程之间是没有隔离的。虽说每个线程有自己的工作栈空间，但是线程A与访问线程B的工作栈也是可以做到的。某个线程的行为可能影响到进程内其他线程。
在Java里面，某个线程抛出异常没有捕获，对应的线程会崩溃，但是对应进程(JVM虚拟机）并不会随之崩溃。这样既有好处也有坏处，好处是，其它线程不受影响，坏处是：若没有外围监控很难察觉到对应的线程是否已经崩溃。

3.线程间通信方式？

① 两个进程间的两个线程通信，相当于进程间通信。
② 一个进程中的两个线程间通信。
通信方式：
1.互斥锁
　　- mutex;
　　- lock_guard (在构造函数里加锁，在析构函数里解锁）
　　- unique_lock 自动加锁、解锁
2.读写锁
　　shared_lock
3.信号量
　　c++11中未实现，可以自己使用mutex和conditon_variable 实现

进程间通信
进程间通信的⽅式：
进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。

1. 管道：
   管道主要包括无名管道和命名管道:管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信
   1.1 普通管道PIPE：
   它是半双工的（即数据只能在⼀个方向上流动），具有固定的读端和写端
   它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）
   它可以看成是⼀种特殊的文件，对于它的读写也可以使⽤普通的read、write等函数。但是它不是
   普通的文件，并不属于其他任何⽂件系统，并且只存在于内存中。
   1.2 命名管道FIFO：
   FIFO可以在⽆关的进程之间交换数据
   FIFO有路径名与之相关联，它以⼀种特殊设备⽂件形式存在于⽂件系统中。
2. IPC
   2.1 消息队列
   消息队列，是消息的链接表，存放在内核中。⼀个消息队列由⼀个标识符（即队列ID）来标记。 (消息队
   列克服了信号传递信息少，管道只能承载⽆格式字节流以及缓冲区⼤⼩受限等特点)具有写权限得进程可
   以按照⼀定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信
   息；
   特点：
   消息队列是⾯向记录的，其中的消息具有特定的格式以及特定的优先级。
   消息队列独⽴于发送与接收进程。进程终⽌时，消息队列及其内容并不会被删除。
   消息队列可以实现消息的随机查询,消息不⼀定要以先进先出的次序读取,也可以按消息的类型读
   取。
   2.2 信号量semaphore
   信号量（semaphore）与已经介绍过的 IPC 结构不同，它是⼀个计数器，可以⽤来控制多个进程对共享
   资源的访问。信号量⽤于实现进程间的互斥与同步，⽽不是⽤于存储进程间通信数据。
   特点：
   信号量⽤于进程间同步，若要在进程间传递数据需要结合共享内存。
   信号量基于操作系统的 PV 操作，程序对信号量的操作都是原⼦操作。
   每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，⽽且可以加减任意正整数。
   ⽀持信号量组。
   2.3 信号signal
   信号是⼀种⽐较复杂的通信⽅式，⽤于通知接收进程某个事件已经发⽣。
   2.4 共享内存（Shared Memory）
   它使得多个进程可以访问同⼀块内存空间，不同进程可以及时看到对⽅进程中对共享内存中数据得更
   新。这种⽅式需要依靠某种同步操作，如互斥锁和信号量等
   特点：
   共享内存是最快的⼀种IPC，因为进程是直接对内存进⾏存取
   因为多个进程可以同时操作，所以需要进⾏同步
   信号量+共享内存通常结合在⼀起使⽤，信号量⽤来同步对共享内存的访问
   3.套接字SOCKET：
   socket也是⼀种进程间通信机制，与其他通信机制不同的是，它可⽤于不同主机之间的进程通信。

4.cpu、内存和外设之间除了中断，还有哪些交互方法？

5.说一下中断是什么？

教材上会说中断是外部设备向处理器发起的请求事件，但这还不够本质。中断的本质是处理器对外开放的实时受控接口。

计算机网络

1.浏览器输入一个url后会发生什么？

过程	使用的协议
1.浏览器查找域名的IP地址(DNS查找过程：浏览器缓存、路由器缓存、DNS缓存)	DNS:获取域名对应IP
2.浏览器向web服务器发送一个HTTP请求(cookies会随着请求发送给服务器)	TCP:与服务器建立TCP连接
3.服务器处理请求(请求 处理请求&它的参数、cookies、生成一个HTML响应)	IP：建立TCP协议时，需要发送数据，发送数据在网络层使用IP协议
4.服务器返回一个HTML响应	OSPF：IP数据包在路由器之间，路由选择使用OSPF协议
5.浏览器开始显示HTML	ARP：路由器在与服务器通信时需要将ip地址转换为MAC地址，需要使用ARP协议
	HTTP: 在TCP简历完成后，使用HTTP协议访问网页

体来说分为以下几个过程:

1. DNS解析

2. TCP连接

3. 发送HTTP请求

4. 服务器处理请求并返回HTTP报文

5. 浏览器解析渲染页面

6. 连接结束

具体可以参考下面这篇文章：

• https://segmentfault.com/a/1190000006879700

2.get和post的区别

1.GET请求的数据会附在URL之后，以?分割URL和传输数据，参数之间以&相连，POST把提交的数据则放置在是HTTP包的包体中。
2.GET的长度受限于url的长度，而url的长度限制是特定的浏览器和服务器设置的，理论上GET的长度可以无限长。
3.POST是没有大小限制的，HTTP协议规范也没有进行大小限制，起限制作用的是服务器的处理程序的处理能力
4.在ASP中，服务端获取GET请求参数用Request.QueryString，获取POST请求参数用Request.Form。
5.POST的安全性要比GET的安全性高application

json 与form表单的区别?浏览器默认的提交方式就是表单。首先，Content-Type 被指定为 application/x-www-form-urlencoded，jQuery的Ajax请求默认方式，其次，数据以键值对形式？key1=value1&key2=value2的方式发送到服务器1、post和get的选择？私密性的信息请求使用post。查询信息和可以想要通过url分享的信息使用get。

3.post为什么两次连接？你做实验验证过吗？

post是不是不一定两次发送，我之前看了一份资料，这个两次发送好像是跟浏览器相关的。少部分的浏览器post请求是分为两次发送的

GET和POST还有一个重大区别，简单的说：
GET产生一个TCP数据包；POST产生两个TCP数据包。

长的说：
对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；
而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。

也就是说，GET只需要汽车跑一趟就把货送到了，而POST得跑两趟，第一趟，先去和服务器打个招呼“嗨，我等下要送一批货来，你们打开门迎接我”，然后再回头把货送过去。

因为POST需要两步，时间上消耗的要多一点，看起来GET比POST更有效。因此Yahoo团队有推荐用GET替换POST来优化网站性能。但这是一个坑！跳入需谨慎。为什么？

GET与POST都有自己的语义，不能随便混用。
据研究，在网络环境好的情况下，发一次包的时间和发两次包的时间差别基本可以无视。而在网络环境差的情况下，两次包的TCP在验证数据包完整性上，有非常大的优点。
并不是所有浏览器都会在POST中发送两次包，Firefox就只发送一次。

状态码.png

4.如何用udp实现可靠传输？

UDP不属于连接协议，具有资源消耗少，处理速度快的优点，所以通常音频，视频和普通数据在传送时，使用UDP较多，因为即使丢失少量的包，也不会对接受结果产生较大的影响。

传输层无法保证数据的可靠传输，只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式，只是实现不在传输层，实现转移到了应用层。

最简单的方式是在应用层模仿传输层TCP的可靠性传输。下面不考虑拥塞处理，可靠UDP的简单设计。
1、添加seq/ack机制，确保数据发送到对端
2、添加发送和接收缓冲区，主要是用户超时重传。
3、添加超时重传机制。
详细说明：送端发送数据时，生成一个随机seq=x，然后每一片按照数据大小分配seq。数据到达接收端后接收端放入缓存，并发送一个ack=x的包，表示对方已经收到了数据。发送端收到了ack包后，删除缓冲区对应的数据。时间到后，定时任务检查是否需要重传数据。
目前有如下开源程序利用udp实现了可靠的数据传输。分别为RUDP、RTP、UDT。

做题

从上往下， 从右向左斜着打印二维数组

写一个矩阵，模拟打印找出规律。可以发现总共需要打印的次数，为矩阵的行数+列数-1(相当于对角线公用了一个元素)。

#include<bits/stdc++.h>
using namespace std;
void printMatrix(vector<vector<int>>& matrix){
    int n = matrix.size();
    int m = matrix[0].size();
    for(int t =0; t<n+m-1; t++){
        int i = t<=m-1?0:t-m+1;
        int j_start = t <= m-1? t: m-1;
        int j_end = t <= n-1? 0:t-n+1;
        int repeat = j_end - j_start;
        for(int temp =j_start; temp>=j_end; temp--){
            cout<<matrix[i++][temp]<<" ";
        }
        cout<<endl;
    }
    return ;
}

int main(){
    vector<vector<int>> matrix = {{0,1,2,3,4},{0,1,2,3,4},{0,1,2,3,4},{0,1,2,3,4},{0,1,2,3,4},{0,1,2,3,4},{0,1,2,3,4},{0,1,2,3,4}};
    
    printMatrix(matrix);
    return 0;
}

输出.png

参考

1.https://www.nowcoder.com/discuss/624163channel=-1&source_id=discuss_terminal_discuss_sim_nctrack&ncTraceId=2a2a511b7de04c699d9fcf89233d3099.197.16215914342259692
2.事务的类型有哪些：https://blog.csdn.net/qq_41333582/article/details/84196964
3.数据库引擎：①https://www.cnblogs.com/yblackd/p/12019818.html②https://zhuanlan.zhihu.com/p/69359526③https://www.cnblogs.com/lingboweifu/p/11808116.html

MyISAM.png
InnoDB.png
4.B树和B+树的区别 ①https://segmentfault.com/a/1190000038216753 ②https://www.shangmayuan.com/a/4f951c016bef4cd4b50abec0.html
③https://snailclimb.gitee.io/javaguide/#/docs/database/MySQL%E6%95%B0%E6%8D%AE%E5%BA%93%E7%B4%A2%E5%BC%95?id=%e4%b8%bb%e9%94%ae%e7%b4%a2%e5%bc%95primary-key
5.线程和进程https://www.zhihu.com/question/25532384
6.线程崩溃①https://blog.csdn.net/weixin_38106322/article/details/107822340（一个不影响进程的案例，别的线程照样允许）②https://www.zhihu.com/question/22397613/answer/21237577
7.中断https://www.zhihu.com/question/21440586
8.浏览器输入一个url会发生什么①https://www.cnblogs.com/jin-zhe/p/11586327.html②https://www.zhihu.com/question/34873227
9.get和post的区别https://www.zhihu.com/question/28586791/answer/621747763

10. post为什么两次https://blog.csdn.net/happy_xiahuixiax/article/details/72859762

11.UDP如何实现可靠传输①https://www.zhihu.com/question/283995548/answer/661809748
②https://www.jianshu.com/p/6c73a4585eba

UDP要想可靠，就要接收方收到UDP之后回复个确认包，发送方有个机制，收不到确认包就要重新发送，每个包有递增的序号，接收方发现中间丢了包就要发重传请求，当网络太差时候频繁丢包，防止越丢包越重传的恶性循环，要有个发送窗口的限制，发送窗口的大小根据网络传输情况调整，调整算法要有一定自适应性。恭喜你， 你在应用层重新实现了TCP！

多线程与多进程.png