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

相关推荐

秋招差不多也就这样了,之后捡漏补录啥的就随缘吧,现在手头大概是这三个工作,希望大伙给点意见个人情况:深二代,可以接受忙但别太卷,主要还是想做后端,想留在广东但还是优先考虑未来发展offer华为:终端云祥云部门(nx15)对接人说争取14a,已经报批了,开奖希望比较大。base东莞,优点就是据说祥云的风评还可以,业务和强度啥的都还不错,不会说很卷,也是纯互联网业务和技术栈。而且离家近,离我家开车40分钟就到了。但华为有进去定岗给我整到测试或者其他岗的风险,而且华子的福利啥的也很差(虽然我下面开水团也没啥福利就是了)美团:实习转正(n+2x15.5)实习转正大sp无签字费,优点是团队氛围还行,比较熟悉,而且业务核心,做到店服务零售那一块的,美团在互联网的title比华子大,跳槽可能好一点,但在上海,虽然是大城市玩的多但上海的物价和租房成本都非常高,扣除这些刚性开销算了一下到手可能还真不一定有华子高。而且组内可能因为比较核心所以强度很大很卷,正职基本上10-9/10-5的作息深圳环水集团:市属国企,进去定岗,年薪全包大概12-15万,到手一般来说都打个七折吧。垄断性国企,反正就是比较稳定,不过发展比较受限,其实并不是很想考虑,但没想到这么快给我发offer了引流:字节百度腾讯腾讯音乐小红书美团华为oppo携程阿里
华为求职进展汇总
点赞 评论 收藏
分享
评论
8
61
分享

创作者周榜

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