<
查看: 11861|回复: 54
收起左侧

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

    |只看干货
本楼: 👍   100% (48)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

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

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

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

正题开始!

评分

参与人数 86大米 +129 收起 理由
ylian0613 + 2 给你点个赞!
v1rar1v + 1 给你点个赞!
德彪西 + 1 赞一个
georgey + 3 很有用的信息!
resco + 2 给你点个赞!
pengxiening + 1 赞一个
zxjin + 1 很有用的信息!
莫言纪季 + 1 给你点个赞!

查看全部评分


上一篇:看到几道面经题找不到leetcode上相关的
下一篇:求问面过狗家的大佬,我刷题一年还是菜如何把握最后一次狗家面试机会
 楼主| YankeeDoodle 2021-4-11 10:52:31 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
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 的前缀的翻转。

评分

参与人数 2大米 +31 收起 理由
admin + 30 很有用的信息!
ymkacscc20 + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| YankeeDoodle 2021-4-12 10:57:11 | 显示全部楼层
本楼: 👍   100% (5)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
给你一个数组 routes ,表示一系列公交线路,其中每个 routes[i] 表示一条公交线路,第 i 辆公交车将会在上面循环行驶。
例如,路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发(初始时不在公交车上),要前往 target 车站。期间仅可乘坐公交车。求出最少乘坐的公交车数量 。如果不可能到达终点车站,返回 -1 。

评分

参与人数 1大米 +1 收起 理由
Roory + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| YankeeDoodle 2021-4-13 10:23:07 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
本题是一个无向图的搜索问题,但是题意很容易把我们弄混,可能一开始以为要将站台作为图上的点,其实应该将车作为点,如果两辆车的路线之间存在公共站点,那么就视作这两个点之间存在连线;

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

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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x

评分

参与人数 5大米 +25 收起 理由
AlexDWang + 2 给你点个赞!
川川唔 + 1 赞一个
10969z + 1 赞一个
csqcloud + 1 赞一个!
admin + 20 很有用的信息!

查看全部评分

回复

使用道具 举报

gabrielleL 2021-4-9 23:29:40 | 显示全部楼层
本楼: 👍   100% (7)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
蹲一个位置,谢谢楼主,顺便要保护好个人信息呀,微软关键词可以改一下, 大家都懂的
回复

使用道具 举报

concessions 2021-4-14 07:38:32 | 显示全部楼层
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   98% (2349)
 
 
1% (35)    👎
大佬好人一生平安
友情提示大佬保护好个人信息以免被有心之人利用
回复

使用道具 举报

 楼主| YankeeDoodle 2021-4-9 22:43:47 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
题目: 给定一组 互不相同 的单词, 找出所有 不同 的索引对 (i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。

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

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
大佬您好 组里还有sde1 的opening吗 最近刚过了面试在team match 求捞!
回复

使用道具 举报

lyglst 2021-4-10 02:27:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
YankeeDoodle 发表于 2021-4-9 22:43
题目: 给定一组 互不相同 的单词, 找出所有 不同 的索引对 (i, j),使得列表中的两个单词, words + word ...

这题有点意思,分享一下我的思路:

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

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

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

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

评分

参与人数 1大米 +10 收起 理由
admin + 10 给你点个赞!

查看全部评分

回复

使用道具 举报

 楼主| YankeeDoodle 2021-4-10 10:27:22 | 显示全部楼层
本楼: 👍   66% (2)
 
 
33% (1)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
题目分析
如果字符串 S1 + S2 能构成一个回文串,把 S1 分成 S1_1 和 S1_2 两部分,可以有以下以下两种拼接情况:
①.S2 拼接在前,并且 S1_1 是回文串、 S1_2 是 S2 的逆序;
②.S2 拼接在后,并且 S1_2 是回文串、 S1_1 是 S2 的逆序;
回复

使用道具 举报

fish444555 2021-4-10 12:34:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (81)
 
 
2% (2)    👎
好人一生平安,虽然我最近简历被微软拒了,早知道叫lz帮忙内推了。我发了linkedin请求,求通过啊
回复

使用道具 举报

mchzh 2021-4-10 12:37:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (500)
 
 
2% (14)    👎
现在是国人代码写不过三锅吗?
回复

使用道具 举报

亦如 2021-4-10 14:08:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   90% (20)
 
 
9% (2)    👎
插眼蹲!谢谢楼主!
回复

使用道具 举报

wengjn 2021-4-10 14:41:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (405)
 
 
5% (22)    👎
谢谢楼主!谢谢楼主!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

X 关闭
>
快速回复 返回顶部 返回列表