2023-09-21 23:18 北京邮电大学 计算机类
关注
文远知行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届软开秋招面试经验大赏##文远知行#
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届软开秋招面试经验大赏##文远知行#
全部评论
爱米信米等米求米给个offer
门头沟学院 电子信息类
送花
回复
分享
看不上那空间大白菜
C++
这个背包问题没啥更好地思路呀
送花
回复
分享
秋招专场
校招火热招聘中
官网直投
只因不会Java
中共广东省委党校 计算机类
文远开始了？
送花
回复
分享
一口三明治
卓驭科技_决策规划控制部_决策规划算法工程师(实习员工)
佬挂的时候有感谢信吗
送花
回复
分享
OfferLimitedExceeded
文远知行_软件开发(实习员工)
（挖个坟）这题在竞赛见过，类似hdu5887的map维护超大背包，刷到这个帖的朋友没思路可以去看看
送花
回复
分享
相关推荐
查看1道真题和解析
投递文远知行等公司6个岗位 > 点赞 评论 收藏
转发
阿里巴巴二面95人在聊 点赞 评论 收藏
转发
点赞 评论 收藏
转发