滴滴面经一二三面9.26求offer

滴滴后端面经9.26

同学内推，笔试有前端的题,不懂，就做了选择交卷了。9.25下午约9.26面试

一面：和蔼胖老哥

问：先自我介绍一下

答：xx大学，本科生，大四，一直在实验室搬砖（科研，没有太多后端经验，秋招想找个后端工作（放弃梦想）

看简历，问：我看你简历写了个STL库，实现了B+树，数据库懂吗，这是innoDB的后端实现，给我讲一下B树和B+树

答：讲b+树先要讲b树，思想和二叉搜索树类似，二叉树二路搜索，i/o较高，b树又叫m路多路平衡搜索树···，是为了多级储存设计balabala，讲了一下搜索、插入删除，上下溢，节点既存key也寸value，调整消耗大，不适合顺序遍历。b+树解决顺序搜索问题，数据链式维护在硬盘，仅把key提出来做索引，类似B树，key定位到有指针指向物理位置，遍历即可。特点1.非叶节点仅存key，小，好维护，2.没个节点大小设置为扇区大小，查找下一节点顺序遍历，不用寻道了，快。另外数据库一点不会不会。

问：那节点设置成多大好呢？

答：一般设置成扇区大小啊，扇区硬盘厂商设定的。

问：那我换个问法，现在一块HDD7200转，寻道时间2ms，寻址时间4ms，问块大小设置成多少，最大qps最大能到多少？

我：蒙了。算，嗯？寻址时间给我来我还算啥？没搞懂。 iops=巡道+旋转+寻址=2+60*1000/7200/2（平均转半个盘定位）+4。qps=1000/iops

问：嗯，平均查找是半圈，之前你说到块，块大小设置成多少呢？

答：一般都是4kB对齐，咦？为什么是4KB？哦我知道了，是最小换页单位，内存frame大小。

问：嗯，不错，页大小4kB，你写过类unix系统啊，看你写的熟练掌握并发编程，讲一下进程调度

答：cpu，中断，陷入，换页，tack_struct切换，PCB内容，内核态用户态切换bala

问：死锁产生条件

答：非抢占、互斥、占有并等待，第四个有点紧张想不起来

问：我们学的时候是循环等待

我：对对对

问：进程调度讲完了，讲讲你知道的内存调度策略

我：FIFO、LLU、LRU

问：设计一个LRU，写一下代码

我：LeetCode146，秒了

问：进程通行方式

我：五大件 管道、共享内存、消息队列，信号量，每个特性讲一下（第五个想不起来，是FIFO文件访问。。。因为没用过也没记过）

问：网络三次握手

我：画并讲

问：第二次确认啥用，没有造成啥后果？

我:防过期请求SYN，服务器连接资源浪费耗尽

问：要是第二步也没了呢？

我：服务器资源浪费耗尽，客户端也是

问：哈哈，那就是个UDP

我：恍然大悟（憨憨

问：考考算法吧，出个简单的题，一栋楼10层，每层有钻石，你坐电梯，只能上，只能拿一次，你用什么策略？

我：铁憨憨??，概率论期望最大策略拿第五层第六层，因为我啥也不知道，大自然会让钻石成正态分布

问：想办法找个量化策略

我：先走五层不拿（暗中观察），记下平均值，后面大于平均我就拿。（真的有钻石我就奥卡姆剃刀，第一层拿了就跑）回来发现是微软面试题，开放题，考数学直觉的，也是暗中观察策略http://blog.sina.com.cn/s/blog_4c2e67c50100gdcc.html

看了看笔试

指着一道二叉树后序遍历选择问：你这个题做错了啊？

我：不想做，随便点的，纸上写了一下后序遍历非递归

翻到笔试，果然一题没交

指着第二题（求连续的最小长度为m的数组和的最小值），我们做个题吧，这个太麻烦，我们做个简单的，写个快排吧

我：写，

问：有什么想问我？

我：滴滴刚来实习的话是做新新项目还是重构旧项目？技术栈不匹配有安排时间学吗？我没啥后端经验

答：bala

感觉一面面试官问的很不错，理论重结合实际，光背书可能听不懂问的啥。还好我是个PCDIY玩家（卡吧基佬），运气不错的。

