🐶onsite遇到一个不会做的题求解

首先吐个槽，因为电面表现差了点，所以虽然我5yrs+工作经验了但是面的还是L3，略心塞
三轮抠腚一轮bq，考官都是典型白人宅男，不太爱说话的亚子（好事儿就是感觉他们说

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

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

w up的考生，希望他能给我个五星好评🙀

还请大家帮我想想第一题怎么做合适啊，面完后网上搜了老半天也没见着更好的答案

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

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

Ｇ家就是：自己刷了三百題後 遇到了非ＬＣ的題
但是朋友面的時候，全是ＬＣ題，輕鬆拿offer

kazumi 发表于 2021-5-27 01:06
text justification 哪有2个follow up?

follow up在利口上木有，就面试官自个加了一些奇怪的条件（比如：单词长度比行宽要长的时候用小横杠把单词掰开）。都不麻烦，能把那题在lc上写明白的我觉得都不至于答不出来

1是不是可以通过分块来优化？

第一题 union find?

TTTCCC 发表于 2021-5-26 22:39
1是不是可以通过分块来优化？

我考虑过，分成各种方块的话可以优化一些但好像还是O(n^2)，分成圆的话想不出来怎么整。。。

huxinran 发表于 2021-5-26 22:57
第一题 union find?

能讲一下具体的算法嘛？union find的题我也做过一些，但是想不出来怎么应用到这里

第一题分块吧， 为了简化题意，我们先假设题目用的是曼哈顿距离，假设距离最小距离为k。

那么我们用边长为k的小网格铺在平面上，每个小方块内部只能有一个点，然后我们只需要比较两个相邻的小网格里的点的距离是不是<k
然后我们可以推广到欧几里得距离，把小网格边长换成 k*根号2。
时间复杂度是O(n)的。

但是如何保证删尽可能少的点使得输出合法可能又是另外一回事了。

第一题，先把所有点移动到第一象限（找出最小x 和y的值）O(n)
按移动后点对原点的距离排序 O(nlogn)
greedy O(n)
还原所有点的值 O(n)

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

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