招银网络C++面经

1. 哈夫曼树

2. 手撕建堆

3. 内存碎片

害怕。。。根本不是我想象中的国企

复盘面经 有些不是很确定，欢迎讨论！

40min 其实记得概念的话也不是太难，主要是有些真的不记得了tat

1. 哈夫曼树

哈夫曼树是带权路径长度最短二叉树，树的带权路径长度规定为所有叶子结点的带权路径长度之和。

算法：每次挑和最小的两个子树作为左右子树，他们的和作为根节点的值。

节点的特点：父节点为左右子节点的和

树的特点：值越大的叶子节点离根最近

找到最小的叶子节点：自己想了一个feasible的吧。。。：节点结构体加一个数据成员标记树的高度，递归找最高的树的叶子节点。

他是平衡树吗：不是

2. 内存碎片

什么是内存碎片：内存中小且不连续，因此不能使用的空闲空间

内存碎片的产生：内部碎片：分页机制导致的，因为只能分配固定大小的内存，四舍五入剩下的就是内部碎片，这些碎片已经分给了进程，只是没用；外部碎片：频繁的分配和回收物理内存造成的，未分配的内存块小且地址不连续，没办法分给其他进程，这些碎片没有分配给进程。

如何避免产生内存碎片：其实到最后也不太明白这个问题是什么意思，如果是操作系统层面可能是内存分配算法，将相邻的内存碎片连接起来；限制不同存储量内存块的数目之类的；在代码层面可能就是要用alloc分配内存么？也不太知道。。。

3. 堆排序

堆排序的算法是怎样的

实现一下

4. 如何拷贝内存

答了memcpy，感觉可能就是想问这个吧？然后问了memcpy需要注意什么：内存可能重叠

5. SQL

删除某一列中的重复数据

面试体验不太好。。都说了哈夫曼树的具体定义忘记了，也没有提示哈夫曼树到底是啥，还让继续撕哈夫曼树相关的代码。。。。

当时只记得哈夫曼编码那堆0101了，面试完了冷静了一下终于想起来哈夫曼树是什么了。。。

最后剩下几分钟让建个堆，脑子一乱。。。也没写完…