2023秋招大厂经典面试题及答案整理归纳（261-28

目录

261. 设计和实现一个LRU （最近最少使用）缓存数据结构，使它应该支持一下操作get和put。

262. 已知sqrt(2)约等于1.414,要求不用数学库，求sqrt⑵ 精确到小数点后10位。

263. 给定一个二叉搜索树(BST),找到树中第K小的节点。

264. 如何用socket编程实现ftp协议？

265. 给定一个数组，它的第i个元素是一支给定股票第i天的 价格。设计一个算法来计算你所能获取的最大利润。你可以 尽可能地完成更多的交易(多次买卖一支股票)。注意你 不能参与多笔交易(你必须在购买前出售掉之前的 股票)。

266. 描述实时系统的基本特性

267. 求任意一颗二叉树最长路径长度

268. 手写冒泡排序算法,计算冒泡排序算法的时间复杂度？

269. redis中的网络IO有了解过吗，它是单线程的还是多线程的，为什么要用单线程。

270. 优先队列时间复杂度。

271. 堆的维护时间复杂度。

272. CPU是怎么执行指令的？

273. 什么函数不能声明为虚函数？

274. 在函数内定义一个字符数组，用gets函数输入字符串的时候，如果输入越界，为什么程序会崩溃？

275. 线上CPU爆高，请问你如何找到问题所在。

276. 从innodb的索引结构分析，为什么索引的key长度不 能太长？

277. MySQL的数据如何恢复到任意时间点？

278. 曹操南下攻打刘备，刘备派关羽守锦州，关羽派张飞去守城 门。刘备又派诸葛亮去向孙权求援。孙权派兵攻打曹操.请画 岀UML图.

279. 信号的生命周期？

280. 信号的产生方式？

---

261. 设计和实现一个LRU （最近最少使用）缓存数据结构，使它应该支持一下操作get和put。

get（key）-如果key存在于缓存中，则获取key的value （总是 正数），否则返回
class LRUCache{
public
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
auto it = m. find (key);
if (it == m. end()) return ~1;
1. splice (1. beginO, 1, it~>second); return it->second">second;
void set(int key, int value) { auto it = m. find (key);
if (it != m. end())
1. erase(it~>second);
1. push_front(make_pair(key, value));
m[key] = 1. beginO ;
if (m. size () > cap) {
int k = 1.rbegin()~>first;
l. pop__back ();
m. erase (k);

---

262. 已知sqrt(2)约等于1.414,要求不用数学库，求sqrt⑵ 精确到小数点后10位。

1. 已知sqrt(2)约等于1.414,那么就可以在(1.4, 1.5)区间做二分查找，如 high=>l.5
lo=>l.4
mid => (high+lo)/2=1.45
1.451.45>2 ? high=>1.45 : lo => 1.45
循环到c)

2. 退出条件
前后两次的差值的绝对值<=0.0000000001,则可退出。
代码

const double EPSINON = 0.0000000001,
double sqrt2()
[
double lo = 1.4, high = 1. 5;
double mid = (lo + high) / 2;
hile (high - lo > EPSINON)
high = mid;
}
else
!
lo = mid;
}
mid = (high + lo) / 2;
}
return mid;
}

---

263. 给定一个二叉搜索树(BST),找到树中第K小的节点。

 Definition for a binary tree node.
 public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode(int x) { val = x; }
 }
