面试比较自闭，我会尽可能回忆起更多的内容，而且写我当时的回答，希望大家讨论，互相学习！

上来先三道算法题，写完再叫面试官（但不挂电话）

1. 方阵逆时针旋转。

我现在看不到代码了，凭记忆说一下哈。

先想了用额外空间的情况，模拟了一下。
a是原始矩阵（方阵），b是旋转之后的。

自己写一个3*3的矩阵模拟一下，就会发现，
左边是原始矩阵的位置，右边是转置之后的。
(x_a, y_a) ->(x_b, y_b) 表示一个元素在a矩阵的坐标是x_a, y_a，在b矩阵是x_b, y_b。

(0, 0)->(2, 0)
(0, 1)->(1, 0)
(0, 2)->(0, 0)

(1, 0)->(2, 1)
(1, 1)->(1, 1)
(1, 2)->(0, 1)

看出规律了吗？
一个元素在b矩阵的y值是a矩阵的x值，它的x值是3 - x_a - 1。
所以，对每个x,y
b[a.size() - y - 1][x] = a[x][y]
不用额外空间的情况
我最后写的是这种。
思路是，最外层枚举(0, 0), (1, 1)...(matrix.size() / 2, matrix.size() / 2)这种坐标。然后里层按照上面的映射换，一圈下来是个闭环。代码有点难写，我面试时写的估计也得debug一下。

双向链表的头部插入，删除指定值，冒泡排序。

这里为什么是双向链表呢？我觉得双向链表有点降低难度诶。

插入不必讲。

删除，注意一下删除头部的情况，是让head = head->next。
如果是单向链表的话就让一个东西在后面跟着，first = head, second = second->next。
如果找到second->val == v（v是要删除的），那就first->next = second->next。

冒泡排序，我取了个巧，swap相邻元素的val值，而不对链表的结构进行操作

找一个数组的第10大元素

这是一道经典的题了，百度“数组第K大”可以找到答案。

我觉得用堆是最好的办法，但是它题目说用C语言，我认为默认不给我用堆。

大家复习一下快排

先取一个基准数，然后把比这个数小的放左边，比它大的放右边，它放中间。

这里是求第10大，所以我们反过来，把比基准数大的放左边，比它小的放右边。

因为比他大的都放左边了，那它的坐标就表示它是第几大的，假设坐标为i。

如果i == k，那a[i]就是答案。
如果i > k，那说明要找的数在左边。
如果i < k，说明要找的数在右边。

在递归查找即可。

代码不太好写，面试的时候只是写个大概，如果之后还又心情的话再补一下代码

开始问答环节

自我介绍

略了

在百度做的项目

略了
反思，我实习只是做一些边边角角的工作，也不太懂这个项目是干嘛的，技术原理都说不清楚，因为是在百度自研的框架开发的，也没搞懂底层原理，底层的东西大佬都写好了的。唉，惭愧

go是多线程还是多进程

多线程 // 我懵的

多线程编程需要注意什么？

注意如果同时读写数据的话会出问题。//我真不会啊orz，我太菜了。
这里bb了半天，没说明白。

go是怎么抓数据（大概这个意思吧）的

emmm因为我只是调用那个框架的函数，我也不知道啊。（问得好深

这里开始断片，接下来的是连不到一块了，

linux是怎么抓数据的（记不清了，大概这个意思）

不知道。。

在linux用什么命令查看正在运行的端口？

我工作的时候记在笔记里，现在不记得了。

TCP和UDP的区别。

TCP是可靠链接，UDP是尽最大努力的。
TCP是面向连接的，UDP是面向报文的。
TCP有拥塞机制，UDP没有。

（这个没有查，我长期记忆记的这些）

你知道拥塞机制和流量机制有什么区别吗？

我知道拥塞机制，b收到a的数据包之后就会返回一个ack，表示ack序号之前的包都收到了，然后如果丢包过多的话就会降低发包的速度。

流量机制不知道。

浏览器打开一个网址，从浏览器到服务器上的代码，经历了怎样的过程？

