微软Hiring event onsite面经

微软面经提供给大家，onsite一共四轮，前三轮都是原题medium的难度，就不赘述了。楼主个人跪在了第四题。题目是这样的：给定

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

慢了，要求线性时间解决问题。最后给出的提示是转换成图的问题，然后看图分成几部分，祝大家好运

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

jontian 发表于 2017-9-8 00:56
感觉不能直接转换成 “有相同label的两个element之间有edge”
不然n个node之间就有n^2个edges了，
可以这 ...

层主能稍微解释下你的做法吗？感觉建图就N^2的复杂度了

shuofeng11 发表于 2017-10-2 09:01
层主能稍微解释下你的做法吗？感觉建图就N^2的复杂度了

就是On吧。对于A只需要1->2, 2->3就可以，这里我们只检查连通性， 没必要每个edge都连上。

转换成图，有相同label的两个element之间有edge，然后dfs分别打印出每个component

我感觉这题看起来就像hashmap和union-find，不容易联想到graph，虽然graph是最优解。。。

感觉不能直接转换成 “有相同label的两个element之间有edge”
不然n个node之间就有n^2个edges了，
可以这样
比如A:1,2,3 就1->2 1->3

qsder 发表于 2017-10-2 09:18
就是On吧。对于A只需要1->2, 2->3就可以，这里我们只检查连通性， 没必要每个edge都连上。

能稍微解释下具体步骤吗？没太明白

楼主是哪个组的hiring event啊？

楼主是哪个组的hiring event这么变态

群主你面后多久给拒？