微软近期高频面试题分享 + 分析

最近来微软面试的小朋友通过概率实在太低了，代码老是写不对，我们组已经十连拒了，不得不感叹，现在出的面试题越来越难了，我决定还是上来地里透透题，说点最近我们组面试常考高频题和解析（毕竟岗位机会也不能都让三锅霸占了对不）。招人艰难，看微软机会的小伙伴，也欢迎LinkedIn勾搭：https://www.linkedin.com/in/andy-yongjian-deng-212977200/

注意打招呼的时候备注一下，方便识别友军，hhhh。

带娃有压力，尽量保持一周两更，大家海涵。

正题开始！

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

1.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 是字符串的平均长度。为字典树的空间开销。

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

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。期间仅可乘坐公交车。求出最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

本题是一个无向图的搜索问题，但是题意很容易把我们弄混，可能一开始以为要将站台作为图上的点，其实应该将车作为点，如果两辆车的路线之间存在公共站点，那么就视作这两个点之间存在连线；

因为需要绕弯，所以，同时用到了多个映射用于保存车和站台、站台和车、车和车之间的关系。

已经将问题转化为图的搜索问题了，那就很好做了，常规的做法就是将点与点的关系存在映射之中，建立邻接表，然后搜索映射。

蹲一个位置，谢谢楼主，顺便要保护好个人信息呀，微软关键词可以改一下, 大家都懂的

大佬好人一生平安
友情提示大佬保护好个人信息以免被有心之人利用

题目： 给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

大佬您好 组里还有sde1 的opening吗 最近刚过了面试在team match 求捞！

YankeeDoodle 发表于 2021-4-9 22:43
题目： 给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words + word ...

这题有点意思，分享一下我的思路：

把所有可能的回文串分成三种来源(words[i]'表示words[i]的反向)：
1. words[i] + words[i]'，最朴素的一种，比如'abc'+'cba'
2. words[i][:k] + words[i][k:] + words[i][:k]'，第一个词的后半部分是自回文的，比如'abcded'+'cba'
3. words[i][k:]' + words[i][:k] + words[i][k:]，第二个词的前半部分是子回文的，比如'abc'+'dedcba'

然后分别找这三种情况：
1.很简单，简单的用hash就是一个近似于O(n)的问题；也可以用字典树获得更稳定的效率。
2.预处理找到所有words后半部分的自回文，应该是一个O(nm)的问题；之后就是一个和问题1一样的问题。
3.和问题2类似。

不知道大家有没有更简单的方法？

p.s. 给lz的linkedin发了消息！现在在狗家实习... 明年毕业求带！

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

好人一生平安，虽然我最近简历被微软拒了，早知道叫lz帮忙内推了。我发了linkedin请求，求通过啊

现在是国人代码写不过三锅吗？

插眼蹲！谢谢楼主！

谢谢楼主！谢谢楼主！