<
回复: 4
收起左侧

伯克利某HF挂经

本楼:   👍  0
0%
0%
0   👎
全局:   13
100%
0%
0

2024(4-6月) 码农类General 硕士 全职@voleon - 猎头 - 技术电面  | 🙁 Negative 😐 AverageFail | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
两轮一起面的,大概率是挂在了第一轮,面试大哥网掉了不知道多少次,我说一半发现没回应,来来回回重说有点搞心态了。这轮是常规的稀疏矩阵题,但是时间浪费太多最后没说完 🙁
第二轮有点意思,之前貌似没在面经里看到,有点类似于NNS[1],面试完有一阵子了细节上可能略有偏差,请酌情参考:每次添加一个新的点到地图上时,随机选取地图上已有的一个距离给定的target(点T)最近[2]的点,把这个点(点A)或者它的邻居[3](点B)设为T的邻居,选取标准是比较A和B对于T的欧式距离,选取欧式距离更短的那个点作为T的邻居。

[1]https://en.wiki
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式

[3]邻居也是个自定义的概念,地图上第一个点没有邻居(哪怕地图上产生第二个点之后也不会将其设为第一个点的邻居),其它的点的邻居根据描述的规则设定。

评分

参与人数 2大米 +6 收起 理由
清道神君 + 5 欢迎分享你知道的情况,会给更多大米奖励!
sam9909 + 1 赞一个

查看全部评分


上一篇:开店莫名其妙经
下一篇:現場元資料工程師
laobai2024 2024-6-2 14:13:22 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   117
83%
17%
24
所以第二个题目要用R tree来实现吗 还是其他空间划分算法?
回复

使用道具 举报

 楼主| m_0_m_0 2024-6-3 13:24:45 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   13
100%
0%
0
laobai2024 发表于 2024-6-1 23:13
所以第二个题目要用R tree来实现吗 还是其他空间划分算法?

我不确定对不对,仅供参考:每次添加一个点的时候把这个点折算成它所在的1 x 1方格里的一个特定点(比方说左下角的点,e.g. A(1.2, 1.3) -> B(1, 1)然后把新增的点A添加到B所映射到的一列点中用来方便之后随机选取邻居。我假设了所有点都会落在一个有限大的以原点为中心N x N (N reasonably small)的方格里,然后用类似刷题网 三菱霸 的方法更新每个1 x 1小方格内有多少个点。再用二分法寻找最小满足条件的大方块(换句话说就是找到一个k,使得以新增点所在方格为中心 (k - 2) x (k - 2) 的大方块内没有其他点但是 k x k 大方块内有其他点,然后在这些可能的k^2 - (k-2)^2 = 4*(k-1) 的方格里找一个点作为邻居,至于为什么是k - 2而不是 k - 1,因为上下左右都需要向外延展1)。我倒是没想过用R-tree,但是简单考虑了一下K-D tree,因为不能保证找到最近的点所以就没有继续朝这个方向优化了。
扫码关注一亩三分地求职移民公众号
更多干货内容等你发现
回复

使用道具 举报

laobai2024 2024-6-4 14:09:56 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   117
83%
17%
24
m_0_m_0 发表于 2024-6-2 22:24
我不确定对不对,仅供参考:每次添加一个点的时候把这个点折算成它所在的1 x 1方格里的一个特定点(比方 ...

感谢回复 稀疏矩阵直接https://leetcode.com/problems/sp ... ach-2-list-of-lists 这个解法就可以吗 还是要求CSR format https://leetcode.com/problems/sp ... roach-3-yale-format
回复

使用道具 举报

 楼主| m_0_m_0 2024-6-4 15:20:08 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   13
100%
0%
0
laobai2024 发表于 2024-6-3 23:09
感谢回复 稀疏矩阵直接https://leetcode.com/problems/sparse-matrix-multiplication/editorial/#approac ...

我用的比较接近于参考答案里面的方法2。面试官不允许你把所有原始数据存下来,所以需要想个办法存非零的数据然后再计算,Yale Format能讲清楚的话应该也行
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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