文远知行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-09-22 21:12 江苏
这个背包问题没啥更好地思路呀
1
送花
回复
分享
发布于 2023-10-07 17:55 北京
滴滴
校招火热招聘中
官网直投
文远开始了?
点赞
送花
回复
分享
发布于 2023-09-22 14:58 广东
佬挂的时候有感谢信吗
点赞
送花
回复
分享
发布于 01-20 11:29 广东
(挖个坟)这题在竞赛见过,类似hdu5887的map维护超大背包,刷到这个帖的朋友没思路可以去看看
点赞
送花
回复
分享
发布于 03-15 17:03 广东

相关推荐

文远三面&nbsp;压力面😅上来就说后面有面试,说要弄快一点,赶时间(时间自己没安排好吗??)然后问我知道Linux文件系统吗,有哪些目录(简单说了两三个,然后很不耐烦地问还有吗还有吗。。。有我早说了)然后又问我Linux网络模块是怎样的(我就说不了解,然后他说那你在学校学了哪些东西,我就说学校学的是一些基础课程的理论还有对应的实验课,没有要求我们具体要了解像Linux的文件系统啊、网络模块、各种bash的复杂命令之类的,他就嘲笑地看着我。这个时候基本没心情答了,想着赶紧结束吧,你们不招可以前面就直接挂的)之后问我数据库的&nbsp;select&nbsp;*&nbsp;from&nbsp;user&nbsp;where&nbsp;user.user_name&nbsp;like&nbsp;(&amp;quot;%xx%&amp;quot;)&nbsp;这条语句做什么的(我跟他讲解了后,说需要用全表扫描,他就说这个他们业务很常见的,那这岂不是很耗时,然后问我可以用哪些数据结构来做索引;我就说可以将这条命令拆成&nbsp;like&nbsp;&amp;quot;%xx&amp;quot;&nbsp;和&nbsp;like&nbsp;&amp;quot;xx%&amp;quot;,然后可以用字典树来查询这些前缀匹配的,同时也用一个字典树记录后缀匹配的,然后他就嘲笑地看着我,说那就这样,问下一个问题吧)最后出了道题:大文件里面的字符串排序,同时内存不足,让我用写论文的方式来描述步骤(题主大三,还没写过论文。我跟他介绍了归并排序方式,拆成小文件来加载到内存中排序,然后他说“你这里是两个步骤,在我看来这就只是一个归并的方法”,然后我就跟他说第一步找出问题的关键,第二步用归并排序解决问题,第三步检验结果,他就说你这是数学证明的方式,要我用计算机科学与技术的方式解决,我tm???然后他就说用divide&amp;amp;conquer方式,将文件divide拆成小文件,然后conquer处理小文件排序。。。我真想反问说着为什么就是计算机科学与技术的方式来描述了,这是你自己的方式吧。。。)最后他说这次面试就这样吧,说我没有怎么准备。。。(你tm想招人的话会问这些问题?)
点赞 评论 收藏
转发
8 50 评论
分享
牛客网
牛客企业服务