找回密码
 立即注册
搜索
楼主: 整活骑士

[职场] 开贴记录一下春招求职过程(C++后端)

[复制链接]
头像被屏蔽
     
发表于 2022-3-16 18:35 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 15:43 来自手机 | 显示全部楼层
3.17更新
今天面b站和oppo
oppo好像又是不匹配 人家做coloros的
b站 上来两道题:
二维坐标系很多点,找距离最近的两个点
怎么用尽量少的正方形盖住所有点

一点思路都没有,凉凉
感觉智商被考官鄙视了
回复

使用道具 举报

     
发表于 2022-3-17 16:08 来自手机 | 显示全部楼层
引用第81楼整活骑士于2022-03-17 15:43发表的  :
3.17更新今天面b站和oppooppo好像又是不匹配 人家做coloros的b站 上来两道题:二维......

@整活骑士
不是遍历所有点比较x差值与y差值最小的两个点吗
画图就出来了

----发送自 samsung SM-N9600,Android 10
回复

使用道具 举报

     
发表于 2022-3-17 16:10 | 显示全部楼层
chachi 发表于 2022-3-17 16:08
@整活骑士
不是遍历所有点比较x差值与y差值最小的两个点吗
画图就出来了

没有这么简单吧,这题作为面试题蛮难的
回复

使用道具 举报

头像被屏蔽
     
发表于 2022-3-17 16:10 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

     
发表于 2022-3-17 16:11 | 显示全部楼层
整活骑士 发表于 2022-3-17 15:43
3.17更新
今天面b站和oppo
oppo好像又是不匹配 人家做coloros的

