模拟面试2-豆包

• 10亿规模的数据找出top100的方法

  回答模板：

  1. 单机 — 小根堆（首选回答）

     我会用一个大小为100的小根堆流式遍历数据。遍历时每个元素只与堆顶比较，大于堆顶就替换并调堆，否则跳过。时间复杂度是 \(O(N \log K)\)，\(K=100\) 相当于常数，非常高效，内存只需维护100个元素

  2. 分布式 — 分治 + 归并（加分项）

     还可以将10亿条数据按哈希分片到 M 台机器 → 每台机器各自用小根堆求局部 Top100 → 汇总M×100条结果到主节点 → 主节点再做一次堆排序取全局 Top100

  追问：

  • 数据有重复怎么办？ 按值计数后再排序；或去重后走同样流程
  • 实时流数据？ 改用动态维护的堆，或近似算法如 Count-Min Sketch

  ---

• 红黑树与跳表的应用区别

  回答模板：

  两者时间复杂度相同，核心区别在于工程特性。红黑树适合点查，Java/C++ 标准库都用它。跳表在范围查询和并发场景更优，Redis 的 ZSet 就用跳表，因为范围查询是高频操作，且跳表用 CAS 就能无锁并发，实现比红黑树简单得多.

  • 红黑树：

    平衡二叉树，严格 \(O(\log N)\) 节点内存不连续，缓存不友好 实现复杂（旋转+变色） 不支持范围查询的顺序遍历 并发锁竞争激烈

  • 跳表： 多层链表，期望 \(O(\log N)\) 顺序存储，缓存友好 实现简单，易于理解 天然支持范围查询 用 CAS 即可实现无锁并发

  • 红黑树的代表应用：

    • C++ STL std::map / std::set

    • Java TreeMap / TreeSet

    • Linux内核进程调度（CFS）、虚拟内存管理

  • 跳表的代表应用

    • Redis 有序集合 ZSet 底层实现

    • LevelDB 内存 MemTable 结构

    • Lucene 索引查找

  ---

• 进程和线程的区别

  回答模板：

  进程是资源隔离的单位，有独立地址空间；线程是调度执行的单位，共享进程内存。进程间切换要刷页表，开销大但隔离性强；线程切换快但需要锁来保证数据安全。Chrome 用多进程保证稳定性，Java Web 服务器用多线程提升并发——工程上根据隔离性和性能要求来选

  • 进程（Process）

    独立地址空间（虚拟内存） 拥有独立的：代码段、数据段、堆、栈、文件描述符 崩溃不影响其他进程 切换开销大（需刷新 TLB、页表） 通信需要 IPC（管道、共享内存、Socket）

  • 线程（Thread）

    共享进程地址空间 独立的：程序计数器、寄存器、栈 共享：堆、全局变量、文件句柄 切换开销小（不换页表） 通信直接读写共享内存（需加锁）

  ---

• 浏览器输入网址之后跳转的原理过程

  回答模板：

  整个过程分五层：先是DNS 解析拿到 IP；然后TCP 三次握手建连（HTTPS 还有 TLS 握手）；接着发送HTTP 请求，服务器处理后返回响应；最后浏览器解析 HTML/CSS 渲染页面。面试官想深聊哪层我都可以展开.

  • URL 解析 & 缓存检查：判断是 URL 还是搜索词；检查浏览器缓存（强缓存 Cache-Control）
  • DNS 解析（递归查询）：浏览器缓存 → 系统 hosts → 本地 DNS → 根 DNS → 权威 DNS，返回 IP
  • TCP 三次握手建立连接：SYN → SYN+ACK → ACK；HTTPS 还需要 TLS 握手（证书验证 + 密钥交换）
  • 发送 HTTP 请求：请求行（GET/POST）+ 请求头（Cookie、User-Agent）+ 请求体
  • 服务器处理并返回响应：路由分发 → 业务逻辑 → 数据库查询 → 返回 HTML（状态码 + 响应头 + 响应体）
  • 浏览器解析 & 渲染：解析 HTML 构建 DOM → 解析 CSS 构建 CSSOM → 合并为渲染树 → 布局 Layout → 绘制 Paint
  • TCP 四次挥手断开连接：或 HTTP Keep-Alive 复用连接

  ---

• 手撕：LeetCode 5 最长回文子串

  一个DP题目.