简寻第二轮面试

Interview

第二轮

你用过STL吗？ hashmap知道是怎么实现的吗？

用过， hashmap是用红黑树实现的。

为什么是用红黑树而不是使用AVL？

因为AVL是高度平衡的树，每次插入删除都要调整树的平衡，而红黑树不需要。

C++ STL中的标准规定：
* map， 有序
* unordered_map，无序，这个就是用散列表实现
为什么不用 AVL 树作为底层实现, 那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的. 选取红黑树, 我认为是一种折中的方案.
链接：https://www.zhihu.com/question/20545708/answer/20149616

那知道unordermap吗?原理是什么?

知道. unordermap是使用hash实现的. 通过哈希函数将一个值映射到小的"指纹",使用的时候反用哈希函数求出值.

如果映射到相同的值时,有什么解决方法?

我想到的就是, 再一次使用一个另外的哈希函数.

还有其他吗?

暂时想不到了.

你有实现过哈希函数吗?

有.我在学数据结构的时候, 都把学过的实现一遍. 学哈希函数的时候, 只是使用简单的取余来做, 没怎么遇到过这个情况. 遇到也是用再一次哈希来做的.

你接触过C++11吗?知道有什么?

有auto自动推到类型, for循环改进, 移动, bind, lambda函数, constexpr, 还有变长模板等.

智能指针知道吗, 是怎么实现的.

我听说过智能指针, 不过没有了解过. 我猜是像初始化了之后, 就会在生存期结束后自动析构

恩, 是这样.

C++的多线程实现里, lock_gard也是这样的

恩

(我又忘记补上了...我猜是自动隐式调用由析构函数, 因为我在wine里实现过lock_gard)

RAII
RAII全称为Resource Acquisition Is Initialization, RAII要求，资源的有效期与持有资源的对象的生命期严格绑定，即由对象的构造函数完成资源的分配(获取)，同时由析构函数完成资源的释放。在这种要求下，只要对象能正确地析构，就不会出现资源泄露问题。
比如: std::lock_guard<std::mutex> lock(mutex);就是会自动释放的.

学过linux是吧, 知道进程有什么方法来进行通信吗?

• 匿名管道
• signal
• 文件锁可以是吧,既然文件锁可以,那么文件内数据也可以
• (现在才想起还有tcp)

进程之间传递信息的各种途径(包括各种IPC机制)总结如下: 
* 父进程通过fork可以将打开文件的描述符传递给子进程 
* 子进程结束时,父进程调用wait可以得到子进程的终止信息
* 几个进程可以在文件系统中读写某个共享文件,也可以通过给文件加锁来实现进程间同步 
* 进程之间互发信号,一般使用SIGUSR1和SIGUSR2实现用户自定义功能
* 管道
* FIFO mmap函数,几个进程可以映射同一内存区
* SYS V IPC,以前的SYS V UNIX系统实现的IPC机制,包括消息队列、信号量和共享内 存,现在已经基本废弃
* UNIX Domain Socket,目前最广泛使用的IPC机制

有听说过内存共享的方法吗?

有, 不过忘记了.

那么知道epoll吗?

不知道.

那问问多线程吧.

好像linux很多都是使用多进程而不是多线程, 因为多进程一个进程挂掉, 也不会令整个程序挂掉.但是多线程就会了.

你确定是这样吗? 会发生在什么情况?

发生在内存耗尽或者申请过大的内存

你觉得操作系统的保护会让一个应用程序发生这样的情况吗?

不会.我想想还有什么情况(⊙o⊙), 想不到了. 我是在知乎上一个答案看回来的,他是这样说的.

如果这样, 那很多程序都是用多进程而不是多线程了

好像是这样. (我想起, 多线程可以共享资源,方便通信, 但是多进程就不行了. 哎,不过电话面试的时候就是这样, 不忍心想太久)

问一下算法吧, 有什么排序算法?

快速排序, 插入排序, 选择排序, 冒泡排序, 桶排序, 基数排序, 归并排序
(忘记说堆排序,以及希尔排序了, 我对他们两个熟悉度不够)

假如要找到一个第10大的数字, 有什么办法?

我现在想到的是, 选择一个排序算法将其排序, 然后再表示出第10大的数字.不过这并不优雅, 我再 想想有什么办法.
想了一阵子...

你想想冒泡排序你是怎么做的?

