360 后端笔试：广告词拼接字典序最小与交错回文

《面试题目》

1. 笔试可以选哪些编程语言方向？为什么没有 JavaScript？
2. 选择题主要考哪些内容？
3. 编程题一：给定若干广告词，把它们全部拼接起来，使结果字符串的字典序最小，怎么求？
4. 编程题二：什么是「交错回文」，如何判断或构造？

《参考解析》

字典序最小拼接：排序规则不是字典序。 直觉上按字符串字典序排再拼是错的。经典反例："b" 与 "ba"——按字典序 "b" < "ba"，拼成 "bba"；但 "ba" + "b" = "bab" 更小。正确做法是自定义比较器：比较 a + b 与 b + a，若 a + b < b + a 则 a 排在前面。这个比较关系可以证明是传递的（可以按「无限重复串」理解：比较 a 与 b 就是比较 a∞ 与 b∞ 的字典序），所以直接用 sort(key=cmp_to_key) 即可得到最优顺序，复杂度 O(n log n · L)。Python 写法：

from functools import cmp_to_key
words.sort(key=cmp_to_key(lambda a, b: -1 if a + b < b + a else (1 if a + b > b + a else 0)))
print("".join(words))

要注意的边界：空串（a+b == b+a 时顺序无所谓）、前缀关系（上面那个反例）、以及输入里有重复词。这个套路也常被包装成「拼出最大的数」（把数字转字符串后同样比较 a+b 与 b+a）。

交错回文（interleaving palindrome）。 这类题通常有两种问法：判断一个串能否由两个回文串交错而成，或者给定两个串判断能否交错成回文。「交错」指保持各自相对顺序地合并。思路一：如果题目是「两个串交错后能否成为回文」，可以从两端向中间双指针匹配，状态是「串 A 用到第 i 个、串 B 用到第 j 个、当前匹配到首尾哪一对」，用记忆化搜索/区间 DP，状态数 O(|A|·|B|)，每个状态枚举「左端取 A 还是 B、右端取 A 还是 B」四种组合，复杂度 O(|A|·|B|)。思路二：如果问的是「一个串能否拆成两个回文子序列交错」，则等价于判断该串能否划分为两个回文子序列，可用 O(n²) 的 DP（dp[i][j] 表示前缀 i、另一个子序列末尾在 j 是否可行）。面试/笔试里先确认问法，再把「相对顺序不变」这个约束翻译成「双指针 + 状态」，通常就能落地。

贪心题的通用训练方法。 作者复盘说「贪心还得再看看」，这类题的共同点是「局部最优的选择需要证明」。练法是三步：① 先写暴力枚举小规模的所有方案，观察最优解的结构；② 猜一个贪心规则，用暴力对拍（随机生成上百组小数据比对）；③ 对拍通过后再想证明（交换论证：若最优解在某一步与贪心不同，交换两者不使结果变差）。对拍这一步最重要——很多「看起来对」的贪心（比如上面按字典序拼串）只有对拍才能发现反例。

语言选择的细节。 360 的笔试只给 Golang / Python 方向，说明岗位技术栈集中在这两个语言上。遇到「没有我熟悉的语言」时，优先选语法最接近、标准库最全的（Python 的 sort 支持自定义比较器、字符串处理方便），并在考前把该语言的输入输出模板背熟，避免在 IO 上浪费时间。