第一题已经比较难了,分治里面算难题了
第二题没看懂,你是指边长为1的正方形嘛?不然足够大的正方形一个总是够(
如果指边长为1的正方形那么是否边必须和坐标轴平行?这题的描述怎么不清不楚的(
回复

使用道具 举报

     
发表于 2022-3-17 16:12 | 显示全部楼层
整活骑士 发表于 2022-3-17 15:43
3.17更新
今天面b站和oppo
oppo好像又是不匹配 人家做coloros的

算法导论-33章计算几何学. 寻找最近点对

做不出来很正常.
回复

使用道具 举报

     
发表于 2022-3-17 16:13 来自手机 | 显示全部楼层
引用第83楼ch_Ange于2022-03-17 16:10发表的  :
引用:chachi 发表于 2022-3-17 16:08@整活骑士不是遍历所有点比较x差值与y差值......

@ch_Ange
怎么不是呢
最近的两个点就是x与x1差值为0,y与y1差值为0
遍历找xy差值,取绝对值并相加,取最小值的为最近

----发送自 samsung SM-N9600,Android 10
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 16:17 来自手机 | 显示全部楼层
ch_Ange 发表于 2022-3-17 16:11
第一题已经比较难了,分治里面算难题了
第二题没看懂,你是指边长为1的正方形嘛?不然足够大的正方形一个 ...

面试官实际上只说是一些便利贴,大小可能不重要。然后还说这是个np问题 找出一种策略即可
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 16:18 来自手机 | 显示全部楼层
chachi 发表于 2022-3-17 16:13
@ch_Ange
怎么不是呢
最近的两个点就是x与x1差值为0,y与y1差值为0

这样遍历的复杂度是on^2,面试官肯定要求nlogn的,但是我想不出。他只说试试分治
回复

使用道具 举报

     
发表于 2022-3-17 16:18 | 显示全部楼层
chachi 发表于 2022-3-17 16:13
@ch_Ange
怎么不是呢
最近的两个点就是x与x1差值为0,y与y1差值为0

你不会以为折线距离最近一定导出欧式距离最近吧……
而且这题面试官想看的解要比N^2时间复杂度要优的(
回复

使用道具 举报

     
发表于 2022-3-17 16:19 来自手机 | 显示全部楼层
第二题不是取最远距离然后做正方形对角线吗,难道我理解错了?

----发送自 samsung SM-N9600,Android 10
回复

使用道具 举报

     
发表于 2022-3-17 16:21 来自手机 | 显示全部楼层
面试官说了要复杂度要求吗,你想太多了

----发送自 samsung SM-N9600,Android 10
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 16:22 来自手机 | 显示全部楼层
chachi 发表于 2022-3-17 16:21
面试官说了要复杂度要求吗,你想太多了

----发送自 samsung SM-N9600,Android 10

我想不出来,他提示我分治。用分治复杂度不可能是n^2啊
回复

使用道具 举报

     
发表于 2022-3-17 16:24 | 显示全部楼层
chachi 发表于 2022-3-17 16:13
@ch_Ange
怎么不是呢
最近的两个点就是x与x1差值为0,y与y1差值为0

几何距离吧
dis=sqrt(x^2+y^2)
回复

使用道具 举报

     
发表于 2022-3-17 16:24 | 显示全部楼层
整活骑士 发表于 2022-3-17 16:17
面试官实际上只说是一些便利贴,大小可能不重要。然后还说这是个np问题 找出一种策略即可 ...

什么鬼,大小不重要的话一个足够大的正方形不是铁定覆盖所有点,题目又只要求个数,你确定没听错题……?
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 16:26 来自手机 | 显示全部楼层
ch_Ange 发表于 2022-3-17 16:24
什么鬼,大小不重要的话一个足够大的正方形不是铁定覆盖所有点,题目又只要求个数,你确定没听错题……? ...

他也没说大小啊,点之间的距离都是可变的,何况是便利贴呢,等比放大收缩就是了。他要的是一个策略。肯定不能说一个无限大的便利贴嘛
回复

使用道具 举报

     
发表于 2022-3-17 16:28 来自手机 | 显示全部楼层
引用第93楼整活骑士于2022-03-17 16:22发表的  :
引用:chachi 发表于 2022-3-17 16:21面试官说了要复杂度要求吗,你想太多了---......

@整活骑士
都提示用分治你就顺着说可以画出小区域分割。。。
面试啊
难道要你手写代码?

----发送自 samsung SM-N9600,Android 10
回复

使用道具 举报

     
发表于 2022-3-17 16:28 | 显示全部楼层
整活骑士 发表于 2022-3-17 16:26
他也没说大小啊,点之间的距离都是可变的,何况是便利贴呢,等比放大收缩就是了。他要的是一个策略。肯定 ...

最终的正方形肯定是2个点在边上的
枚举2个点,可以拿到4个正方形,每个正方形算一下覆盖了哪些点作为一个集合
然后进行搜索就行了
回复

使用道具 举报

     
发表于 2022-3-17 16:28 来自手机 | 显示全部楼层
引用第94楼yakumorin于2022-03-17 16:24发表的  :
引用:chachi 发表于 2022-3-17 16:13@ch_Ange怎么不是呢最近的两个点就是......

@yakumorin
对的,手机打字没想那么多

----发送自 samsung SM-N9600,Android 10
回复

使用道具 举报

发表于 2022-3-17 16:30 | 显示全部楼层
那就是大小是变量呗,可以试试贪心,用最边缘的点做顶点的正方形覆盖最多的点,然后下一个最边缘的点(
回复

使用道具 举报

     
发表于 2022-3-17 16:30 | 显示全部楼层
整活骑士 发表于 2022-3-17 16:26
他也没说大小啊,点之间的距离都是可变的,何况是便利贴呢,等比放大收缩就是了。他要的是一个策略。肯定 ...

能不能形式化一点叙述这个题?这个叙述真的不知所云。
比如:给定N个点,找出一个面积最小的正方形覆盖所有点
或者:给定N个点,用若干个正方形覆盖所有点使得这些正方形的总面积最小
或者:给定N个点,用最少个数的边长为1的正方形覆盖所有点

“怎么用尽量少的正方形盖住所有点”这种叙述我只能说“来个足够大的,一个就够”(
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 16:30 来自手机 | 显示全部楼层
chachi 发表于 2022-3-17 16:28
@整活骑士
都提示用分治你就顺着说可以画出小区域分割。。。
面试啊

我看了答案
如果分别求两个区间的距离最近再合并。没法保证两个区间的最小就是合起来最小,因为边界上可能存在着距离比内部更近的点对。而在二维空间,想找到两个区间里面的点对在另一个区间的最小值,复杂度还是on^2啊
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 16:31 来自手机 | 显示全部楼层
ch_Ange 发表于 2022-3-17 16:30
能不能形式化一点叙述这个题?这个叙述真的不知所云。
比如:给定N个点,找出一个面积最小的正方形覆盖所 ...

就是最后一种
回复

使用道具 举报

     
发表于 2022-3-17 16:31 | 显示全部楼层
整活骑士 发表于 2022-3-17 16:30
我看了答案
如果分别求两个区间的距离最近再合并。没法保证两个区间的最小就是合起来最小,因为边界上可 ...

边界最多8个点
所以还是O(nlogn)
这题很经典可以去网上搜搜
回复

使用道具 举报

     
 楼主| 发表于 2022-3-17 16:35 来自手机 | 显示全部楼层
yakumorin 发表于 2022-3-17 16:31
边界最多8个点
所以还是O(nlogn)
这题很经典可以去网上搜搜

看到别人写的文章了确实想不到
回复

使用道具 举报

     
发表于 2022-3-17 16:36 | 显示全部楼层
整活骑士 发表于 2022-3-17 16:35
看到别人写的文章了确实想不到

这种2维空间的问题直接背诵K-D tree得了, 90%的题都能做.
回复

使用道具 举报

     
 楼主| 发表于 2022-3-18 22:40 | 显示全部楼层
本帖最后由 整活骑士 于 2022-3-18 22:45 编辑

3.18日更新
B站,昨天以为挂了,今天打电话来要再面试一下,什么时间有空。结果我说下周二行不行。。。然后回头就真的挂了

快手,小哥人很好,但是问的问题直接给我橄榄。这算是我面试以来第一个C++主力的面试官,问题还是蛮有意思的vector map的线程安全怎么实现
如何把右值转为左值(我还第一次听说还能转)
写一个基类 如何实现知道它有多少派生类
算法:逆序对的数量

美团二面,
估计是leader,不问八股,上来一道topk,我用小顶堆来写,但是写的太慢了,面试官就说你说思路吧。然后问我一堆场景题,什么几十亿数据,白天给用户查询晚上更新,怎么设计。。。我设计个锤子。还有什么你带一个团队如果有人进度跟不上怎么办。。。
总之这些全都凉凉了
目前还是0 offer



回复

使用道具 举报

     
 楼主| 发表于 2022-3-21 18:13 来自手机 | 显示全部楼层
3.19日更新
虾皮凉凉,要求on的算法没写出来,只写了个nlogn
字节三面居然通过了,约了hr面
求求了给我发个offer吧。。。这几天太难受了,焦虑的睡不着觉
回复

使用道具 举报

     
发表于 2022-3-21 18:14 | 显示全部楼层
来投tplink吧
连我这样的都能进二面
拿个offer心里有底,之后还能用来a别家的薪资
回复

使用道具 举报

     
 楼主| 发表于 2022-3-21 18:15 来自手机 | 显示全部楼层
wyptaotao 发表于 2022-3-21 18:14
来投tplink吧
连我这样的都能进二面
拿个offer心里有底,之后还能用来a别家的薪资 ...

tp一面挂
回复

使用道具 举报

     
发表于 2022-3-21 18:18 | 显示全部楼层
回复

使用道具 举报

头像被屏蔽
     
发表于 2022-3-21 18:20 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

     
发表于 2022-3-22 06:17 来自手机 | 显示全部楼层
Sunyalche 发表于 2022-3-1 21:23
一般10万行怎么说也太夸张了吧...

十万行有点夸张,不过我之前统计过,一年1万行一般还是有的,毕业的时候4万行比较正常
回复

使用道具 举报

     
发表于 2022-3-22 07:32 | 显示全部楼层
本帖最后由 takooctopus 于 2022-3-22 07:33 编辑

线程安全要分治,一般来说是用hash做桶,还有加锁嘛。右值转左值一般来说不用forward就自己坍缩到左值了吧,基类的话,添加static引用计数?
回复

使用道具 举报

     
发表于 2022-3-22 07:52 来自手机 | 显示全部楼层
本帖最后由 星空天神 于 2022-3-22 09:19 编辑
整活骑士 发表于 2022-3-18 22:40
3.18日更新
B站,昨天以为挂了,今天打电话来要再面试一下,什么时间有空。结果我说下周二行不行。。。然后 ...

左值转右值用std::move 右值转左值直接赋值不就行了。auto&& a = B 更新 他可能想问你 static_cast<T&>
线程安全一般用锁 不过他可能想问你当容器发生改变时对已经拿到的迭代器和引用的有效性




—— 来自 OnePlus LE2120, Android 12上的 S1Next-鹅版 v2.5.2-play
回复

使用道具 举报

     
发表于 2022-3-22 11:58 | 显示全部楼层
写一个基类 如何实现知道它有多少派生类
这个题目太神必了,正常人应该会理解为“它有多少种派生类”。那我只能说如果不引入额外的编码,只通过继承应该是做不到这一点的,不懂你的面试官都在想些什么
回复

使用道具 举报

     
 楼主| 发表于 2022-3-22 12:34 来自手机 | 显示全部楼层
ch_Ange 发表于 2022-3-22 11:58
写一个基类 如何实现知道它有多少派生类
这个题目太神必了,正常人应该会理解为“它有多少种派生类”。那我 ...

是多少个还是多少种我忘记了
意思是定义一个基类 经过一段黑盒代码 之后要知道多少种/个派生类
提示static变量
但我还是不会
回复

使用道具 举报

     
发表于 2022-3-22 12:37 来自手机 | 显示全部楼层
整活骑士 发表于 2022-3-21 18:13
3.19日更新
虾皮凉凉,要求on的算法没写出来,只写了个nlogn
字节三面居然通过了,约了hr面

hr面不就稳了,估计只有阿里hr会挂人吧。。。
回复

使用道具 举报

     
发表于 2022-3-22 13:34 来自手机 | 显示全部楼层
字节hr面基本稳了吧。

— from realme RMX3366, Android 12 of S1 Next Goose v2.4.4.1
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|上海互联网违法和不良信息举报中心|网上有害信息举报专区|962110 反电信诈骗|举报电话 021-62035905|Stage1st ( 沪ICP备13020230号-1|沪公网安备 31010702007642号 )

GMT+8, 2025-2-17 21:05 , Processed in 0.221413 second(s), 4 queries , Gzip On, Redis On.

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表