SYSTEM
多益网络笔试错题整理
src/content/notes/growth/笔试.md 多益网络笔试错题整理
考试情况回顾:选择题大量二叉树、二分查找;4道简答题,只完整答出第2题时间复杂度,其余简答空白;编程题思路方向正确,但代码逻辑、边界处理出错,未能运行通过。
简答题1:怎么用两个栈实现队列,讲一下实现方式
原题:简述使用两个栈实现队列的实现方式。
你的答题情况:未作答
标准答案(笔试答题卡简短版)
栈特性是后进先出LIFO;队列特性先进先出FIFO。使用两个栈:inStack输入栈、outStack输出栈。
-
入队push:元素直接压入
inStack; -
出队pop
:
-
如果
outStack为空,把inStack全部元素依次弹出,压入outStack; -
如果
outStack不为空,直接弹出
outStack栈顶;
注意:不要每次出队都倒栈,仅outStack空的时候才迁移元素。每个元素最多两次入栈出栈,摊还时间复杂度O(1)。
-
-
取队头逻辑同出队,只查看栈顶,不弹出元素。
解题思路
利用两次栈反转,把后进先出转为先进先出;inStack只管接收新元素,outStack只管对外输出,减少元素来回搬运,保证效率。
你的思考&踩坑反思
看过原理,脑子里懂,但不能压缩成笔试书面文字输出。后续训练:看完题,强迫自己手写3‑6行简短答案,不要只在脑子里想。
// 核心伪代码
push(x): inStack.push(x);
pop():
if(outStack.isEmpty()){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
return outStack.pop();
简答题2:哈希表、二叉树、链表的时间复杂度,哈希表和二叉树在什么情况下效率低下
原题:写出哈希表、链表、二叉搜索树查找、插入、删除的时间复杂度;说明哈希表、二叉搜索树分别在什么场景效率低下。
你的答题情况:完整写出,本题得分
标准答案
| 数据结构 | 平均(查找/插入/删除) | 最坏(查找/插入/删除) |
|---|---|---|
| 单向链表 | O(n)/O(1)/O(n) | O(n)/O(1)/O(n) |
| 哈希表 | O(1)/O(1)/O(1) | O(n)/O(n)/O(n) |
| 普通二叉搜索树BST | O(logn)/O(logn)/O(logn) | O(n)/O(n)/O(n) |
注意:红黑树/AVL平衡二叉树最坏依旧O(logn)。
效率低下场景:
- 哈希表:哈希函数不均匀,大量key发生哈希冲突;负载因子过高不及时扩容,冲突链表过长,性能退化到O(n)。
- 普通二叉搜索树BST:输入数据有序或者接近有序,树退化成单链表,高度等于节点数量,增删查退化为O(n)。
解题思路
平均是理想情况;最坏是发生退化;区分普通BST和平衡二叉树。
你的思考&踩坑反思
本题掌握不错,记住:题目说二叉树,笔试一般指普通二叉搜索树,不是红黑树。
简答题3:讲一下什么是大端存储模式和小端存储模式
原题:简述大端存储模式、小端存储模式。
你的答题情况:未作答
标准答案(笔试答题卡简短版)
大小端是多字节数据在内存中的字节排布顺序,以4字节整数0x12345678举例:
- 大端模式Big‑Endian:高字节存内存低地址,低字节存内存高地址。 内存地址从低到高:
12 34 56 78;网络TCP/IP协议默认使用大端,符合人类阅读习惯。 - 小端模式Little‑Endian:低字节存内存低地址,高字节存内存高地址。 内存地址从低到高:
78 56 34 12;x86 PC CPU本机默认小端。
解题思路
记忆口诀:大端:高字节放前面(低地址);小端:低字节放前面(低地址)。
你的思考&踩坑反思
属于计算机组成原理知识点,平时看的少,没有记忆简短答题模板。不需要深挖复杂底层,背下定义+例子即可应付笔试简答。
简答题4:事务隔离有哪些锁机制
原题:MySQL InnoDB事务四个隔离级别对应的锁机制。
你的答题情况:未作答
标准答案(笔试答题卡简短版)
MySQL InnoDB四个隔离级别从低到高:
-
读未提交 Read Uncommitted:几乎不加锁,可以读到未提交数据,脏读、不可重复读、幻读都存在。
-
读已提交 Read Committed(RC):写操作加排他锁;共享锁读完立刻释放;依靠MVCC快照读解决脏读;存在不可重复读、幻读。无间隙锁。
-
可重复读 Repeatable Read(RR,MySQL默认)
:
- 普通select快照读,不加锁,依靠MVCC多版本实现可重复读;
select ... for update等当前读,使用临键锁(Next‑Key Lock,行锁+间隙锁),解决幻读问题。
-
串行化 Serializable:所有读操作加共享锁,写加排他锁;全部串行执行,全部并发问题解决,并发性能最低。
关键区分:快照读不加锁;当前读才会加行锁、间隙锁、临键锁。
解题思路
隔离级别 = MVCC + 锁机制组合;RC没有间隙锁,RR才有临键锁防止幻读。
你的思考&踩坑反思
MySQL八股看过概念,但没有整理简答版文字,考试写不出来。笔试简答题不要写长篇博客,抓关键点分条写。
编程题:字符串里面提取整数求和
题目:给一个字符串,找出里面连续整数求整数和。例:
aa1bb3cgh321ls,输出1+3+321 = 325。
你的答题情况
思路方向正确:遍历字符串,区分字母数字;但是代码逻辑错误,程序无法运行。 你的错误点:
- 直接拿数组下标
arr[i‑1],不能正确累积多位数(例如321),应当维护独立变量curNum; - 字符char没有做
c‑'0'转换,直接拿ASCII码参与运算; - 遇到字母直接赋值0,逻辑错误,应该把已经拼接好的数字累加进总和,重置临时变量;
- 边界漏洞:字符串末尾是数字,循环结束后忘记再累加一次curNum,会漏掉末尾数字。
参考Java完整代码
public class Test {
public static void main(String[] args) {
String s = "aa1bb3cgh321ls";
System.out.println(getSum(s));
}
public static int getSum(String s) {
int sum = 0;
int curNum = 0; // 保存正在拼接的连续数字
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
// 字符转数字,拼接多位数
curNum = curNum * 10 + (c - '0');
} else {
// 遇到非数字,把当前数字加到总和,重置临时变量
sum += curNum;
curNum = 0;
}
}
// ⚠️关键边界:字符串以数字结尾,循环结束还要再加一次
sum += curNum;
return sum;
}
}
输出结果:325
解题思路
维护curNum变量累积连续数字;遇到非数字就结算;循环结束处理末尾数字边界。
你的思考&踩坑反思
现象:思路能想明白,翻译成代码就出错,边界条件考虑不全。 以后写这类题目强制自查两点: 1)字符是否执行
c‑'0'; 2)循环结束,是否处理末尾还未结算的数字。
整体笔试总结复盘
1、暴露的问题
- 简答类:看得懂 ≠ 笔试写得出 很多知识点脑子里理解,但没有提炼简短书面答案,考试空白丢分。以后复习简答题,必须动手写简短版本,不要只阅读。
- 算法编码:思路有,但是细节、边界、类型转换容易翻车 逻辑大体方向对,但字符‑数字转换、循环结束边界这类小坑直接导致整题0分。
- 选择题短板:二叉树、二分查找基础薄弱 本次选择大量二叉树、二分,这部分刷题量不足,是接下来要补齐的重点。
- 知识点分布:除了数据结构,还要覆盖计组基础(大小端)、MySQL锁与隔离级别,广东央国企、中厂笔试高频出现。
2、后续复习行动计划(适配BIGO、视源、广东各大央国企笔试)
① 简答题专项训练(必背简答模板)
-
两个栈实现队列
-
大端小端存储
-
MySQL四大隔离级别、锁机制、脏读/不可重复读/幻读
训练方法:看到题目,手写3‑6行答案,模拟答题卡。
② 算法刷题优先级
- 字符串简单:LeetCode 8(字符串转换整数),重点训练字符与数字转换、多位数拼接。
- 二叉树简单题:94中序遍历、104最大深度、102层序遍历;掌握二叉搜索树BST特性,应付选择题。
- 二分查找基础:LeetCode704、35,搞懂边界。
- 手撕数据结构:两个栈实现队列,脱离答案手写代码。
③ 考试做题习惯改进
- 编程写完代码强制检查2个边界:末尾数据处理、字符类型转换。
- 简答题哪怕记不全,尽量分点写,不要完全空白。