/
class Solution {
private class ResultType {
//是否找到
boolean found;
//节点数目
int val;
ResultType(boolean found, int val) {
this, found - found;
this, val = val;
}
}
public int kthSmallest(TreeNode root, int k) { return kthSmallestHelper(root, k). val;
private ResultType k thSmalles tHeIp er(TreeNode root, int k) { if (root == null) {
return ne ResultType(false, 0);
ResultType left = kthSmallestHelper(root.left, k);
//左子树找到，直接返回
if (left, found) { return ne ResultType(tiue, left, val);
}
//左子树的节点数目=K-l,结果为功。t的值
if (k - left, val == 1) { return ne ResultType(tiue, root, val);
}
//右子树寻找
ResultType right = kthSmallestHelper(root, right, k - left, val - 1); if (right, found) {
return ne ResultType (tiue, right, val);
}
//没找到，返回节点总数
return ne ResultType(false, left, val + 1 + right, val);

---

264. 如何用socket编程实现ftp协议？

以linux为例，使用socket编程中的read。函数和rite。函数已可实现文件的发送 接收，为啥还要专门建立ftp协议呢？单单使用:read。函数和rite。函数，数据接口和命 令接口未分开，效率低。而ftp将数据接口和命令接口分开，提高了文件传输效率和安全性。
ftp协议的实现仍是使用socket编程，是实现tcp连接。
Socket客户端编程主要步骤如下
socket ()创建一个 Socket
connect ()与服务器连接
rite()和readO进行会话
close ()关闭 Socket
Socket服务器端編程主要步骏如下
socket ()创建一个 Socket
bind()
listenO 监听
aept ()接收连接的请求
rite()和readO进行会话
close ()关闭 Socket
建立tcp连接代码简示如下
SOCKET control_sock;
struct hostent hp;
struct sockaddr_in server;
memset(^server, 0, sizeof(struct sockaddr_in))

control_sock = socket(AF_INET, SOCK_STREAJ.f, 0);
hp = gethostbyname(server_name);
memcpy(&server・ s in_addr, hp->h_addr, hp->h_length);
server. sin_family - AF_INET;
server. sin_port = htons(port);

connect(control_sock, (struct sockaddr )^server, sizeof(server));

read (control_sock, read__buf, read__len);
ftp客户端与服务器建立起tcp连接后，然后向服务器发送命令。(这一步建立的是命 令接口的tcp连接，数据接口连接尚未建立。)
通常第一步发送USER和PASS命令给证账号和密码后登陆服务器。若是匿名服务器则另 当别论。
登陆服务器代码简示如下

sprintf(send_buf, "USER %srn°, username);

rite(control_sock, send_buf, strlen(send_buf));

read(control_sock, read_buf, read_len);

sprintf (send_buf, "PASS passvord);

rite(control_sock, send_buf, strlen(send_buf));
read(control_sock, read_buf, read_len);
接下来是选择发送PORT命令选择主动模弍还是发送PASV命令选择被动模式。
主动模式还是被动模式是相对服务器来说的。被动模式即命令接口连接和数据接口连接 都由客户端主动建立；主动模式是数据接口蟻由服务器主动建立。这里仅简述被动模式的 建立，主动模式可依理建立。
被动模式建立连接代码

sprintf(send_buf, "PASVrn");

rite (control_sock, send__buf, str 1 en (send__buf));

read(control_sock, read_buf, read_len);
客户端发送PASV命令让服务器进入被动模式。服务器会打开数据端口并监听。并返回 响应码227和数据连接的端口号。
接下来通过数据端口下载上传查看文件就不整述了。

connect(data_sock, (struct sockaddr x)&server, sizeof(server));

sprintf(send_buf, "CWD %srn^, dirname);

rite (control_sock, send__buf, str 1 en (send__buf));

read(control_sock, read_buf, read_len);

sprintf (send_buf, "SIZE %sxn filename);

rite (control_sock, send__buf, str 1 en (send__buf));

read(control_sock, read_buf, read_len);

sprintf (send_buf, "RETR %sxn filename);

rite (control_sock, send__buf, str 1 en (send__buf));
read (control_sock, read__buf, read__len);

file_handle = open(disk_name, CRFLAGS, RWXALL);
&(；；){

read(data_sock, read__buf, read二en);

rite (f ile_handle, read__buf, read_len);
}

rc = close (file_handle);
下载完成后客户端退出服务器，关闭连接。

close(data_sock);

read(control_sock, read_buf, read_len);

sprintf (send_buf, "QUIT:rn");

rite (control_sock, send__buf, str 1 en (send__buf));

read (control_sock, read__buf, read__len);

close(control_sock);
断点续传的实现
由于网络不稳定，在传输文件的过程中，可能会发生连接断开的情况，这时候需要客户 端支持断点续传的功能，下次能够从上次终止的地方开始接着传送。需要使用命令REST。 如果在断开连接前，一个文件已经传输了 512个字节。则断点续传开始的位置为512,服 务器会跳过传输文件的前512字节。

---

265. 给定一个数组，它的第i个元素是一支给定股票第i天的 价格。设计一个算法来计算你所能获取的最大利润。你可以 尽可能地完成更多的交易(多次买卖一支股票)。注意你 不能参与多笔交易(你必须在购买前出售掉之前的 股票)。

package test;
import java. util. Scanner;
public class Many {
public static void main(String[. args) {
Scanner sc = ne Scanner(System, in);
String str =”“；
str = sc. nextLine (); //读入数组中所有元素；
String arr[] = str. split C 0； // 用空格分割字符串
int n = arr. length;
int arra[] = ne int [n];
for (int i = 0; i < arra.length; i++) {
arra[i] - Integer.parselnt(arr[i]);
// System, out. print(arra[i] + ";
} //将字符串转化为整数数组
int max = 0; //盈利最大
for (int i = 0; i < axra.length - 1; i++) {
int t = axra[i+l] - axra[i];
if(t > 0) max += t;
}
System, out. printIn(max);

---

266. 描述实时系统的基本特性

实时系统是指在系统工作时，能在特定啊寸间内完成特定的任务，其各种资源可以根据 需要进行动态的分配，其处理事务的能力强，速度快。
1） 高精度计时系统
计时精度是影响实时性的一个重要因素。在实时应用系统中，经常需要精确确定实时地 操作某个设备或执行某个任务，或精确的计算一个时间函数。这些不仅依赖于一些硬件提供 的时钟精度，也依赖于实时操作系统实现的高精度计时功能。
2） 多级中断机制
—个实时应用系统通常需要处理多种外部信息或事件，但处理的紧迫程度有轻重緩急之 分。有的必须立即作出反应，有的则可以延后处理。，需要建立多级中断嵌套处理机制, 以确保对紧迫程度较高的实时事件进行及时响应和处理。
3） 实时调度机制
实时操作系统不仅要及时响应实时事件中断，也要及时调度运行实时任务。, 处理机调度并不能随心所欲的进行，因为涉及到两个进程之间的切换，只能在确保“安全切 换”的时间点上进行，实时调度机制包括两个方面，一是在调度策略和算法上保证优先调度 实时任务；二是建立更多“安全切换”时间点，保证及时调度实时任务。

---

267. 求任意一颗二叉树最长路径长度

图1树的最长路径长度为4,图2的最长路径长度为7,图1最长路径经过根节点，顶 点为1,图2不经过，顶点为3
思路
有中任意两个节点之间，连接起来的路径最长。方法就是求出每个节点的左子树和右子 树的高度，两者相加就是当前节点的最长路径，然后比较每个节点的最长路径，最大的就是 结果
实现方法
定义一个静态变量MaxLength记录每一步最大长度，采职前序遍历来遍历每一个节点, 在遍历过程中，对当前节点的最长路径进行比较，对于每一个节点最长路径求法，先求出它 左子树和右子树的高度(节点数最多的路径)，然后相加即为当前节点最长路径
static Integer MaxLength=0;//记录最长路径
//遍历整棵树，得到最长路径

public void g e tL eng th(Tr e eNo de t){
if(tJ=null){
KaxLength=Math. max(LengthTree(t), MaxLength);
getLength(t. 1 chi Id); getLength(t. r chi Id);
}
}
//得到当前节点的最长路径
public int LengthTree(TreeNode t){
if (t==null)
return 0;
int left=heighTree(t. 1chiId);
int right=heighTree(t. rchiId);
int CurMax= 1 ef t-hr i ght;
return CurMax;
//求二叉树最大高度
public int heighTree(TreeNode t){
if (t==null)
return 0;
else
return Math, max(heighTree(t.Ichild), heighTree(t. rchiId))+1;
}

---

268. 手写冒泡排序算法,计算冒泡排序算法的时间复杂度？

public void sap(int[] array, int i, int j) {
array[i] = array[i] + array[j];
array[j] - array[i] 一 array[j];
array[i] - array[i] 一 array[j];
public void sort(int[] array) {
int n = array, length;
for (int i = 0; i < n - 1; i++) {

/依这里j不需要遍历到nT 了，因为n-l-i"n-l之间的元素 //已经排好序了，不需要再比较
for (int j = 0; j < n - 1 - i; j++) {
/R寻最大元素移动到数组末尾
if (axraytj] > array[j - 1]) {
sap (array, j, j + 1)；

从代码中可以看出一共遍历了 n-1 + n-2 + ― + 2 + 1 = n (n~l) / 2
2 - 0. 5 n,
那么时间复杂度是0(『2)。

---

269. redis中的网络IO有了解过吗，它是单线程的还是多线程的，为什么要用单线程。

redis采用网络10多路复用技术来保证在多连接的时候，系统的高呑吐量。

多路-指的是多个socket连接，复用-指的是复用一个线程。多路复用主要有三种技术: select, poll, epollo epoll是最新的也是目前最好的多路复用技术。

这里“多路”指的是多个网络连接，“复用”指的是复用同一个线程。采用多路I/O 复用技术可以让单个线程高效的处理多个连接请求(尽量减少网络I。的时间消耗)， 且Redis在内存中操作数据的速度非常快(内存内的操作不会成为这里的性能瓶颈)，主要 以上两点造就了 Redis具有很高的呑吐量。

Figure 6.3. I/O multiplexing model.

jppllolion

kernel

select

no datagram rvady

pivetg bkx:k> in vail

proce bkvk^ tvhile data copied into applies I ion buffer

return readable

ait for cLila

reevfren

datagram tv^dy copy datagram

copy data from kl to itovr

return OK

pnvfss
datagram

因为Redis是基于内存的操作，CPU不是Re dis的瓶颈，Re dis的瓶颈最有可能是机器 内存的大小或者网络带宽。既然单线程容易实现，而且CPU不会成为瓶颈，所以采用单线程

---

270. 优先队列时间复杂度。

优先级队列用堆实现，只是需要构建初始堆，这个时间复杂度是0(n)插入和删除只是 修改了堆顶和堆底，不需要所有的都排序，只是需要调整好堆，时间复杂度都 是0(log2n).

---

271. 堆的维护时间复杂度。

假如有N个节点，那么高度为H=logN,一层每个父节点最多只需要下调1次，倒 数第二层最多只需要下调2次，顶点最多需要下调H次，而一层父节点共有2YH-1) 个，倒数第二层公有2、(H-2),顶点只有1(2八。)个，所以总共的时间复杂度为s = 1 2A(H-1) + 2 2A(H-2) + ... + (H-l) 2A1 + H 2A0 将 H 代入后 s= 2N - 2 - 10g2(N),近似的时间复杂度就是C(N)o

---

272. CPU是怎么执行指令的？

计算机每执行一条指令都可分为三个阶段进行。即职指令——分析指令——执行指 令。
取指令的任务是根据程序计数器pc中的值从程序存储器读出现行指令，送到指令寄 存器。
分析指令阶段的任务是将指令寄存器中的指令操作码取出后进行译码，分析其指令性 质。如指令要求操作数，则寻找操作数地址。
计算机执行程序的过程实际上就是逐条指令地重复上述操作过程,直至谒到停机指令可 循环等待指令。
—般计算机进行工作时,要通过外部没备把程序和数据通过输入接口电路和数据总 线送入到存储器，然后逐条取出执行。但革片机中的程序一般事先我们都已通过写入器 固化在片内或片外程序存储器中。因而一开机即可执行指令。
下面我们将举个实例来说明指令的执行E程
幵机时，程序计算器pc变为。。。。川然活单片机在时序电路作用下自动进入执行程序 过程。执行过程实际上就是取出指令(取出存储器中事先存放的指令阶段)和执行指令 (分析和执行指令)的循环过程。
例如执行指令MOV A,#0E0H,其机器码为“74H EOH”，该指令的功能是把操作数 E0H送入累加器，
0000H单元中已存放74H, 0001H单元中已存放EOH。当单片机开始运行时，是进 入取指阶段，序是
1程序计数器的内容(这时是0000H)送到地址寄存器；
2程序计数器的内容自动加1 (变为。。。川)；
3地址寄存器的内容(。。。纺)通过内部地址总线送到存储器，以存储器中地址译码电
跟，使地址为。。。釦的单元被选中；
4 CPU使读控制线有效；
5在读命令控制下被选中存储器单元的内容（此时应为74H）送到内部数据总线上，因 为是取指阶段，所以该内容通过数据总绒被送到指令寄存器。至此，取指阶段完成，进 入译码分析和执行指令阶段。
由于本次进入指令寄存器中的内容是74H （操作码），以译码器译码后单片机就会知道 该指令是要将一个数送到A累加器，而该数是在这个代码的下一个存储单元。所以，执 行该指令还必须把数据（E0H）从存储器中取出送到CPU,即还要在存储器中取第二个 字节。其过程与取指阶段很相似，只是此时PC已为。。。1田指令译码器结合时序部件, 产生74H操作码的微操作系列，使数字E0H从。001H单元取出。因为指令是要求把取 得的数送到A累加器，所以取出的数字经内部数据总线进入A累加器，而不是进入指 令寄存器。至此，一条指令的执行完毕。单片机中PC="0002H", PC在CPU每次向存 储器取指或取数时自动加1,单片机又进入下一取指阶段。这一过程一直重复下去，直 至收到暫停指令或循环等待指令暂停。
cpu就是这样一条一条地执行指令,完成所有规定。

---

273. 什么函数不能声明为虚函数？

常见的不能声明为虚函数的有普通函数（非成员函数）、静态成员函数、内联成员函数、 构造函数和友元函数。以下将分别对这只种情况进行分析。
1） 普通函数（非成员函数）只能overload （重载），不能被override （覆盖），不 能 被声明为虚函数，，编译器会在编译时绑定函数。
2） 静态成员函数不能是虚函数，因为静态成员函数对于每个类来说只有一份代码，所 有的对象都共享这一份代码，它不归某个对象所有，所以，它也没有动态绑定的必要性。
3） 内联成员函数不能是虚函数，因为内联函数本身就是为了在代码中直接展开，减少 函数调用花费的代价而设立的,而虚函数至为了在继承后对象能够准确地执行自己的动 作，这是不可能统一的。再说，inline函数在编译时被展开，虚函数在运行时才能动 态地绑定函数。
4） 构造函数之所以不能是虚函数，因为或I造函数本来是为了明确初始化对象成员才产 生的，虚函数主要是为了在不完全了解细节的情况下也能正确处理对象。，虚 函数是在不同类型的对象产生不同的动作，现在对象还没有产生，如何使用虚函数来完 成你想完成的动作？
5） 友元函数。C++语言不支持友元函数钓继承，对于没有继承特性的函数没有虚函数 的说法。友元函数不属于类的成员函数，不能被继承。所以，友元函数不能是虚函数。

---

274. 在函数内定义一个字符数组，用gets函数输入字符串的时候，如果输入越界，为什么程序会崩溃？

因为gets无法截断数组越界部分，会将所有输入都写入内存，这样越界部分就可能覆 盖其他内容，造成程序崩溃。

---

275. 线上CPU爆高，请问你如何找到问题所在。

1、 命令Linux命令。可以查看实时的CPU使用情况。也可以查看最近一段时间 的CPU使用情况。
2、 PS命令Linux命令。强大的进程状态监控命令。可以查看进程以及进程中线程的 当前CPU使用情况。属于当前状态的采栏数据。
3、 jstack Java提供的命令。可以查看某个进程的当前线程栈运行情况。根据这个 命令的输出可以定位某个进程的所有线程的当前运行状态、运行代码，以及是否死锁等
4、pstack: Linux命令。可以查看某个进程的当前线程栈运行情况。

---

276. 从innodb的索引结构分析，为什么索引的key长度不 能太长？

key太长会导致一个页当中能够存放的key的数目变少，间接导致索引树的页数目变 多，索引层次増加，从而影响整体查询变更的效率。

---

277. MySQL的数据如何恢复到任意时间点？

恢复到任意时间点以定时的做全量备份，以及备份増量的binlog日志为前提。恢复 到任意时间点将全量备份恢复之后，再此基础上回放増加的binlog直至指定的 时间点。

---

278. 曹操南下攻打刘备，刘备派关羽守锦州，关羽派张飞去守城 门。刘备又派诸葛亮去向孙权求援。孙权派兵攻打曹操.请画 岀UML图.

279. 信号的生命周期？

信号产生-》信号在进程中注册-》信号在进程中的注销-》执行信号处理函数

---

280. 信号的产生方式？

（1） 当用户按某些终端键时产生信号

（2） 硬件异常产生信号【内存非法访问】

（3） 软件异常产生信号【某一个条件达到时】

（4） 调用kill函数产生信号【接受和发送的所有者必须相同，或者发送的进程所有 者必须为超级用户】（5）运行kill命令产生信号

---

秋招大厂经典面试题及答案整理不断更新中，感兴趣且正在学习的同学可以点个关注；狮会不断更新文章连载，有问题或者见解可以评论区讨论。