算法题
- 单链表排序 ————（自顶向下,merge,split），如何实现自底向上
通过step实现，或者通过vector实现
C++
- 类的对象占多少内存
1、空类、单一继承的空类、多重继承的空类所占空间大小为：1（字节，下同）；
2、一个类中，虚函数本身、成员函数（包括静态与非静态）和静态数据成员都是不占用类对象的存储空间的；
3、因此一个对象的大小≥所有非静态成员大小的总和（包括动态分配的变量…）；
4、每个实例对象可能会【虚函数指针，虚基类指针】
5、padding
6、类对象大小 = 非静态成员 + vfptr(多继承下可能不止一个) + vbptr(多继承下可能不止一个) + padding
虚函数表：不占用存储空间；存储的是虚函数地址 虚基类表：占用存储空间；存储的是虚基类相对于直接继承类的偏移
- 前缀树和后缀树
前缀树即字典树，核心思想是：空间换时间。一种用于快速检索的多叉树结构。最大程度的减少对字符串的比较次数。
- static作用
全局变量，文件域静态变量，类的成员变量在main执行前初始化，线程安全。
局部静态变量（一般在函数内），在第一次使用时分配内存并初始化。
- static是如何限定作用域在文件范围内的
定义全局静态变量即可。
- 重载和重写
操作系统
- 子进程写时复制底层原理
linux系统fork时，并不会把父进程所占有的内存页拷贝一份，而是与父进程共享相同的内存页。
当多个进程的虚拟页映射到相同的物理页时，就实现了共享内存。
- 创建子进程时，将父进程的虚拟地址到物理内存的映射关系拷贝到子进程中，并将内存设置为只读（设置只读是为了写时触发缺页异常）
- 当子进程或父进程进行修改时，会触发写时赋值，新开辟一个内存页，拷贝对应的数据并做修改。
- 进程的调度
https://www.cnblogs.com/yangyuliufeng/p/9318146.html
挂起态和等待态的区别：等待态占用已申请到的资源等待，挂起态没有任何资源
把处于统一状态的所有进程PCB链接在一起，即为进程队列。（运行队列，就绪队列，设备队列，信号量队列等等）
- cpu缓存
- 共享内存实现方式
mmap:在进程的虚拟地址空间分配地址空间，创建和物理内存的映射关系
ftok:创建唯一IPC标识符来让不同进程通信，通过ftok生成key标识，并通过shmget创建共享内存。
计网
- UDP怎么保证可靠
传输层无法保证数据的可靠传输，只能通过应用层来实现，实现的方式可以参考 TCP 可靠性传输，只是实现不在传输层，实现转移到了应用层
实现确认机制，重传机制，窗口确认机制
如果不利用 Linux 协议栈及上层 socket 机制，自己通过抓包和发包的方式去实现可靠性传输，那么必须实现以下功能
发送：包的分片、包确认、包的重发
接收：包的调序、包的序号确认
目前已有如下开源程序利用 UDP 实现了可靠的数据传输，分别为：RUDP、RTP、UDT
- TCP keep-alive和HTTP的区别
HTTP KEEPALIVE: 用作一个TCP连接发送多个HTTP请求，服务端为设置了KEEP ALIVE选项的连接保留连接的有效性，直到超时关闭该连接，这是实现管线化的必要条件。
TCP KEEPALIVE: 作为检测TCP连接是否保活的一种机制，当上层协议一直不发送数据时，TCP需要确定对端是连接失效了还是暂时无数据可传输。
超过一段时间后，TCP自动发送一段数据为空的报文，用于检测对端是否还在线。
一般TCP保活机制为2小时，2小时后会连续发送10次探测报文，每隔75s发送一次，若对端无回应，则丢弃该连接。
- 主从状态机是什么？
DNS过程
- 用户主机运行DNS客户端
- 浏览器将接受到的url抽出域名字段
- dns客户端向dns服务器发送查询报文，查询该域名对应的ip地址
- dns客户端接收到ip地址
- 向该ip地址对应的HTTP服务器发起TCO连接
- 检查浏览器和操作系统是否有缓存
- 请求本地域名服务器，
- 请求根域名服务器，返回主域名服务器地址
- 本地域名服务器向主域名服务器请求解析
- 主域名服务器将该网站对应的【Name Server服务器地址】返回
- 本地域名服务器将请求转发给NAME SERVER
- Name SERVER服务器解析后，将结果返回LDNS
- LDNS保存返回结果，并将其转发给客户端
- 客户端访问对应IP的HTTP服务器
UDP和TCP的发包限制
对于TCP而言，受链路层限制，数据包最大为MTU1500B，到TCP层，由于受包头40B限制，数据包最大为1460B，且受接收端滑动窗口限制。
在UDP层，由于包头8字节，所以数据包最大为1472B
当UDP报文大于1472时，IP层需要进行分片传输，并在接收方IP层重组，由于UDP是不可靠协议，由于分片丢失导致重组失败，会丢弃整个IP报文。
UDP数据包长度 = 报头 + 数据部分，长度字段为16字节，包括报头最大支持长度为64KB
TCP没有限定，报头中不存在包长度字段，由于是字节流协议，只需要往socket缓冲区添加数据即可，TCP自己保证流量控制和拥塞控制。
- nagle算法中包是怎么发送的
若发送端需要多次发送小数据包，则发送端会先将第一个小包发送出去，将后续到达的少量数据都缓存起来而不立即发送，直到收到对端对前一个数据包的ACK，或当前字符数据属于紧急数据，或积攒到一定大小时等情况，才会将组合包发出。
一般有如下规则：
- 数据包大小超过MSS【TCP连接时，收发双方不包括报头的最大报文段大小】
- 包含FIN
- 设置TCP_NODELAY
- 超时，一般为200ms，立即发送
- TCP客户端接收FIN报文后，能不能立刻关闭
若客户端为主动关闭方，在接收到FIN报文后，需回复LAST-ACK并进入TIMEWAIT状态
若客户端为被动关闭方，在接收到FIN时，进入CLOSE-WAIT状态，此时同时发送(FIN+ACK)报文，会进入LAST-ACK状态，等待接收最后的ACK
数据库
场景
- 设计一个UDP协议，在应用层实现可靠传输。
按如下方面分析：
- 流量控制，拥塞控制
- 发送窗口，接收窗口
- ACK,RTO(Retransmission Time Out))，ARQ（重传）
从这些方面去考虑，并设计协议结构和数据结构
- 实现shuffle算法（54张扑克牌，打乱顺序）
- 若支持随机访问，则从后向前遍历，swap(i,rand(i));
- 不支持，则先转为支持随机访问的结构，在做如上处理
- 单例模式
- 非线程安全
- 双if实现线程安全
- 或使用
once_flag,call_once实现线程安全
- 一个二维地图，怎么判断怪物中距离玩家距离小于r的数目
四叉树
若有收获，就点个赞吧
0 人点赞
