2020-03-25 21:10 阿里巴巴_基础平台研发工程师

关注

2020.3.25微软笔试题回忆

做完果然自闭，发现牛客上好像还没有帖子。写出来希望大佬们分享一下思路。

第一题：

给一个无序数组，需要分成k个大小相同的子数组，求每个子数组最大最小元素的差值之和的最小值，子数组中元素不能重复

第二题：

给一个字符串，每次可以移除其中一个字符，或者移除一个回文子串，求全部移除所需最少次数

例如：14315.先移除3，再移除141，再移除5，得到最少次数3.

第三题：

给一个无向图，每条边初始权值为1。图中除普通节点外有4种节点。

第一种：走过这种节点后的两条边权值翻倍

第二种：走过这种节点后的两条边权值减半

第三种：走到这个节点就GG

第四种：跟第一种第二种类似，记不清了（因为没做这道题🙃🙃），望大佬补充。

求节点1到N的最短权值和路径

#微软暑期实习春招##微软##笔试题目#

全部评论

推荐最新楼层

木子十千

字节跳动_Data-商业化技术_算法工程师

第二题 https://github.com/liwan-cn/recruit-2020/tree/master/src/microsoft0403

送花回复

发布于 2020-03-25 21:37

牛客151369345号

Java

请问微软笔试只有一场吗，如果错过还会有机会吗

送花回复

发布于 2020-03-26 00:19

滴滴

校招火热招聘中

官网直投

Justin201902180106887

算法工程师

第一题一定数组中每个数都用么

送花回复

发布于 2020-03-26 03:59

禾羽木木木

测试开发

第二题：https://blog.csdn.net/abccc250110119/article/details/105143804 这个对吗😥

送花回复

发布于 2020-03-27 16:35

wwxy261

C++

mark，一样的题目，等解答

送花回复

发布于 2020-03-25 21:15

bzzbzzb

门头沟学院

第二三题都只过了两个testcase...不知道能不能有面试，我写的第二题用回溯法，第三题的话dfs吧

送花回复

发布于 2020-03-25 21:15

不会算法的精灵球

腾讯微保_计算机视觉工程师

第二题用正序和逆序的最大公共子序列可以过四个test case

送花回复

发布于 2020-03-25 21:21

MichelleGoGoGo

Java

第三题的第四种应该是要让权值是max(1, weight)吧

送花回复

发布于 2020-03-25 21:27

木子十千

字节跳动_Data-商业化技术_算法工程师

第一题个人理解的思路：{5, 10, 4, 8, 3, 6, 5, 10, 4, 8, 3, 6} 最大值10有2个，最小值3有2个 1. 所有的最大值和最小值必定在每个Team的最大值最小值中 2. 贪心策略如果最大值的个数+最小值的个数>= 分组数，在本例中为2+2 >3，那么必然有2+2-3=1个Team的最小值为3最大值为10，该Team 10-3= 7 3. 此时还剩下一个以3为最小值的Team, 需要从所有数中找到满足条件的最大值最小是多少，在本例子中[3, 4, 5,6]，寻找的方法就是把所有未选中的排序，从前往后插入不重复的数, 如果是多个以全局最小值为最小值的Team，就寻找多次 4. 此外还有一个以10为最大值的Team,要从所有数中找到满足条件的最小值最大是多少，在本例子中[5,6,8,10], 寻找的方法就是把所有未选中的排序，从后往前插入不重复的数； 5. 在本题中 7 + 3 + 5 = 15 6. 如果最大值的个数+最小值的个数< 分组数，也是按照相同的方法贪心，最后剩下的数的划分又是另一个同样的子问题了

送花回复

发布于 2020-03-25 21:52

刘嘟嘟呱

Java

SWE要过几道才能有面试啊，自闭了。

送花回复

发布于 2020-03-25 22:35

皮蛋烤柿粥

Java

第一题贪心，第二题dp（不过我O（N3）有个例子超时了），第三题没来得及看。。。

送花回复

发布于 2020-03-25 23:04