八月底骨骼昂赛

八月末Sunnyvale 昂赛，已过HC，首先谢谢地里很多无私分享的小伙伴。 发面经回馈地里，希望接下来面试的小伙伴都能顺利~
如果觉得有用的话希望可以给我加一点大米。

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

游客，您好！
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 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

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

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

关于第一题：
如果只是问最多可以去掉多少个点，那么就是地里经常出现的一道面经．最方便的算法就是用union find. 所有ｘ坐标相同的点可以归并，所有ｙ坐标轴相同的可以归并，两个并集只要有一个节点相交的话又可以归并，总之用并查集就是秒杀．最终并查集里面有几个集，就是最少能留下多少个点，相应就知道最多可以去掉多少点．
那么这道变形我们该怎么做呢？基本思路也是差不多的，只要能按照上述定义归并到一起的点都是连通的．我们每次删除，只要删除一个连通图最边缘的点，就不影响剩下的图的节点的连通性．怎么判定是边缘的点呢？只要它的度为１就是了（注意，这里是无向图，不分入度和出度）．所以很明显了，这题就是用BFS做拓扑排序．
另外，大家注意到，我们的首要任务其实就是要构造出若干张连通图，这张连通图的edge不要太多，只要恰好能够使该连通的节点（如上定义）连通起来就够了．怎么做呢？同一个Ｘ坐标的点，将第一个点和其他的点连通起来；同一个Ｙ坐标的点，将第一个点和其他的点连通起来．这样构建的连通图，每个节点的度最少，而且还保证它们都连通．
具体的代码如下，如果有任何bug请反馈给我．如果觉得好，欢迎给个好评加点米．谢谢

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

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

补充内容 (2018-9-30 03:22):
感谢网友“蝶自西来”的提醒，这段代码有小bug，大家就不要看了。请看57楼我的新帖。

请问楼主第四轮怎么做的？用DFS ？

没找到回复楼上的地方。第四题是用DFS 做的

求timeline

第一题求最后点的数目还是去除顺序？

pandami 发表于 2018-9-16 00:20
第一题求最后点的数目还是去除顺序？

是顺序，字数字数

xoyang 发表于 2018-9-15 13:48
求timeline

昂赛后过了一周开始team match, 选好组后第二天过了hc,一共两周的时间

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

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