虾皮 9.29 笔试：选择题加三道编程题

《面试题目》

笔试结构：单选 20 道（40 分）、多选 5 道（15 分）、编程 3 道（45 分）；选择题主要考操作系统、计算机网络和数据结构。

1. 编程题一：最长回文子串，返回所有最长的回文子串
2. 编程题二：返回 XML 的值
3. 编程题三：一个字符串只含有两个字符，要求每两个相邻字符不同，求最小操作次数

《参考解析》

1. 返回「所有」最长回文子串，难点在全部而不是最长：中心扩展最好写，枚举 2n-1 个中心向两边扩，同时维护最大长度和结果集合；关键是扩到最大长度时不能马上返回，要继续扩到不行为止，否则会漏掉同长度的解。奇中心和偶中心都要枚举，长度 0 与 1 的边界单独处理，多个解要去重。想压复杂度可以上 Manacher，但笔试里写对、写完整通常比写得妙更值分。

2. XML 解析是模拟题，分都丢在边界上：用栈匹配标签名，遇到开标签入栈、闭标签出栈并校验配对，自闭合标签单独处理，取值时注意属性和嵌套层级。真正容易出错的是空标签、标签里带空格换行、只给一段片段而不是完整文档这几种情况——先把分支列清楚再落代码。

3. 「相邻不同」的最小操作是一道状态 DP：把「处理到第 i 位、最后一位放的是哪个字符」作为状态，转移时枚举当前位放哪个字符，按题目定义的操作累加代价取最小。只有两个字符时状态数就是 2，空间还能压成两个变量。这类题还要特别注意空值处理：空串、长度为 1 的串要单独返回 0，用例往往就藏在这里。

4. 选择题性价比最高，但覆盖面要铺开：这类笔试的选择题基本落在操作系统、计算机网络与数据结构三块——进程与线程、内存管理与分页、调度算法、TCP 与 HTTP、排序查找的复杂度。多选要留意「正确项可能不止一个」，别按单选的习惯只挑一个。