面灵AI→

全量全速 后台开发 一面:快排复杂度、DNS 顺序与跳跃游戏

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

《面试题目》

  1. 快速排序的平均和最坏时间复杂度分别是多少,如何证明?
  2. 为什么浮点数相减可能得不到预期的十进制结果?
  3. 浏览器输入一个网站地址并回车,到页面显示出来,中间经历了哪些步骤?
  4. DNS 查询的顺序是什么?
  5. 给定长度为 n 的正整数数组 a,从下标 0 开始,在位置 i 可以向前跳 1 到 a[i] 格。如何用最少的步数跳出数组,即到达下标至少为 n 的位置?动态规划怎么做?
  6. 上一题能否使用贪心算法?贪心的目标是什么?如何证明正确性?
  7. 贪心实现需要维护哪些变量?如何更新步数和边界?什么时候返回?复杂度是多少?
  8. 候选位置的覆盖范围可能重叠,为什么仍然可以做到 O(n)?如何避免重复扫描?
  9. 介绍个人项目。
  10. 能否提前实习?

《参考解析》

快排复杂度与证明:平均 O(n log n),最坏 O(n²),空间 O(log n)(递归栈)。平均情况的分析:每次划分的枢轴位置随机,递归树的期望深度是 O(log n),每层划分的总代价是 O(n),所以期望 O(n log n)。更严格的做法是用指示器随机变量求比较次数的期望,任意两个元素被比较的概率是 2/(j-i+1),求和得到 O(n log n)。最坏情况是每次划分都极不均衡(已排序数组且取首元素为枢轴),递归深度 n,代价 n + (n-1) + … = O(n²)。避免方式:随机选枢轴、三数取中、小数组切换插入排序、三路划分处理大量重复元素、递归深度过大时改用堆排序(内省排序)。

浮点数精度:IEEE 754 用二进制表示,很多十进制小数(如 0.1、0.2)无法用有限位二进制精确表示,只能存近似值;两个近似值相减会把误差暴露出来,甚至出现「大数吃小数」(数量级差太多时小数被舍入掉)。0.1 + 0.2 != 0.3 就是这个原因。解法:金额用整数分或 Decimal 类型;比较浮点数用误差范围而不是相等;避免用浮点数做大数加小数;需要精确十进制运算时用定点数或高精度库。

浏览器输入网址到页面显示:URL 解析(协议、域名、端口、路径);查缓存(浏览器缓存、DNS 缓存、系统 hosts);DNS 解析得到 IP;建立 TCP 连接(三次握手),HTTPS 还要 TLS 握手;发送 HTTP 请求(请求行、头、body);服务端处理并返回响应(可能经过 CDN、负载均衡、反向代理、应用服务器、数据库);浏览器解析响应(HTML 解析建 DOM、CSS 解析建 CSSOM、合成渲染树、布局、绘制、合成);加载子资源(JS、图片、字体)并执行 JS(可能阻塞解析);页面完成加载并触发 load 事件。要能说清关键路径上的阻塞点:CSS 阻塞渲染、同步 JS 阻塞解析、DNS 与 TCP 是串行的往返。

DNS 查询顺序:浏览器 DNS 缓存 → 操作系统缓存(含 hosts 文件)→ 本地 DNS 服务器(递归查询)→ 根域名服务器 → 顶级域名服务器 → 权威域名服务器。递归查询由本地 DNS 代劳,迭代查询由本地 DNS 逐级询问。结果按 TTL 缓存。补充:现代浏览器有预解析(DNS prefetch)、HTTP/2 与 HTTP/3 的连接复用会减少解析次数。

跳跃游戏的最少步数:动态规划定义 dp[i] 为到达下标 i 的最少步数,转移是 dp[j] = min(dp[j], dp[i] + 1) 对所有 i < j <= i + a[i],时间 O(n²)。贪心解法:维护当前这一步能到达的最远边界 end、在边界内能到达的最远位置 maxReach、步数 steps。遍历数组,每到一个位置更新 maxReach = max(maxReach, i + a[i]);当 i == end 时说明当前步数能覆盖的范围已用完,必须再跳一步,steps++、end = maxReach;若 end >= n 则返回步数。正确性来自「在一步可达的范围内,选择能跳最远的那个位置不会比任何其他选择差」——这是贪心选择性质,可用交换论证证明:把最优解中该步的选择替换为最远可达位置,后续仍可行且步数不变。复杂度 O(n)、空间 O(1)。范围重叠不影响正确性,因为每个位置只被访问一次,maxReach 是单调不减的,遍历一次即可覆盖所有候选。