2022-08-19 21:59 东南大学 算法工程师 发布于江苏
关注
#微软笔试# #微软# #秋招# #笔试# #算法#
今日份（8-19）的微软笔试：
第一题：直接求解+二分优化。数据量N是10^5，数据大小M是10^9，从左往右直接求解，再使用二分优化一下，复杂度O(lg M)。当然，最大的问题在于无法证明这种做法是最优解，但是快就完事了！
第二题：贪心+堆优化。统计所有数出现的次数，对于任意两个数，当他们的数量都大于2、或者值都为1时，值更大的优先级更高；否则数量大于2的优先级更高。每次选择当前优先级最高的数，用于从两端向内组成回文，直至优先级最高的数无法再用于组成回文。
第三题：DFS。每次 DFS 返回一个 cost 和人数，当前点的 cost 、人数分别为由深层DFS返回的 cost 之和、人数之和，在当前非0的点返回前再对 cost 加上 ceil(当前人数/5)。
今日份（8-19）的微软笔试：
第一题：直接求解+二分优化。数据量N是10^5，数据大小M是10^9，从左往右直接求解，再使用二分优化一下，复杂度O(lg M)。当然，最大的问题在于无法证明这种做法是最优解，但是快就完事了！
第二题：贪心+堆优化。统计所有数出现的次数，对于任意两个数，当他们的数量都大于2、或者值都为1时，值更大的优先级更高；否则数量大于2的优先级更高。每次选择当前优先级最高的数，用于从两端向内组成回文，直至优先级最高的数无法再用于组成回文。
第三题：DFS。每次 DFS 返回一个 cost 和人数，当前点的 cost 、人数分别为由深层DFS返回的 cost 之和、人数之和，在当前非0的点返回前再对 cost 加上 ceil(当前人数/5)。
全部评论
lemonlemon777
美团_后端开发
第一题，如果不优化，应该是NlogN。
如果优化从左向右的判断过程：二分寻找大于当前最远可以达到的点，在W为1的时候这个步骤退化为O（N），其他时候的时间复杂度不会分析了orz。。。
第二题应该不需要用堆，因为就0-9十个数字，统计十个数字出现的频率，然后逐个数字遍历即可。贪心的把大的数字放在字符串两侧。时间复杂度是O（N）
求求了🙏
四川大学 golang
啥时候可以贴个代码了
paceccccc
中南大学 图像识别
最后一题没想出来😥前两题虽然测试用例都过了但是不知道会不会有一些边界条件没考虑到
新垣結衣男朋友
香港中文大学 Java
最后一题麻烦给个代码可以吗
Les1ie 楼主
楼主 东南大学 算法工程师
附上代码：https://www.nowcoder.com/discuss/1021679 
雷先生
中国科学院大学 C++
朋友可以麻烦贴一个题目咩，这周没做😂
牛客442288877号
重庆大学 自然语言处理
😂完蛋，我写的ceil（x/4）
offeraofferpls
云南大学 后端
借口问一下，微软的笔试只需要考一场就可以了吗？
相关推荐
查看20道真题和解析
点赞 评论 收藏
分享
投递旷视等公司10个岗位 > 点赞 评论 收藏
分享