苏州微软 sde 实习oa

国内微软的笔试题挺难的。。

1.5h做3道coding题，感觉时间很不够用，而且提供的ide也不是很顺滑，当然主要还是本人太菜了。大概说一下题目和思路吧：

1. 给定一个数组A及其大小n，将其划分为不同的大小为m的子数组（即一共n/m个子数组），每个数组中的元素各不相同，且每个数组也不能一样。要求每个子数组的极差最小，且求出最小极差之和。每个子数组最少要有两个元素，不符合要求的话返回-1.
eg：A={3，3，4，4，5，5，6，6，8，8，10，10}，n=12,m=4.
output=15. explanation：sub1={3，4，5，6}，max-min=6-3=3; sub2={3, 4, 8, 10}, max-min=10-3=7; sub3={5, 6, 8, 10}, max=10-5=5; total=3+7+5=15.
思路：听说用贪心，不过我还没有想出来。

2.N个瓶子都有编号，每次能射击1个或多个瓶子，如果是回文的就能一次性击倒。最少几次能全击倒？
eg：input={1，3，4，1，5}，n=5.
output=3. explanation: 先击中3，击倒次数count=1；剩余{1，4，1，5}， 其中{1，4，1}构成回文序列可以一次击倒，所以击中{1，4，1}，累计count=1+1=2；最后击中5， 累计count=2+1=3.
思路：用dp。参考lc1246。

3.给一个无向图，每条边初始权值为1。图中除普通节点外有4种节点。    第一种nitro：走过这种节点后的边权值翻倍    第二种sand：走过这种节点后的边权值减半    第三种cop：走到这个节点就GG    第四种crash：走过这种节点后边权值+1.   普通节点状态记为“None”。求从节点0到N-1的最短权值和路径。（这个题目有点记不清了，大概是这样，欢迎指正。）
eg：input1={“None”，“Cop”，“None”，“None”，“None”}，input2={0，1，2，3，4}，input3={{0，1}，{1，2}，{0，2}，{2，3}，{3，4}}
output={0，2，3，4}，total=3. explanation：节点1状态为cop，说明不能从节点1经过，因此可选路径为0->2->3->4.因为其他节点都是普通节点，所以路径总权重为3.
思路：用dfs或者bfs。

起床->做题->自闭->点烟->登录官网withdraw application

感觉这题目就是劝退的，而且早上4点爬起来做题真是醉了

xiana406 发表于 2020-3-27 12:55
第三题有更多例子吗？没看太懂。例子里面好像没涉及到nitro,sand，她们是怎么计算的。鞋鞋。另外大神有做第 ...

nitro 之后两段路程速度加倍 sand之后两个城市速度减半 举个例子 比如一条路径是
A-B(nitro)-C(nitro)-D(sand)-E
A-B耗时标准时间1小时 B之后2段速度加倍 所以B-C 耗时0.5小时 C-D耗时0.25小时 因为B的加速还没结束 C之后两个城市速度又要翻倍 D-E耗时一小时。 这时候B的加速结束了 C的加速还在，和D的减速抵消了。
总计耗时2.75小时 起始速度为v结束速度为0.5v

真的有点难

就nm难的离谱

也不知道有没有人能全做出来……

一题没做出来

做出来第二道，但有两三个case超时...

第三题有更多例子吗？没看太懂。例子里面好像没涉及到nitro,sand，她们是怎么计算的。鞋鞋。另外大神有做第一题的吗？没看懂。

请问楼主是海投还是找人内推的啊。国内微软在哪投递简历比较靠谱