面灵AI→

某公司软件开发一面:括号匹配手撕之后,从数据结构问到红黑树、编译过程与死锁

轮次
一面
时间
2026-11
来源
牛客网

《面试题目》

手撕与数据结构

  1. 手撕:括号匹配,先说一下思路。
  2. 说一下你了解的数据结构。
  3. 二叉树了解吗?
  4. 红黑树是什么?
  5. 二叉树的遍历方式有哪几种?

编译与内存

  1. 程序的编译过程分为哪几个阶段?
  2. 内联函数是什么?
  3. 内存管理是怎么做的?

死锁

  1. 死锁在什么场景下会出现,怎么避免?
  2. 「互斥等待」具体指什么?

项目

  1. 具体介绍一下你的项目,并准备接受针对项目细节的追问。

《参考解析》

括号匹配:先说思路再动手:这类题的标准解法是栈——遇左括号入栈,遇右括号检查栈顶是否为对应的左括号,匹配则弹出,不匹配或栈空即返回失败,遍历结束后栈必须为空。时间复杂度 O(n)、空间 O(n)。口述思路时按「用什么结构、每步做什么、什么条件下提前返回、结束后还要检查什么」四句讲完,再写代码;边界要主动交代:空串、只有一个字符、交叉嵌套(([)])、多余的右括号、只有左括号。若面试官追问,可以补一句「只有一种括号时可以用计数器把空间降到 O(1),多种括号必须用栈保存顺序」。

数据结构与二叉树:回答不要罗列名词,按「逻辑结构 + 典型实现 + 适用场景」组织:数组与链表(随机访问与插入删除的取舍)、栈与队列(以及单调栈、优先队列这类衍生结构)、哈希表(平均 O(1) 查找,冲突用链地址法或开放寻址)、树(二叉搜索树、平衡树、堆、字典树)、图(邻接表与邻接矩阵)。二叉树要能说清满二叉树、完全二叉树、二叉搜索树、平衡二叉树各自的约束,以及完全二叉树用数组存储时父子下标的关系。

红黑树:它是一棵带颜色约束的二叉搜索树,五条性质是:节点非红即黑、根为黑、叶子(NIL)为黑、红节点的子节点必为黑、任一节点到其所有叶子的路径上黑节点数相同。后两条保证最长路径不超过最短路径的两倍,因此树高为 O(log n)。与 AVL 相比,红黑树对平衡的要求更松,插入删除时的旋转次数更少,读多写少选 AVL、增删频繁选红黑树。工程中的典型位置是 C++ std::map / std::set、Java 的 TreeMap 与 HashMap 的树化桶、Linux 内核的 epoll 就绪队列与 CFS 调度器。

二叉树遍历:前序(根左右)、中序(左根右)、后序(左右根)、层序(按层,用队列)。递归写法只需三行,面试更常考迭代:前序用栈并先压右再压左,中序沿左链入栈再弹出访问,后序可用「根右左」的前序变体再反转,层序用队列并记录每层长度。延伸考点是「由前序加中序还原二叉树」(前序定根、中序分左右区间)与 Morris 遍历(利用空闲右指针做到 O(1) 空间)。

编译过程与内联函数:以 C/C++ 为例分四个阶段:预处理(展开宏、处理 #include 与条件编译,产出翻译单元)、编译(词法、语法、语义分析与优化,生成汇编)、汇编(汇编器把汇编翻译成机器码,产出可重定位目标文件)、链接(符号解析与重定位,合并段、处理静态库与动态库,产出可执行文件)。内联函数是在调用点把函数体展开,省去压栈、跳转与返回的开销,并为跨函数优化创造条件;代价是代码体积膨胀、指令缓存命中率下降。inline 只是对编译器的建议而非强制,类内定义的成员函数隐式内联;递归函数、取地址的函数、虚函数调用通常无法内联;调试时内联会让断点与调用栈失真。

内存管理:从两个层面回答。语言层面:栈上分配随作用域自动回收,堆上分配需要显式释放或由 GC / 智能指针 / RAII 管理;要能说出内存泄漏、悬垂指针、重复释放、越界这几类问题的成因与排查手段(Valgrind、AddressSanitizer、堆快照对比)。系统层面:malloc 在小块内存上用空闲链表加 bins,大块用 mmap;内核用伙伴系统管理物理页、用 slab / slub 分配器服务小对象;虚拟内存通过页表把虚拟地址映射到物理页,缺页时触发调页。碎片分为内部碎片与外部碎片,前者来自对齐与固定块大小,后者来自空闲块不连续。

死锁与「互斥等待」:死锁需要四个条件同时成立:互斥(资源一次只能被一个进程占用)、占有并等待(持有已分配资源的同时申请新资源)、不可抢占(资源只能由持有者主动释放)、循环等待(存在进程与资源的环形等待链)。「互斥等待」问的就是前两条——资源排他占用,且进程在等新资源时不放弃已持有的资源,这两条同时成立才可能形成僵持。常见场景是多个线程以不同顺序申请多把锁、数据库事务交叉更新多行、线程池里任务互相等待对方的结果。避免手段对应破坏条件:全局统一的加锁顺序(破坏循环等待)、一次性申请全部资源(破坏占有并等待)、tryLock 加超时后退重试(破坏不可抢占)、把临界区缩到最小并按资源类型分锁(降低互斥范围)。检测侧可用资源分配图找环,或用 jstack、gdb 抓取等待链。

项目介绍怎么讲:一面时间有限,用「一句话定位 + 我的模块 + 一个技术难点 + 一个结果」四段讲完,主动留一个自己熟悉的追问点。避免按时间流水账讲需求背景,也不要只讲业务功能而不讲技术决策。被追问细节时,答不上的部分明确说「这块是同事负责的,我了解到的是……」,比临场编造更安全。