文远知行C++一面

1、实习项目说一下,难点是什么,最终效果怎么样

2、LRU 了解吗,具体可以怎么实现,时间复杂度

3、select、poll、epoll 是什么,有什么不同

4、模板原理是什么,虚函数可以写成模板函数吗

  > 编译期间和运行期间角度

5、shared_ptr 线程安全问题,weak_ptr 作用

6、TCP 和 UDP 不同

7、算法题:变形背包问题,给定 n 个物品的重量 w_i, 价值 v_i,背包容量 m,其中 1 <= n <= 40, 0 <= w_i, v_i, m <= 10^15(寄)

由于背包容量高达10^15,因此不能用简单 dp 来思考

可以考虑从 n 的范围入手,直接枚举 n 的子集,最多 2^40 复杂的,还是太高

- 考虑分成两堆,每堆最多 20 个元素,复杂度为 2^20
- 枚举 20 个元素的子集问题,考虑用集合的思想,1 << 20
- 预处理第二个集合,按照重量排序,重量前缀和,维护最大的价值,这样在枚举第一个集合元素的时候就可以二分查找指定重量的最大价值

> 其他答的挺好,算法没弄出来,第二天直接挂

#24届软开秋招面试经验大赏##文远知行#
全部评论
这个背包问题没啥更好地思路呀
1 回复 分享
发布于 2023-10-07 17:55 北京
1 回复 分享
发布于 2023-09-22 21:12 江苏
(挖个坟)这题在竞赛见过,类似hdu5887的map维护超大背包,刷到这个帖的朋友没思路可以去看看
点赞 回复 分享
发布于 2024-03-15 17:03 广东
文远开始了?
点赞 回复 分享
发布于 2023-09-22 14:58 广东

相关推荐

03-04 01:37
算法工程师
bg:&nbsp;985本硕。现在主要研究视频生成,之前做过3d/4d、多模态(和推荐相关)。3个offer:1.&nbsp;字节广告算法,1-2,n*15+3w期权。优点:字节的广告算法行业内应该算top级别,团队leader人也非常好。缺点:和个人背景没有那么匹配,也没有那么感兴趣,2.&nbsp;卓驭科技(前大疆车载)多模态大模型(视频生成、vla等方向),(n+10k)*(12-17)。优点:薪资确实比字节高很多,方向也喜欢,个人觉得智驾和具身智能未来发展空间很大,哪怕未来智驾和具身未来不行,应该也可以跳槽到别的行业,毕竟做大模型的。缺点:强度应该比字节稍大,其他福利待遇比字节差一些,年终奖无保底(hr说绝大部分都能拿到4个月年终奖),公司在智驾行业不算第一梯队,网上信息也比较少,不清楚到底咋样,未来稳定性、业务发展、行业认可度(据hr说公司员工跳槽出去,行业认可度很高)等都不太清楚,但是看算法团队硕博比例很高,人才密度比较高,技术水平应该也还行。3.&nbsp;华为2012实验室ai多模态(软件特战队),15a,40-50w。hr说进去之后会根据个人意愿匹配到对应的项目组,但是看网上有人说这个很坑,进去之后随便分,看运气,都是做算子开发的。面试过程也几乎没怎么问ai算法相关的,感觉面试官根本不懂ai算法。暂时不考虑华为了。求帮选,或者给些建议和信息,感谢。
校招薪资来揭秘
点赞 评论 收藏
分享
评论
8
63
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务