微软STCA苏州暑期实习一面

微软一面
1. 自我介绍,非科班转行,只有实验室项目嘤嘤嘤。
2. 做题:有n个白色节点和m个黑色节点的图,每个白色节点都能找到离他最近的黑色节点,已知所有的白色节点,求所有白色节点到他最近的那个黑色节点的路径和。
(哭了,图论根本没怎么学过,题目都听不懂。用BFS写了个O(n2)的,然后优化跟面试官尬聊了半小时。求评论区大佬给个题解😂,同门说可能是最小生成树,俺也不懂,晕)
3. 求n个node在n叉树中的最近公共祖先。
(聊了还有时间,面试官说再来个简单点的,哭了。DFS写了一个题解,然后面试官觉得不够好,优化没时间,就提了一些可以改进的方向)
4. 面试官建议:写得时候不要太随意,要先把输入输出定义好,struct Node定义好。
总结:微软面试官人挺友好的,循循善诱带你解题,可惜本渣渣太菜了。
听说牛客许愿很灵,许愿微软一面能过吧。。。

#微软暑期实习##微软##面试题目##实习#
全部评论
快过 !!!等着老哥分享工作经历
点赞 回复 分享
发布于 2022-02-28 21:44
算法题一感觉没表述清楚,既然你说暴力BFS解那我就当是无权图了。 把白色节点按照是否直接和黑色节点相邻分成两类。如果相邻,那么距离是1。如果不相邻,那么这个节点必须经过别的白色节点才可以到达黑色节点。相当于在所有白色节点构成的子图中,求这个节点到最近的与黑色节点相邻的白色节点的距离再加一。 那么初始化把所有和黑色节点相邻的白色节点距离设为1,跑一遍BFS求其他白色节点的最短路就完事了。
点赞 回复 分享
发布于 2022-02-28 22:33
n 叉树的公共祖先,可以先设置一个数组,找到根节点到这个叶子结点的路径,然后使用类似:两个链表的相交结点的方式求解吗?总的时间复杂度 : O(n), 空间复杂度 : O(n)
点赞 回复 分享
发布于 2022-03-01 15:23
老哥太强了
点赞 回复 分享
发布于 2022-03-02 20:41
第一题多源bfs?
点赞 回复 分享
发布于 2023-04-22 02:53 浙江

相关推荐

3 17 评论
分享
牛客网
牛客企业服务