等了一会，二面

面试官双眼皮，剑眉，冷面 吓得我瑟瑟发抖

问：我是xxx，xx部门xxx，自我介绍一下吧

我：自我介绍*2

问：讲一下你实习的实验室经历

答：Faster-RCNN、DCP、MASK-RCNN，Inpainting，SuperResolution,前向反向传播，梯度下降算法大概描述了一下。

问：听起来做的不错，你为什么不读研呢？

答：菜，么得研读，考不动，保不上，出国GRE来不及bala，国内读完研我就算读清华最好不过也是来互联网做后端算法不是吗？（其实我还在考GRE，找个工作保底先

问：嗯，你这个跟我领域差的很大，不好问，数据库会吗

答：不会，一点也不会（逃，上回面头条说会，给自己挖坑gg，不会就说不会吧

问：我看你写了个STL库，那你讲讲你这个接触到最难的点和启发

答：allocator，二级空间配置器，内存池减少碎片，颠覆我开发观念、STL开发诸君真乃神人也，源码阅读体验：精彩！，开发过程：学到很多，以前只会用，现在终于懂了，泛型、继承、数据结构复习、架构设计，确实很不错balabala，画了两张草稿纸

问：你怎么觉得颠覆开发观念了呢？计算机科班应该觉得很正常吧？

我：一直在写lab-code，第一次看大型开源源码，很多东西只书上看过，没做过，觉得震惊

问：你这个hbase项目，java写的吧？怎么就用上hbase了？

我：学校安排的大数据实训，你要是问我java我就凉了（***）不会

问：学校实训啊（会心一笑）我不问你hbase，我看你写了个linux操作系统，讲一下进程调度

我：进程调度*2

问：https知道吗？

我：不知道，只会HTTP，但我知道是会话用SSL加密，

问：UDP怎么交付

我：画出UDP报文头，画出ip豹纹头，ip传到主机，再根据udp里的端口号传到对应端口

问：TCP和UDP区别

我：TCP面向连接，UDP尽力交付bala

问：TCP怎么保证交付

我：滑动窗口，连续确认，画了个只有 1234 789的接收窗口，server的ack=5，client重新传56789···

问：TCP拥塞控制

我：慢开始、拥塞避免 窗口、ssthresh

问：写个算法吧

出了个最大连续子序列

我：dp，秒了

面试官看不懂，我一行一行给他看

问：我没什么可以问你了（沉浸在dp方程中，还没悟出来）

？？？反问环节呢？

三面：前面的老哥跑了，HR让我顶替，上了个厕所，五分钟继续面

面试官高冷至极，说话没有语调，不敢造次

问：自我介绍一下

我：自我介绍，强调没后端经验，c++

问：你觉得技术哪一部分不错

我：数据结构和操作系统和c++

问：我看你实现了线程安全的hbase读写接口，说一下怎么实现的？

我：讲一下线程怎么不安全，线程和进程的关系，画了个kernel内存分布 高地址内核、入口、栈，堆，静态存储区、常量存储区、代码段，PCB内容、线程共享进程内容，线程调度阻塞模式、上下文切换机制，内存申请系统调用，然后讲线程多了stack会爆掉，再多线程开不起来，或者把旧线程down掉（stack爆），我们搞一个线程池，加锁，控制连接上限，减少线程上下文切换损失。

问：和我理解的线程安全不一样，你这个是控制并发数量

我：嗯

问：文件描述符讲一下

答：一个整数，inode的结构讲了一下，目录文件、无名文件讲了一下，文件描述符即是引用向inode的值

问：怎么实现两个进程同时访问文件描述符？

答：进程通通信吗？可以共享内存mmap可以实现，讲了一下映射共享内存结构，另外还有shm，我不太熟，亲缘进程可以用管道，也可以socket 访问

问：现在要进程b和a访问同一个文件描述符，传什么参数？怎么传？

我：？不是共享内存了吗？mmap，shm还传啥参数啊？

问：比如a 访问一个文件描述符，读到pos位置，怎么传给b，你刚刚说过进程通信方式了，比如用信号量，现在我就问你要传什么参数？

我：信号量也可以传文件描述符？

问。。。

