头条后端开发提前批技术面小结（已拿意向性offer）

其实7.24就收到了头条HR意向性offer的邮件，不过比较懒就拖到了现在才写😑 最近有少量筒子问我面了啥，索性简单写一下以免重复造轮子。。（写完又要摊10分钟）也算回馈在牛客上刷面经得到的前辈们的帮助～

7.18 一面
面试官一位年龄相仿的小哥，很认真也很nice吧，很快进入状态。简单问了下实习经历，然后撕了两道代码：
1. 给一组日志文件，包含用户id，登陆时间，登出时间，假定时间范围一天之内，求出一天之内在线用户数量的峰值，并给出时间区间（多个相等区间都输出，可以假设登录登出时间为整数）：
最开始想用pair存登陆登出时间，想排序如何排的时候一拍脑壳我管你是张三李四干什么，直接把登陆时间和登出时间分别当做两个向量分别排序，然后从小到大扫描，类似归并排序的merge操作，先判断下一次操作登陆在前还是登出在前，登陆加一登出减一，得到当前时刻的在线人数，至于怎么得到最大值，怎么存储时间区间，诸君随意，方便就好～
2. 给一个01矩阵，计算1被0分割成了几块（参考围棋规则，上下左右相邻算作一块，否则为不同块）：
简单的深度优先搜索，回溯算法5分钟搞定～
接着又问了点基础知识，地址栏输入地址后发生了什么，HTTP状态码，tcp ip连接过程，进程线程区别这些，具体的记不清了，我基本都答了个表面，课没学过的确说不深入，直接跟面试官承认这些课都只懂基础深了不会，节约时间😅

7.18 二面
一面结束已经5点，本来准备回去了，小哥让我等一下，不到20分钟新的面试官来了（后来才知道是内推我的师兄的leader，也是幸运），又聊了一下实习经历，问了句听说你基础一般，我说是，相对来说数据结构和数学好点，于是就再没问基础知识（我服了。。）
手撕代码：
1. 给一个json对象，可能是list也可能是dict，dict的所有key值都是string，写一个函数，将原本驼峰命名的key值处理为全部小写以下划线分隔的新的string，list成员和value成员都不作处理，输出新的对象：
用python写的，忘了type.__name__()方法，用try except实现的，递归调用就可以，不过代码兼容性应该很差。。
然后是讲算法不用撕了：
2. 在一个表盘上，从0时刻出发，一次移动一格，顺时针逆时针均可，n步回到0时刻，问有多少种不同的路径：
这题我第一时间给出了排列组合解法的正确答案（数竞坑人不浅啊。。），但面试官表示不太明白，也不是个数学题能不能写个代码实现的算法，开始想动态规划解法。虽然我明知这题就是找递推关系，但是陷入“绕圈需要分类讨论”这个误区的我一直在想边界条件怎么处理，将近10分钟后想出正确答案的我心态崩了😶
3. 一道概率题：在一个圆上任取三个点，每个点在圆上服从均匀分布，点与点间相互独立，问三个点围成锐角三角形的概率：
答案1/4，可能与感觉违背，积分求一下即可，注意积半圆不要积整圆，整圆可能会积成优弧而不是劣弧～
4. 用简单数据结构实现一个符合LRU算法的缓存队列（要求 put 和 get 操作的时间复杂度均为 O(1) ）：
两个map加一个链表即可，一个map存key和value，一个map存key和链表指针，链表存LRU队列，get() 的时候利用存指针的map更新链表队列，put() 简单实现就可以。这个题问的时候脑子已经累了，答出了框架但细节没描述清楚，不过细节其实挺简单的～有更好的方法还请不吝赐教😃

7.23 三面
前两面其实挺随意的，没想太多因为觉得过不了，三面有点紧张了。面试官是个非常非常骨感的先生，见到比我瘦那么多的人我真是惊了😂 上来还是简单聊了下实习，问了下收获什么的，然后也是没问基础直接提问：
1. 64位操作系统下，实现一个链接式的hash map，保存n组(key, value) 对，假设key, value各占8字节，问一共需要占多少字节：
64位操作系统，指针8字节，假设hash函数有m个值，则8*m + (8+8+8)*n = 8m + 24n，似乎是这样，有不对的地方希望大家指正～
2. 手撕代码：服务器访问限制：实现一个bool visit(int ip) {} 函数，对任意一个ip的访问请求，限制一小时内请求总次数不超过50万，超出则返回false，要求请求总次数是按秒更新的，类似于实现一个秒单位的滑动窗口，判断最近的3600秒是否请求超限：
这个我撕了很久，想不出好的办法，最后给每个ip都开了3600长度的int数组，用map存ip和数组指针，再在访问时更新ip的数组，效率不高。这个代码写起来很长很复杂，大家可以简单试试。
最后面试官问我如果分布式服务器完成这个工作，不同步数据的情况下如何实现这个功能？我回答的还是构造一个hash函数对ip进行分配，固定访问特定的一台服务器，应该有好的多的办法不过不了解，欢迎指教～

总结来说头条开发岗还是非常注重coding的，代码速度和质量是第一位的，要求15～20分钟完成就要完成，面试官到时间就会看你的进度，写不出来或者写不完就很僵硬，题都不算难但是好的算法和快速的实现会比较有压力，不过面试官都非常nice，你有思路的情况下会愿意和你交流，很有耐心，所以不懂就问，卡住了就和面试官聊天，寻求提示和方向，这样要比干坐着大脑放空好的多😂 另外头条HR的效率也真的好高，面试结束第二天就有消息了，也是辛苦了😄
#字节跳动##面经##校招##C++工程师#