<
回复: 10
收起左侧

HRT | New Grad | CoreDev | 电面第一轮

 
匿名用户-1OI3C  2022-11-2 01:29:17
本楼:   👍  4
100%
0%
0   👎

2022(7-9月) 码农类General 硕士 全职@hudson-river-trading - 网上海投 - 技术电面  | 😐 Neutral 😐 AverageOther | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 匿名 于 2022-11-1 18:31 编辑

hrt电面不让开摄像头也挺扯的,主题来了:
简单自我介绍之后,询问cv上面做过的intern和一个project。面试之前还是需要稍微复习一下自己的cv。
正题部分 (C++和OS基础)问题用红色标出了


Question: Do you know std::vector in C++, what is the time complexity of insertion/deletion
Ans: It's a dynamic array where you can put your items inside. For insertion, it is amortized O(1) complexity, and for deletion, O(1).


Question: What do you mean by amortized?
Ans: When the vector's size reaches its capacity, we have to increase the size. In such case, we have to do the copy of all previous elements, this will increase the latency that you have to wait for the insertion.


Question: For example, if I have 100 elements to insert, how many times the copy will be, and what would be the time complexity?
Ans: Say we double the size when the size reaches the capacity, then for n items, we have to do log(n) copies.


Question: Since you are doing log(n) copies, does it mean that the total time complexity is n * log(n)?
Ans: No, because we are not coping the full array, when capacity increases from 1 to 2, we are only copying 1 element for example. In total, we are only copying O(n) elements.


Question: OK, now we delete some elements, it would be a huge waste to keep the large capacity, how would you do to reclaim the memory?
Ans: We can reduce the capacity to half, if the occupied ratio is dropped below some threshold.


Question: How would you do that exactly? For example, if you have a vector with capacity=100, and 49 elements inside, would you reduce the size to half?
Ans: We can have a buffer time, for example, only reduce the capacity to half, when the occupied ratio is 0.4. In your case, I will drop the capacity to 50, when there are 40 elements inside.


Question: I like the idea of buffering. What if you do not do the buffer, and the size dropped to 49?
Ans: It can introduce some zig-zag patterns. For example, you drop to 49, the capacity is reduced to half, and then you do the insertion, and the capacity is grown to double. This process can be repetitive. If you have the buffer, or delayed shrink, this kind of problem can be avoided.


Question: OK, I am good with this part, let's move on to the next topic. Do you know what the new operator is doing in C++?
Ans: The new operator allocates the memory of the object, and then calls the constructor of that object.


Question: Then what is malloc doing?
Ans: malloc on the other hand, only allocates the memory, and returns the pointer to that heap memory region.


Question: If you want to implement your own malloc, what would you do?
Ans: You can have a Freelist and AllocList, which contains the regions that are free to use, and regions that are already malloced. When the user calls malloc, you find inside the FreeList for a region that has a larger size compared to the user request size. Then you push back the remaining free regions back to the FreeList for others to use. There can be multiple strategies to choose which region to use here: best-fit, first-fit, last-fit, and so on.


Question: that sounds cool, how would you do the de-alloc. When users call de-alloc, they only specified a pointer. You don't know how large
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
ons, depending on its implementation.


Question: Why is the inline function useful?
Ans: It avoids the jump instruction. The CPU is better at handling in-sequence instructions to do speculative and out-of-order execution.


Question: Why the jump instruction is slow?
Ans: It is a control hazard, which can waste some CPU computations, and it has to load the instructions in a different code region. This can be troublesome if that code region is not inside the L1 i-cache.


Question: What is the disadvantage of using an inline function?
Ans: It can introduce the problem of code bloating. The size without the inline function can be very small initially. But if you use it unwisely, the code can grow to a very large size. It is also not good for the cache performance.


Question: I am done with my question part, you can go ahead with your questions!
Ans: OK, -,-||

评分

参与人数 11大米 +30 收起 理由
等闲芳草斜阳 + 1 赞一个
sudeepto.g + 1 点个赞
清道神君 + 20
blueberrysauce + 1 很有用的信息!
微信用户_d1d7d91 + 1 很有用的信息!

查看全部评分


上一篇:Bloomberg过经
下一篇:Bloomberg约EM面到底要多久,没消息是据了吗?

本帖被以下淘专辑推荐:

地里匿名用户
匿名用户-GQQO0  2022-11-2 01:59:36
本楼:   👍  0
0%
0%
0   👎
感谢分享。五年tech公司Java选手,曾经考虑过冲一冲trading公司,看了这个帖子,必须花足够多的时间去学习c++,才能去面试

这么一看微软员工倒是可以无缝衔接lol
回复

使用道具 举报

地里匿名用户
匿名用户-1OI3C  2022-11-2 03:14:55
本楼:   👍  0
0%
0%
0   👎
匿名用户 发表于 2022-11-1 18:59
感谢分享。五年tech公司Java选手,曾经考虑过冲一冲trading公司,看了这个帖子,必须花足够多的时间去学习c ...

其实c++这些内容也是需要专门去了解才行,日常开发积累知识的速度还是太慢了。只不过整体而言c/c++需要自己做memory management,和其他语言还是有很大的区别。
扫码关注一亩三分地求职移民公众号
更多干货内容等你发现
回复

使用道具 举报

地里匿名用户
匿名用户-PU3WL  2022-11-2 08:47:49 来自APP
本楼:   👍  0
0%
0%
0   👎
说实话并不是很难🤣

有本科水平的os和计组知识就足够了

补充内容 (2022-11-02 08:55 +8:00):
C++ vector那个resize其实还有一个优化

就是根据vector存的元素是否实现no except的移动构造,决定直接move还是做一次拷贝
回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   1
100%
0%
0
lz进下一轮了吗
回复

使用道具 举报

clarkmzhang 2022-11-7 10:28:52 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   9
90%
10%
1
为啥说insert和erase是常数复杂度?按说是线性的啊,你要把元素重新移动,占用连续的内存空间。

https://cplusplus.com/reference/vector/vector/insert/

补充内容 (2022-11-07 10:30 +8:00):
可能楼主说的是push_back和pop_back。。。
回复

使用道具 举报

地里匿名用户
匿名用户-1OI3C  2022-11-9 03:14:20
本楼:   👍  0
0%
0%
0   👎

进了 下一轮是coding
回复

使用道具 举报

地里匿名用户
匿名用户-1OI3C  2022-11-9 03:14:58
本楼:   👍  0
0%
0%
0   👎
clarkmzhang 发表于 2022-11-7 03:28
为啥说insert和erase是常数复杂度?按说是线性的啊,你要把元素重新移动,占用连续的内存空间。

https:/ ...

对的 说的是push_back和pop_back 😂
回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   1
100%
0%
0
匿名用户 发表于 2022-11-8 14:14
进了 下一轮是coding

我也进下一轮了,想不想一起准备一下
回复

使用道具 举报

地里匿名用户
匿名用户-1OI3C  2022-11-9 03:27:49
本楼:   👍  0
0%
0%
0   👎
微信用户_f46be73 发表于 2022-11-8 20:18
我也进下一轮了,想不想一起准备一下

估计不准备了,明天就面 hhhh
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表