我会两两比较交换, 比较到低10次后, 就已经得到第10大的数字了.

算法复杂度是多少?

O1 (犯傻了)

是这样吗? 第一次两两比较,就比较了n次了

恩,对. 搞错了. 一次就On了, 然后10次是10*On, 所以复杂度还是On

没错. 那么, 快排是怎么做的?

利用中枢值将其划分, 只要大的那一边, 再用新的中枢值将其划分, 如此类推, 最后大致在10左右的时候, 就直接用快速排序将其排序, 第10个数就是所求.
(中间有小插曲, 信号不太好, 他不太听清楚, 最后我到了宿舍外面)

虽然不是很清楚, 不过大致你的做法是对的.

聊一下计算机网络吧. 你知道tcp为什么要三次握手吗?

跟上次面试一样回答 (忘记加上四次挥手的知识了)

TCP有什么状态?

状态是指Wait, 那种吗?

对.

有establish, Finish, Wait, 还有一个是4次挥手, 发送方发送并接受等待的状态

那个是Time_Wait

对. 然后有固定的等待时间

问问数据库吧. 用过什么数据库?

Mysql

你知道数据库索引吗?

知道. 用索引可以增加查找速度.

知道是怎么实现的吗?

不知道. 是对每列做一个索引吗?

如果这样, 数据量很大的时候性能没有优势.

知道事务的隔离级别吗?

不清楚.

用过socket吗? 知道粘包问题吗?

用过, 但是不知道粘包问题.
我当时做过文件传输的程序, 只是做一个循环, 每次发送8byte直到发完, 接收方就写这样子.

问题产生
一个完整的业务可能会被TCP拆分成多个包进行发送，也有可能把多个小的包封装成一个大的数据包发送，这个就是TCP的拆包和封包问题。
下面可以看一张图，是客户端向服务端发送包：
1. 第一种情况，Data1和Data2都分开发送到了Server端，没有产生粘包和拆包的情况。
2. 第二种情况，Data1和Data2数据粘在了一起，打成了一个大的包发送到Server端，这个情况就是粘包。
3. 第三种情况，Data2被分离成Data2_1和Data2_2，并且Data2_1在Data1之前到达了服务端，这种情况就产生了拆包。
由于网络的复杂性，可能数据会被分离成N多个复杂的拆包/粘包的情况，所以在做TCP服务器的时候就需要首先解决拆包/粘包的问题。
TCP粘包和拆包产生的原因
1. 应用程序写入数据的字节大小大于套接字发送缓冲区的大小
2. 进行MSS大小的TCP分段。MSS是最大报文段长度的缩写。MSS是TCP报文段中的数据字段的最大长度。数据字段加上TCP首部才等于整个的TCP报文段。所以MSS并不是TCP报文段的最大长度，而是：MSS=TCP报文段长度-TCP首部长度
3. 以太网的payload大于MTU进行IP分片。MTU指：一种通信协议的某一层上面所能通过的最大数据包大小。如果IP层有一个数据包要传，而且数据的长度比链路层的MTU大，那么IP层就会进行分片，把数据包分成托干片，让每一片都不超过MTU。注意，IP分片可以发生在原始发送端主机上，也可以发生在中间路由器上。
TCP粘包和拆包的解决策略
1. 消息定长。例如100字节。
2. 在包尾部增加回车或者空格符等特殊字符进行分割，典型的如FTP协议
3. 将消息分为消息头和消息尾。
4. 其它复杂的协议，如RTMP协议等。

你了解Docker, Memcache这些新技术吗?

Docker知道, 就是容器. 用来配置环境的.
比如说, 我们到公司, 是要配置开发环境的, 而不同机器都需要配置, 是很麻烦的事情, 还会遇到更新的问题等等. 但是用Docker, 只要配好并且发布容器让其他机器使用, 就不用配置了.

你拿过什么奖项吗?

blabla

你在项目中, 怎么存储班级,学生, 对应的老师这些信息的?

外键(⊙o⊙) bla

你还有什么问题要问我吗?

我对C++没有很熟悉, 再问我C的问题吧

你知道, malloc/free频繁使用的时候, 会产生很多内存碎片. 你有什么办法解决?

用环形结构解决.

不过这样, 还是会产生碎片的, 因为不一定顺序释放呀.

这样

malloc， free内存碎片，memcache
你做过什么项目
了解什么新技术，docker，xx这些呢？