[干货] 微软内部面试题

[longSwordMan]

本人目前在微软带了一个开发团队，我们 team 主要负责 Search 这块，包括一些 NLP，CV 的 model 、后端的 high concurrent/available 的 service，作为一个在 MS 当了三四年面试官的工程师，早就已经知道现在的小朋友喜欢刷题，当时我也是丝毫没有头绪，一头埋进 leetcode 的题库里刷题，但是那些大厂的面试官也不是傻子，当然不可能傻傻的去考 leetcode 的原题，所以最好不要死记硬背，想要通过题海战术进入大厂。

我们作为面试官也出了很多面试题和改编题。我们几个微软、谷歌的 leader 根据我们作为面试官的一手出题经验，总结出了七条心决，也就是七条算法题的解题模板，我在后面的文字会慢慢分享。

我的微信：sxxzs3998，技术问题欢迎交流讨论，备注 V2EX + id 即可。

[longSwordMan]

给定一 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词，words + words[j] ，可拼接成回文串。
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

题目分析
如果字符串 S1 + S2 能构成一个回文串，把 S1 分成 S1_1 和 S1_2 两部分，可以有以下以下两种拼接情况：
①． S2 拼接在前，并且 S1_1 是回文串、S1_2 是 S2 的逆序；
②． S2 拼接在后，并且 S1_2 是回文串、S1_1 是 S2 的逆序；

[longSwordMan]

1.暴力
本题可以想到暴力做法，我们枚举每一对字符串的组合，暴力判断它们是否能够构成回文串即可。时间复杂度 O(n^2\times m)O(n^2 ×m)，其中 n 是字符串的数量，m 是字符串的平均长度。时间复杂度并不理想，考虑进行优化。

[longSwordMan]

2.枚举前缀和后缀
假设存在两个字符串 s1 和 s2，s1+s2 是一个回文串，记这两个字符串的长度分别为 len_1 和 len_2，我们分三种情况进行讨论：

1,len 1=len 2，这种情况下 s_1 是 s_2 的翻转。
2,len1>len2，这种情况可以将是 s1 拆成左右两部分 t_1 和 t_2，其中 t_1 是 s2 的翻转，t_2 是一个回文串。
也就是说，我们要枚举字符串 k 的每一个前缀和后缀，判断其是否为回文串。如果是回文串，我们就查询其剩余部分的翻转是否在给定的字符串序列中出现即可。
注意到空串也是回文串，所以我们可以将 k 拆解为 k+∅ 或 ∅+k，这样我们就能将情况 1 也解释为特殊的情况 2 或情况 3 。

而要实现这些操作，我们只需要设计一个能够在一系列字符串中查询「某个字符串的子串的翻转」是否存在的数据结构，有两种实现方法：

我们可以使用字典树存储所有的字符串。在进行查询时，我们将待查询串的子串逆序地在字典树上进行遍历，即可判断其是否存在。

我们可以使用哈希表存储所有字符串的翻转串。在进行查询时，我们判断带查询串的子串是否在哈希表中出现，就等价于判断了其翻转是否存在。

时间复杂度：O(n*m^2) )，其中 n 是字符串的数量，m 是字符串的平均长度。对于每一个字符串，我们需要 O(m^2)地判断其所有前缀与后缀是否是回文串，并 O(m^2)地寻找其所有前缀与后缀是否在给定的字符串序列中出现。

空间复杂度：O(n×m)，其中 n 是字符串的数量，m 是字符串的平均长度。为字典树的空间开销。

[longSwordMan]

3.字典树 + Manacher
注意到方法一中，对于每一个字符串 k，我们需要 O(m^2)地判断 k 的所有前缀与后缀是否是回文串，还需要 O(m^2) 地判断 k 的所有前缀与后缀是否在给定字符串序列中出现。我们可以优化这两部分的时间复杂度。
对于判断其所有前缀与后缀是否是回文串：
利用 Manacher 算法，可以线性地处理出每一个前后缀是否是回文串。

对于判断其所有前缀与后缀是否在给定的字符串序列中出现：
对于给定的字符串序列，分别正向与反向建立字典树，利用正向建立的字典树验证 k 的后缀的翻转，利用反向建立的字典树验证 k 的前缀的翻转。

不懂的同学可以去搜一下 Manacher 算法，这个算法在处理回文串方面可以把原来 n^2 的复杂度变成线性的

我们解题的时候一定要想一下最优解，不然可能让我们就算做出来了这道题可能也得不了高分