文远知行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 广东

相关推荐

05-28 22:52
已编辑
北京理工大学 C++
京东零售-产研timeline:0515&nbsp;一面0521&nbsp;约二面0526&nbsp;二面0527&nbsp;约三面0528&nbsp;三面,下午oc##一面:50min1.&nbsp;简单介绍一下项目2.&nbsp;zookeeper是做什么用的&nbsp;&nbsp;&nbsp;&nbsp;a.&nbsp;为什么用zookeeper,还了解哪些其他的3.&nbsp;为什么用protobuf而不是其他协议&nbsp;&nbsp;&nbsp;&nbsp;a.&nbsp;跟其他协议比有什么优势&nbsp;&nbsp;&nbsp;&nbsp;b.&nbsp;为什么速度快体积小4.&nbsp;怎么解决tcp粘包拆包问题的5.&nbsp;遇到过什么困难,怎么解决的6.&nbsp;硕士学过什么课程&nbsp;&nbsp;&nbsp;&nbsp;a.&nbsp;一般怎么自学的&nbsp;&nbsp;&nbsp;&nbsp;b.&nbsp;有没有关注什么技术网站’7.&nbsp;网络是怎么通信的8.&nbsp;tcp建立连接过程&nbsp;&nbsp;&nbsp;&nbsp;a.&nbsp;为什么要三次不能两次9.&nbsp;一个存了40亿个字的文件,在一个内存(2GB)很小的旧电脑里,怎么查找里面有没有没出现某个数?可以用什么数据结构?怎么设计算法?&nbsp;&nbsp;&nbsp;&nbsp;a.&nbsp;不知道,提示下说了与或,说了哈希set但很暴力,面后查了一下:用位图(BitSet),原理:用一个足够大的&nbsp;bit&nbsp;数组(每一位表示一个整数是否出现过)10.&nbsp;MySQL索引结构是什么11.&nbsp;唯一索引和主键索引区别?12.&nbsp;联合索引(a,b)能不能查b?13.&nbsp;了解哪些设计模式?单例模式的使用场景?14.&nbsp;本科学过什么为什么换专业15.&nbsp;为什么想做后端16.&nbsp;能不能转java17.&nbsp;C++是怎么学习的18.&nbsp;还面了什么公司反问:1.&nbsp;业务做什么的、技术栈2.&nbsp;对实习生有什么要求?3.&nbsp;怎么去提高那些方面?前情:前一天半夜刚做完测评,于当日下午突然接到电话,说下周一有没有时间聊一下,说了两个时间都刚好跟别的撞了,遂约在当晚八点半。太突然了鼠鼠突然迎来人生处女面,很多东西都没有准备好🥹不过面试官人真超好一直笑呵呵的很亲和,鼠鼠太菜了全程很多题没答上来但氛围都没有尴尬。##二面:30min1.&nbsp;可以实习多久2.&nbsp;为什么想做这个方向3.&nbsp;专业问题,未来规划问题4.&nbsp;举一个体现学习能力的例子5.&nbsp;遇到了什么难点,怎么克服的6.&nbsp;具体是怎么去学习的7.&nbsp;手撕一个最长回文子串,共享屏幕,限时5min8.&nbsp;写一个sql题:表示不会写9.&nbsp;反问:实习生工作、对实习生的期待、流程要多久##三面:40min就是常规问题,能实习多久、毕业压力大不大、学校做的研究课题和创新点、遇到的困难怎么解决的、最有成就感的事情、讲一个学生工作经历、为什么转专业、未来规划之类的。反问:部门业务、实习生业务、实习生人数、转正率、是否要转java和会不会有要求、工作氛围和工作时长等。
点赞 评论 收藏
分享
评论
8
56
分享

创作者周榜

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