先是DNS域名解析嘛，然后到得到了IP地址，就取发起一个HTTP会话到这个地址，然后通过TCP进行封装成数据包，输入到网络层。

在客户端的传输层，把HTTP会话请求分成报文段，加上源端口和目的端口，比如服务器使用80端口，客户端是系统随机出来一个端口。

接下来数据链路层是ARP协议啥的，我记不清了。

Q：然后呢？

然后应该服务器那边有个端口监听，接着。。

我做项目的时候知道我们的框架有一个叫路由的东西，定义了GET和POST，就是访问哪个URL，就会映射到代码的哪个函数，然后就执行。

（emmmm太难了。我太菜了。）

SQL和redis有了解吗？

不了解

map和unordered_map有什么区别？

map的底层是红黑树，unordered_map是hash。

hash怎么实现的？
emmm先说一下为什么要用hash吧，就是有一个key要映射到一个value，然后有一个连续的空间是存value的，通过hash函数，把key映射到这片连续的空间上。

红黑树有什么特点？

先说一下，最开始是二叉排序树，然后发展到平衡树，而红黑树相对于平衡树来说，旋转操作比较少，对于插入删除比较频繁的应用场景，用红黑树比较好，所以map用红黑树。

那它有什么特点呢？

我想想。。比如根节点是黑的。

（其他记不起来了mmp，考这个有意思吗）

C++的多态是怎么实现的？

每个类都有一个虚函数表，然后当父类指针指向的子类对象调用虚函数时，就会找那个表，然后映射到子类定义函数的地址。

还问了一些我记不得了，但我还是理解了这块的。

定义一个main函数，一个f函数，在f函数里声明100万的数组，然后返回。这个程序的编译运行是怎样的？

首先呢，局部变量是放在栈里，100万放到栈里有可能会栈溢出，这个编译可以过，但是运行可能会出现segment fault。

面试官重新说了下，把100万改成10个。还特地强调了CPU的状态

大概就是，调用的时候有个JMP命令，然后跳转到f函数的起始地址，接着开始执行f函数。

执行JMP的时候CPU的状态是怎样的？

哦。。那就是有一个寄存器存当前执行指令的地址，执行到JMP的时候，因为JMP有个地址嘛，就会取那个地址取指令，然后执行。（这是计算机组成原理的知识吧。。我记起来一些）

知道用户态和内核态嘛？

知道
可以说一下吗？
内核态能执行的指令权限最高，而用户态的权限较低。

那你用户态调用内核态的函数时，是怎样实现的？

我不知道。。。

有100亿个QQ号，肯定有重复的，要求去重。

用布隆过滤器（我还记错记成多隆orz，面试官纠正了一下）
然后blabla说一下原理。

看了这篇文章才知道的
详解布隆过滤器的原理，使用场景和注意事项 - Young Chen的文章 - 知乎
https://zhuanlan.zhihu.com/p/43263751

用布隆过滤器会出现什么问题？
我哪知道，我知道布隆过滤器已经很不容易了。。。哭

大概没有了吧。

反思

要了解业务，我太水了，做项目不认真了解项目背景，只是高T派过来任务，然后我去coding。像以前刷题一样做需求，是远远不够的。

要了解一下底层底层没了解，不知道调的框架底层是咋实现的。

这段时间主要花在算法上了，主要是上次被wxg的算法整自闭了。

上次面试顺便记一下

是wxg的，也是上来就四道算法题，
第1题当场写的有Bug
第2题提示之后才做出来（其实就是中序遍历，但我太久没复习数据结构了），
第3题因为做过所以直接秒。
第4题写了个假算法

于是面试结束了。。。
题目如下：

链表的奇偶合并。https://leetcode-cn.com/problems/odd-even-linked-list/
1->2->3->4->5变成1->3->5->2->4

二叉排序树求第k大元素。
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

装雨水问题https://leetcode-cn.com/problems/trapping-rain-water/

类似这道用rand7()求rand10()，只是数字不一样。

https://leetcode-cn.com/problems/implement-rand10-using-rand7/