招银网络C++面经
1. 哈夫曼树
2. 手撕建堆
3. 内存碎片
害怕。。。根本不是我想象中的国企
复盘面经 有些不是很确定,欢迎讨论!
40min 其实记得概念的话也不是太难,主要是有些真的不记得了tat
1. 哈夫曼树
哈夫曼树是带权路径长度最短二叉树,树的带权路径长度规定为所有叶子结点的带权路径长度之和。
算法:每次挑和最小的两个子树作为左右子树,他们的和作为根节点的值。
节点的特点:父节点为左右子节点的和
树的特点:值越大的叶子节点离根最近
找到最小的叶子节点:自己想了一个feasible的吧。。。:节点结构体加一个数据成员标记树的高度,递归找最高的树的叶子节点。
他是平衡树吗:不是
2. 内存碎片
什么是内存碎片:内存中小且不连续,因此不能使用的空闲空间
内存碎片的产生:内部碎片:分页机制导致的,因为只能分配固定大小的内存,四舍五入剩下的就是内部碎片,这些碎片已经分给了进程,只是没用;外部碎片:频繁的分配和回收物理内存造成的,未分配的内存块小且地址不连续,没办法分给其他进程,这些碎片没有分配给进程。
如何避免产生内存碎片:其实到最后也不太明白这个问题是什么意思,如果是操作系统层面可能是内存分配算法,将相邻的内存碎片连接起来;限制不同存储量内存块的数目之类的;在代码层面可能就是要用alloc分配内存么?也不太知道。。。
3. 堆排序
堆排序的算法是怎样的
实现一下
4. 如何拷贝内存
答了memcpy,感觉可能就是想问这个吧?然后问了memcpy需要注意什么:内存可能重叠
5. SQL
删除某一列中的重复数据
面试体验不太好。。都说了哈夫曼树的具体定义忘记了,也没有提示哈夫曼树到底是啥,还让继续撕哈夫曼树相关的代码。。。。
当时只记得哈夫曼编码那堆0101了,面试完了冷静了一下终于想起来哈夫曼树是什么了。。。
最后剩下几分钟让建个堆,脑子一乱。。。也没写完…
#招银网络##校招##C++工程师##面经#