作者：从0开始学c
链接：https://www.nowcoder.com/discuss/128236
来源：牛客网

然后问算法，问了反转链表，要求空间复杂度o1，我在循环内用了一个局部指针变量，虽然不优雅，但是局部变量每次循环完都会被析构，他硬说我的空间复杂度是on。

然后问了虚函数，这是唯一问的c++，我感觉他也就会个虚函数了。

然后问找前k大的数。

我： 如果内存放得下的话，用类似快排的思想，partition把大的放左边，小的放右边，调用partition之后，如果分界元素等于k，则返回最左边的k个值；否则对k所在的半边递归调用parition，平均时间复杂度是on。

面试官（惊讶）： 时间复杂度是on？

我： 是啊

面试官： 真的是么？

我： 是啊，假如每次分界完，平均下次要处理的元素占总元素数的a/b，那么时间近似是（1+a/b+（a/b）^2+…）n= b/a*n

面试官： 那我的k要是很大，接近n，你这个不就是n平方了么

我： a/b是平均下次要处理的元素占本次处理的总元素的比值，跟k无关

面试官： 那最坏时间复杂度是多少

我： on^2 当数组已经有序，每次处理完规模减少1。 如果你觉得这个方法不好，在内存放得下的情况下，那我们用堆做，建一个最大堆，建堆的时间复杂度是on，调整k次，调整一次的时间复杂度是ologn，一共是o（n+klogn）

面试官： 建堆的时间复杂度是on？

我： 有什么疑问么

面试官： 你确定？

我： 确定！

面试官： 你再想想？

我： 建堆是从最后一个非叶结点开始调整，倒数第二层最多有n/2个需要调整的元素，最多需要调整1次，倒数第三层最多有n/4个需要调整的元素，每个最多需要调整2次，以此类推，最后累加起来接近线性时间复杂度。

面试官： 额…

我： 换一种方法，如果数据比较大，内存放不下，可以用优先队列，实现也是堆。优先队列是用一个最大堆，我们求前k大要用最小堆，所以要重载小于号运算符，优先队列重载时候要指定底层容器，我一般指定的是vector。执行时候如果队列里面的元素少于k个，则直接插入；否则将该元素与top（）比较，如果大则删掉top把这个元素放到队列中。

面试官：额..

我： 如果重复元素算一个，就用set，set是默认从小到大排列的，所以不需要重载运算符。

然后面试官没有回话，思考了一会，用“你会数据库么”结束了对算法的问询。在得知我不会数据库之后，面试官开始了他的主导，一直问数据库。我说，我不会数据库，要不你问问别的吧。然后他问我会网络么，我说曾经会一些，很久没用了，于是就问我tcp连接的终止，在我答完四次握手之后，问我服务器单方面终止链接之后，客户端继续发送数据会怎么样； 双方都终止了之后，客户端继续向服务器发送数据会怎么样。
如何处理get和post
tcp接收窗口和拥塞窗口
什么时候会向对端传窗口大小
extern C的意义
假设rtt（数据从两端一来一回） 100ms，那么从输入一个http://url到得到网页要多少时间
https呢？
连续发送两次http请求，会得到两次结果吗？可能第二次比第一次快吗？
是否了解TCP包头阻塞?
服务器状态502 503 504什么问题，怎么排查
netstat具体查看什么问题
写题：多路归并（用了堆，在细节上有一些问题）
看代码中的问题：
class Foo
{
public:
Foo(){_p = new int();}
~Foo() {delete _p; _p = nullptr;}
private:
int* _p;
}
sql：三句查询，要求建立索引来优化查询
一些linux语句的作用：less more sed awk du df dd at tee crotab xargs
最近看了什么技术书籍

二面
linuxIO模型，区别在哪
线程独立拥有哪些资源
协程和线程有什么差别，优势呢？
get和post有什么差别
sendfile的优势在哪？
代码：随机播放100首歌（洗牌算法/这个我把自己绕进去了，洗一次直接输出就完了，我当时脑子短路了，洗一次播一首非要再洗一次来手动提升复杂度，最后没绕出去，然后换题了）
两个倒序数组找最第k大的（框架差不多，最后发现漏了一种情况，感觉还在想洗牌的事情）

因为二面代码花了很久，最后没写完，当时心态有点崩，但给了三面

三面
三面没有写代码，问了一个小时，面试官全程半启发半追问，感觉有点懵，我把上下文相关的问题空格分段了

C/C++内存问题有哪些，尽量说
free和delete在具体实现上的差异
free之后的指针使用有什么问题
缓冲区溢出如何避免，有哪些场景
如何检查/处理越界
野指针和悬空指针分别是什么
试图使用野指针有什么问题
内存上还有别的问题吗？

C++11用过什么特性

之前讲的内存问题有什么好的方法吗？
智能指针讲一下
shared_ptr讲一下，怎么实现的，unique_ptr呢？
是不是所有要用指针的地方都应该用智能指针，有什么问题和不足？（我答了两次寻址和额外空间）
这些缺陷，在不用shared_ptr的前提下有减少成本的策略吗？（跳过了）

include，头文件里面一般放了些什么
声明和实现要写在一起吗？是不是一定要分开写？
写在一起和分开对最后的代码有什么影响，怎么确认（这个我不会，面试官让我试着分析一下，结合include的行为来谈）
gdb怎么查看一个函数的地址？
你在Linux使用经常哪些指令
如何探查CPU负载情况
在什么时候CPU被认为是繁忙/空闲的？

看过哪些比较大的代码？（后面很多问题是从这来的）

服务器：
多线程服务器和nginx在工作方式有什么不一样的地方
nginx怎么处理请求
进程唤醒（惊群问题）的额外成本主要在哪？
nginx的负载均衡（我只答了那个worker的负载均衡）
为什么它要用多进程，优势在哪，劣势在哪
多线程怎么应付同样的问题，能够解决吗，讲一讲方案
你的方案有什么问题？

http了解多少？
http缓存机制了解吗？
长连接讲一下
如何实现长连接（保活）
带外数据如何使用？
你的这个方法有什么问题，可以直接兼容不同的浏览器吗？
了解nginx的解决方案吗？

redis
你对redis怎么理解的？
redis的总体结构
单线程的优势和缺点
redis的事件分发
讲一讲文件事件有哪些
client功能是怎么实现的
时间事件（serverCron函数）
serverCron做了什么
redis所有事情都只有一个单线程吗？
bgsave讲一下，为什么要fork一个进程来做

interrupt与signal有什么差别
interrupt的发起和接受者是谁
操作系统在interrupt中发挥了什么作用
signal呢，发起者又是谁，接收者呢？（这里答得有点混乱）

TCP
ack什么时候发送，丢失了会怎么样？
sack了解吗？
重传ack的时机只有ack超时吗？
重复报文被接收会发生什么？
拥塞窗口要不要把自己的大小发给接收方，意义何在？（这个问题一面也问了，没有答出来）
延迟ACK的意义在哪？
为什么不能每次都直接发大的窗口？

进程地址空间布局讲一下
BSS为什么要叫这个名字？（后来查了，block started by symbol）
static关键字有什么作用，如果用来修饰函数呢？
多个线程使用static数据会开启多个副本吗？

C++OO
多重继承怎么实现
虚拟继承怎么实现
对于函数寻址在时间成本上有什么差异？
对于继承体系很复杂的情况这个成本会被拉高吗？