我：那传一个文件描述符、一个pos不就行了（这里楼猪不太懂，求指点

问：真的吗？

我：嗯（大无畏不怕死乐观***gm精神

看简历

问：自旋锁和普通锁有什么区别

我：自旋锁 写了个自旋锁伪代码，在死循环里不断试探锁位，占用处理机，发现锁被占用后不断读取，处于忙占用状态，不会挂起进入阻塞队列，如果是单核主机，没有其他核上面的线程给他释放锁，就死机了。

普通锁分互斥锁和条件变量，锁被占用时，立刻被挂起，task_struct内容修改，寄存器保护，保存打开的文件描述符，进程被换出内存，等待系统进程发现对应锁释放后再wake，换入内存。

问：自旋锁这种设计有用吗？占用cpu，为什么呢？

想了一会，想起来自旋锁设计初衷 我：缺页中断讲一下，讲进程挂起，保存状态，换出内存再唤醒、换入的上下文开销很高，如果进程很重要，或者进程挂起唤醒一次时间很长，比如每次把内存换完，就不值得挂起，不如空转处理机，使用自旋锁，避免上下文切换。

问：嗯，你还会其他编程语言吗？

我：python懂一点，会用，没有深入了解过，java也差不多

问：没有深入了解，嗯，你知道现在c++开发用的很少，只有腾讯或者一些在用了，这里一般都是php、golang，你了解过吗？

我：听说和c++很相似，熟悉c++很好转，我就是没有后端经验，想靠c++转才投的

问：嗯，c++多态讲一下

我：多态由静态联编和动态联编实现，静态联编是编译时确定，动态联编是运行时确定，静态主要靠重载实现，动态靠虚函数

问：虚函数怎么实现的？

我：有继承特性才能用虚函数，所以是类实现，含虚函数的类对象内存第一个单元会内置一个虚函数指针，占一个指针的内存单位，派生类定义与基类同名函数就会自动成为虚函数，类会在只读数据段生成一张虚函数表，对应各类实际实现的虚函数，用基类指针和引用调用派生类虚函数，vptr会去vtable找派生类真实实现虚函数。

问：含虚函数的类

class A{
virtual fun();
int a;
short b;
long c;
}

各部分偏移地址

我：内存对齐吗？vptr 0-7，其余和最长的vptr对齐a 8-15,b16-23,c24-32（这里楼猪看书不仔细，答错了，泪目了 应该是和内存偏移对齐

class A{
virtual fun(); //有虚函数，所以对象有一个  vptr 0-7
int a;//8是size（a）4的倍数，所以占用内存偏移a 8-11
short b;//12是sizeof（b）2的倍数,所以占用内存偏移 12-13
long c;//14不是 sizeof(c) 8的倍数，所以不占用内存偏移 改用15-24
}

问：这个你回去多看看吧

我：哦，我可能记错了

问：最后我们来写道算法吧 一个数组，只有一个数出现1次，其他都出现三次，求这个数

我：hash散列，求得没碰撞的数，o（n）

问：还可以再优化一下

我：桶，找只有一个的 O（n）

问：有别的思路吗？还可以优化

我：只能o（n），怎么都得遍历一边，想不出来啊

问：肯定要遍历一遍，可以从空间上优化

我：呜呜呜～有提示吗（这个题我见过，好像是相邻做位运算的，上一题答错了，太紧张忘了）

问：可以考虑位运算

我：2分钟过去，没有思路

问：好了，我的问题问完了，你有什么要问我的吗？

我：滴滴后端都是什么技术栈？我去实习应该就是学新技术栈了吧？

问：嗯，一般都是php和golang，不粗意外是转，至于分到哪个组不一定

我：刚刚内存布局我哪错了？

问：面试题我不会回答，这个要你自己回去研究

我：好的，没有问题了

问：嗯，你基础不错，有些地方还可以提升

我：谢谢

问：点头致意

hr一会出来，说回去等消息，我悄悄问hr回去等消息是有消息还是没消息啊？hr说我也不知道。

应该是比较真实的面经了，真情实景，大家提提意见，另外也给怕面试的老哥看看我的铁憨憨面试风格

另外求offer，手里只有一些实习和工资低的弟弟厂，想进独角兽🦄️