虾皮 10.14 笔试：子网划分、堆与三道编程题

《面试题目》

1. 主机 130.72.70.12，掩码 255.255.192.0，不经过路由器可以访问的 IP 有哪些？
2. 动态替换类的实现：不改变「调用的是哪个方法」的前提下替换类的实现，怎么做？
3. (m=a>b) && (n=c>d)，其中 m=n=2、a=5、b=6、c=7、d=8，表达式计算完后 n 的值是多少？
4. 小顶堆删除堆顶数字需要比较的关键字次数怎么算（堆基于选择排序的思路）？
5. 适配器模式的应用实例有哪些？
6. IPsec、DES 相关知识点。
7. 虚拟内存相关知识点。
8. 一致性哈希原理。
9. 编程题：判断字符串中各字符出现次数相同、或次数之差小于 1，返回 true。
10. 编程题：日程安排。
11. 编程题：输入两个二进制字符串，返回这两个二进制乘积的二进制字符串（ACM 模式，自己处理输入输出）。

《参考解析》

子网划分这题的关键是先把掩码翻译成前缀长度，再算块大小。 255.255.192.0 即 /18，第三个字节用了 2 位，块大小是 2^(24-18) = 64。把 70 按 64 分块：64 ≤ 70 < 128，所以网段是 130.72.64.0/18，广播地址 130.72.127.255，可用主机范围 130.72.64.1 ~ 130.72.127.254。题目问「不经过路由器可访问」，意思就是同一广播域内的地址，答案就是这个区间（要排除网络地址、广播地址以及已被占用的网关与主机地址）。这类题有两个常见陷阱：一是忘记 /18 的边界落在第三个字节而不是第四个，把范围算成 130.72.70.1~130.72.70.254；二是把「可访问」理解成「能 ping 通」，其实它只问网段。延伸追问一般是同网段可容纳主机数（2^(32-18) - 2 = 16382）、如何划分子网、以及两台主机是否同网段的判断方法（各自与掩码按位与比较网络号）。

「动态替换类的实现」考的是依赖倒置加运行时决定实现。 调用方只面向接口编程，实现的选取放在工厂、配置或容器里，替换就不需要改调用点。可用手段按侵入性排序：策略模式加工厂（最朴素，配置里写类名或枚举）、依赖注入容器按配置装配（Spring 的 @Conditional、@Profile、SPI 的 META-INF/services）、动态代理（JDK Proxy / CGLIB，在方法前后插行为，能不改原类就替换调用路径）、类加载器隔离（同一个接口不同版本共存，按租户隔离）、以及把实现搬到脚本或表达式引擎里做热改。答题时要点出「不改调用点」这个约束意味着编译期不能有具体类名，因此 new 必须被移出业务代码。追问通常是「替换后怎么保证兼容」——契约测试、灰度、以及新旧实现同时上线按开关切换。

短路求值题考的是副作用与运算符优先级，结论是 n 仍为 2、而 m 已经被改成 0。 (m=a>b) 里先算 a>b，5>6 为假，在 C/Java 里布尔表达式参与赋值会得到 0（Java 里这样写本身是编译错误，因为 boolean 不能赋给 int，所以这题默认按 C/C++ 语境），m 变成 0，整个左操作数为假，&& 立即短路，右侧的 n=c>d 完全不执行，n 保持原值 2。要提醒自己两点：一是很多人只看 n 忘了 m 已经变了；二是如果把 && 换成 &（不短路的按位与），右侧就会执行，n 变成 1，这个对比正是面试官想听的。工程上的结论是别把赋值和判断写在一起，可读性和调试成本都会变高。

小顶堆删除堆顶的比较次数按「下滤」的过程算。 删除堆顶后把最后一个元素放到堆顶，然后逐层向下调整：每一层要先把左右孩子比较一次选出较小的，再拿它和当前节点比较一次决定是否交换，所以每层最多 2 次比较；堆高是 ⌊log₂n⌋，因此最坏约 2⌊log₂n⌋ 次比较，最好情况（一次都比较不过、不用下沉）是 2 次（两个孩子比较 + 与较小者比较）。题目里提到「堆是选择排序」，指的是堆排序的选数过程：每一轮把堆顶换到末尾、堆规模减一，总比较次数是各轮之和，量级 O(n log n)。答这题时把「删除 → 补位 → 下滤 → 每层几次比较」的步骤讲出来，比只报一个数更稳。

