微软面试真题+面试官改编leetcode思路

微软的面试官现身来说一下,现在微软带一个开发团队,作了三四年的面试官,早已经知道现在的小朋友喜欢刷题,自然不会傻到原原本本的去考leetcode的原题。所以最好不要通过死记硬背,想要碰到原题来制霸面试。

划重点:编程面试,只有高频知识点,没有所谓的高频题。

众所周知,微软以及诸多其他大厂的面试算法题主要是以leetcode为素材的改编,我现在分享一些面试真题以及我自己和同事作为面试官的改编思路,希望可以帮到还在苦战刷题的同学。我会将大部分的leetcode原题过一遍,再附上面试真题的改写思路,尽量讲得傻瓜。由于篇幅限制,在这里我只举几个小栗子,更多面试真题后续会慢慢更新。

我尽量保持每周两更+回复评论,看后续的反馈情况决定是否改变更新频率以及增减分享的内容,每条评论回复都会看,也可以加微信交流:longswordMAN,注明1o24的id即可。

1 Like

废话不多说,正题开始:

我们先来看leetcode上第1号问题:Two Sum:

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

简单题,考的是哈希表,暴力两重循环必挂。现在网上的帖子都喜欢和你说leetcode 第XX题 是高频题,其实都是懒人思维,属于新手的思维误区。真正高频的是一些特定的知识点,如果按这种“原题照搬”思维,题目稍微做一些变招,大概率是要马失前蹄。

这里的真正的高频考点是数据结构哈希表,划重点:哈希表的应用面试 必考 ,一定会以某种形式在题目的某一部出现,以后还会讲到哈希表和二叉树,哈希表和二位数组等其他数据结构结合的变招。

面试官改编思路:

  1. 不同的运算规则,可以是乘除法,可以发明一个运算规则。
    真题:
    给定一个整数数组和一个目标值,找出数组中乘积为目标值的两个数。

示例:

给定 nums = [2, 7, 11, 15], target = 14

因为 nums[0] * nums[1] = 2 * 7 = 14
所以返回 [0, 1]

其实换汤不换药,乘除法注意考虑边界情况即可(除以零),如果面试官自己发明的运算法:比如运算符:bla 的规则是: X ‘bla’ Y = X*Y - X -Y。 同样的,查表规则改一下而已,换汤不换药,注意考虑边界情况 。

期待这多这样的改编

  1. 换一个数据结构,看面试者是否能够利用规则,在时间复杂度上进一步优化。真题:
    给定一个有序整数数组和一个目标值,找出数组中和为目标值的两个数。

示例:

给定 nums = [2, 7, 11, 15], target = 13

因为 nums[0] + nums[2] = 13
所以返回 [0, 2]

当然有序数组也可以改成二叉树等其他数据结构,或者是一些具备某特性的数据结构。有序数组的话,注意用二分查找,可以把时间复杂度降到O(logn)

  1. 变成多数之和,比如 3 sum。这样的改写容易真题:
    给定一个有序整数数组和一个目标值,找出数组和为目标值的三个数。

示例:

给定 nums = [2, 7, 11, 15], target = 20

因为 nums[0] + nums[1] + nums[2] = 2 + 7 + 11 = 20
所以返回 [0, 1, 2]

思路类似,查两次表,但注意排除第一个数,比如 2+2+2 这种一个数重复用多次的情况。

当然这都是容易的,如果三个数,再结合第1条变化,查表次数仍然是两次,但不要被复杂的运算搞晕,然后注意边界条件即可。