博思软件Python二面：语言特性与数据结构基础

《面试题目》

1. 拷打项目（因人而异）。
2. Python 是编译型语言还是解释型语言？编译型语言和解释型语言有什么区别？
3. 数据结构与算法相关：二叉搜索树的时间复杂度？二叉平衡树的时间复杂度？
4. 为什么二叉平衡树可以提高检索效率？不平衡状态下最坏时间复杂度是多少？
5. 知道哪些排序算法？分别说一下时间复杂度。
6. 协程、进程和线程的区别？
7. 操作系统能不能看见进程？能不能看见线程？
8. HTTP 和 HTTPS 的区别？HTTPS 的 S 是对什么进行加密了？
9. 解释一下 TCP 和 UDP。

《参考解析》

Python 是编译型还是解释型：严格说两者都不是——Python 是「先编译成字节码、再由虚拟机解释执行」的语言。CPython 执行 import 或脚本时，先把源码编译成字节码（__pycache__/*.pyc），然后由 CPython 虚拟机逐条解释执行；exec/eval 编译的也是字节码。所以它有编译阶段，但没有生成机器码（除非用 PyPy 的 JIT、Cython、Nuitka 这类工具）。对比：编译型语言（C/C++/Rust/Go）在运行前把整个程序翻译成目标平台机器码，运行期没有翻译开销、执行快、能提前发现类型与语法错误，但需针对平台分别编译；解释型语言（传统意义上的 JS/Python/Shell）逐行或逐字节码翻译执行，跨平台、开发迭代快，代价是运行慢、错误延迟暴露。补充一个常考的点：Python 的「动态类型 + 解释执行」是它慢的主因之一，优化手段有向量化（NumPy）、C 扩展、JIT（PyPy）与多进程绕开 GIL。

二叉搜索树与平衡树的时间复杂度：BST 的查找/插入/删除平均是 O(log n)，但取决于树的形状——数据有序插入时会退化成链表，最坏 O(n)；平衡二叉树（AVL、红黑树）通过旋转维持高度为 O(log n)，因此查找/插入/删除最坏都能保证 O(log n)。为什么平衡能提升检索效率：查找的代价等于「从根走到目标节点的路径长度」，也就是树高；每次比较都能排除一整棵子树，只有树足够矮（近似满二叉树，高度约 log₂n）时才能每步排除一半。AVL 严格平衡（左右子树高度差不超过 1），查询更快但插入删除旋转更频繁；红黑树放松平衡条件（最长路径不超过最短路径的两倍），旋转次数少，所以被 Java 的 TreeMap、HashMap 树化阈值、Linux 的 CFS 调度器选中。顺带记住：n=100 万 时 log₂n ≈ 20，这就是索引能扛住大数据量的直观解释。

常见排序算法与复杂度：冒泡/选择/插入排序平均 O(n²)、最好情况插入排序 O(n)（近乎有序时）且稳定；希尔排序平均约 O(n^1.3)、不稳定；归并排序稳定，最好/最坏/平均都是 O(n log n)，代价是 O(n) 额外空间；快速排序平均 O(n log n)、最坏 O(n²)（每次选到极值作为 pivot）、不稳定、原地（递归栈 O(log n)）；堆排序三者都是 O(n log n)、原地、不稳定；计数/桶/基数排序在特定条件下能到 O(n + k)，但要求数据范围有限。工程实践上，Python 的 sorted() 用 Timsort（归并 + 插入的混合，稳定，对真实数据接近 O(n)），Java 对基本类型用双轴快排、对对象数组用 Timsort（要稳定性）。面试经常顺带问「稳定排序的意义」：多关键字排序时，先按次关键字排、再按主关键字排，稳定性保证第一次的顺序不被破坏。

协程、进程、线程：进程是资源分配的最小单位，拥有独立地址空间、文件描述符、信号处理与页表，进程间隔离好但切换和通信（管道、共享内存、socket）成本高；线程是 CPU 调度的最小单位，同一进程内的线程共享地址空间与堆，各有自己的栈和寄存器，切换比进程轻但仍然由内核调度、有锁与竞态问题；协程是用户态的轻量执行单元，由程序自己（事件循环/调度器）切换，不进入内核、没有系统调用开销，所以能轻松开出几十万个，但一个协程阻塞住线程就会拖住同一线程上的所有协程，因此协程只适合 I/O 密集场景，且必须用「非阻塞 + 事件循环」的配合（Python 的 asyncio、Go 的 goroutine 由 runtime 做 M:N 调度）。对比维度建议按「隔离性/切换成本/并发规模/适用场景」来答。Python 还要提 GIL：CPython 里同一时刻只有一个线程执行字节码，所以多线程无法利用多核做 CPU 密集计算，此时要用多进程或把计算下沉到 C/NumPy；I/O 密集场景 GIL 会在阻塞时释放，多线程仍有效。

操作系统能不能看见进程和线程：能看见进程，线程的可见性取决于视角。内核当然管理线程——Linux 里线程就是「共享地址空间的 task」，用 clone() 创建，ps -eLf/top -H 能看到同一进程下的多个 LWP（轻量级进程），/proc/<pid>/task/ 下每个线程一个目录，所以内核与调度器完全「看得见」。但操作系统通常不把线程作为资源分配和隔离的单位（不给线程单独地址空间），对外接口（如 kill、wait、权限模型）以进程为粒度，所以「操作系统看不见线程」这个说法只在「资源管理与隔离粒度」的意义上成立。用户态线程（goroutine、协程）内核确实看不见——它们由 runtime 复用若干个内核线程，ps 只能看到那几条内核线程。答题时先分清「内核态线程（1:1）」「用户态线程（N:1）」「混合/多对多（M:N）」三种模型，就不会被绕进去。

HTTP 与 HTTPS 的区别，S 加密了什么：HTTPS = HTTP + TLS/SSL，默认端口从 80 变成 443，多了加密、完整性校验与身份认证。加密是分层的：握手阶段用非对称加密（RSA 密钥交换或 ECDHE，后者具备前向安全）协商出一个共享的对称密钥，并对服务器证书做校验（证书由 CA 签发，验证域名、有效期与吊销状态，防止中间人）；数据传输阶段用对称加密（AES-GCM 或 ChaCha20-Poly1305）加密应用层数据，同时用 AEAD/MAC 保证完整性防篡改。所以「S 加密的是 HTTP 报文」这句话只对了一半——它加密的是「HTTP 报文 + 头部」，也就是整个应用层数据（包括 URL 路径、Cookie、请求体）；但目标域名/IP 在握手阶段会通过 SNI 与 DNS 暴露，TLS 1.3 已把大部分握手字段加密，SNI 的加密要靠 ECH。另外 HTTPS 不能防「服务端本身泄露数据」，也不能防应用层漏洞（XSS/SQLi），它只解决传输安全。性能上 TLS 握手增加 1~2 个 RTT，靠会话复用、TLS 1.3 的 0-RTT、HTTP/2 多路复用与 CDN 边缘终结来抵消。

TCP 与 UDP：TCP 面向连接、可靠、有序、面向字节流，有三次握手四次挥手、超时与快速重传、序号与确认、滑动窗口做流量控制、拥塞控制（慢启动、拥塞避免、快重传快恢复），头部 20 字节起，代价是延迟与开销；UDP 无连接、不可靠、无序、面向报文，头部只有 8 字节，不保证送达也不重传，因此延迟低、开销小、支持广播/组播，需要可靠性时由应用层自己实现（QUIC 就是「UDP + 自研可靠传输 + 多路复用 + 0-RTT」，避免了 TCP 的队头阻塞与内核升级缓慢问题）。选型口诀：要可靠性用 TCP（文件传输、HTTP、数据库连接、消息队列），要实时性且能容忍少量丢包用 UDP（音视频通话、直播、游戏同步、DNS 查询——DNS 之所以用 UDP 是查询报文小、一次往返即可，超过 512 字节或响应被截断时切到 TCP）。还要能说清「TCP 三次握手为什么不是两次」：防止历史延迟的连接请求造成服务端建立无效连接并浪费资源，同时确认双方收发能力都在；「四次挥手为什么多一次」：TCP 是全双工，任一方关闭都需要单独发 FIN 并得到 ACK，被动关闭方可能还有数据要发，所以 ACK 与 FIN 不能合并；以及 TIME_WAIT 存在 2MSL 是为了保证最后的 ACK 能到达并让旧连接报文自然消亡。