适配器模式的实例要答出「接口不兼容但必须协作」这个共同点。 常见的有：Java 的 InputStreamReader 把字节流适配成字符流、Arrays.asList 把数组适配成 List、集合框架里把 Enumeration 适配成 Iterator；JDBC 驱动在各种数据库协议之上提供统一 API；Spring MVC 的 HandlerAdapter 让不同类型的 Controller 都能被统一调度；日志门面 SLF4J 屏蔽底层日志实现；业务上最常见的三类——对接第三方支付/短信 SDK（把对方签名、返回码翻译成内部统一模型）、老系统接口包装（新代码用新接口，内部转调老接口）、以及单测里用适配器把真实依赖替换成假实现。要顺带区分它和装饰器（装饰器加功能、接口不变）、代理（代理控制访问、接口一致）、外观（外观简化一组接口）的差别，这是最常见的追问。

IPsec 与 DES 这两个点要能说清定位。 IPsec 是网络层的安全套件，两个核心协议是 AH（只认证不加密，现已少用）和 ESP（加密 + 认证），工作模式分传输模式（只保护载荷，用于端到端）和隧道模式（整个原 IP 包被封装成新载荷，用于网关到网关的 VPN）；密钥与安全参数由 IKE 协商出 SA（安全关联），SA 决定了算法、密钥与生存期。DES 是 56 位密钥的分组密码（8 字节里每字节有一位奇偶校验），Feistel 结构 16 轮，今天已不安全（穷举可行），实际用的是 3DES（两密钥或三密钥）或 AES；面试里常顺着问分组模式（ECB 相同明文出相同密文、不安全；CBC 需要 IV；GCM 提供认证加密）与密钥交换（DH/RSA）这两条线。

虚拟内存的答题主线是「地址转换 + 缺页 + 置换」。 每个进程看到独立虚拟地址空间，CPU 用页表把虚拟页映射到物理帧，TLB 缓存最近的映射以减少多级页表访问开销；访问的页不在内存时触发缺页中断，由内核把页从磁盘换入（可能要先淘汰一页），被淘汰的脏页需要回写。置换算法常考 LRU（近似实现用 Clock 算法，靠访问位扫描）、FIFO（有 Belady 异常）与 OPT。工程相关的考点还有：mmap 把文件映射进地址空间实现零拷贝读写、写时复制（fork 后父子共享只读页，谁写谁复制）、swap 与 OOM Killer 的关系、以及为什么内存越大 TLB 和页表层级越重要（大页 HugePage 就是为了减少 TLB miss）。答的时候把「为什么需要虚拟内存」摆在最前面——隔离与保护、允许程序使用超出物理内存的空间、以及让内存分配与共享更灵活。

一致性哈希要讲清「解决什么问题」和「为什么要虚拟节点」。 普通取模 hash(key) % N 在节点数变化时几乎全部键都要搬迁；一致性哈希把节点和键都哈希到一个环上，键归属顺时针方向第一个节点，加节点时只有该节点与前一节点之间的数据需要迁移，删节点时只有它的数据要转移，平均迁移量约为 1/N。问题是节点少或哈希不均时，环上的分布会严重倾斜（一小段弧承载大部分键），所以引入虚拟节点：每个物理节点在环上映射成几百个虚拟节点，既让负载均衡，也让节点权重可调（性能强的机器多放几个虚拟节点）。要能主动说出它的局限：缓存的「雪崩/击穿」问题它只能缓解不能消除；节点故障时该节点承载的请求会全部压到下一个节点（可用「副本 + 多环」缓解）；以及哈希函数的均匀性很关键。

三道编程题分别考字符串统计、区间贪心与高精度乘法。 第一题按字符计数即可：遍历一遍统计每个字符出现次数，取最大最小值，判断是否相等或差值不超过 1（题面「次数之差小于 1」严格说等于全相等，实现时按「差值 ≤ 1」更稳妥，边界上「空串或单字符」直接返回 true），时间 O(n)、空间 O(字符集大小)。第二题「日程安排」这类题的通用套路是区间处理：若是求两堆空闲时间里的可用会议时段，做法是把两组区间分别排序后双指针求交集；若是判断能否插入新日程，用有序结构（TreeMap/平衡树）维护已有区间并按前驱后继判断重叠；若是求最多能参加多少场会议，按结束时间排序后贪心。答这类题先跟面试官确认是哪种变体，比闷头写快得多。第三题二进制字符串相乘是经典高精度乘法：把结果数组开成 len(a)+len(b)，从低位向高位双重循环累加（res[i+j+1] += int(a[i])*int(b[j])），再统一处理进位，最后去掉前导零、全零输出 “0”；也可以用竖式加法模拟（逐位与被乘数相乘再错位相加）。ACM 模式要自己处理输入输出，注意读取整行、去掉空白与换行，以及这题用语言自带的 BigInteger 是否被允许——大多数笔试允许，但面试官更想看你手写位数处理。