2023-09-21 23:18 北京邮电大学 C++
关注
文远知行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届软开秋招面试经验大赏##文远知行#
全部评论
看不上那空间大白菜
北京邮电大学 C++
这个背包问题没啥更好地思路呀
爱米信米等米求米给个offer
门头沟学院 算法工程师
OfferLimitedExceeded
华南理工大学 C++
（挖个坟）这题在竞赛见过，类似hdu5887的map维护超大背包，刷到这个帖的朋友没思路可以去看看
只因不会Java
中共广东省委党校 golang
文远开始了？
相关推荐
荣耀二面122人在聊
查看6道真题和解析 点赞 评论 收藏
分享
