文远知行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届软开秋招面试经验大赏##文远知行#