头条后端开发提前批技术面小结(已拿意向性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的效率也真的好高,面试结束第二天就有消息了,也是辛苦了😄
最后还是祝愿大家秋招顺利,毕业顺利,都拿到心仪的offer,开启新的旅程~

----------------------------分割线-----------------------------
有筒子问钟表那题的两种做法,这里简单更一下:
首先 n 一定为偶数,奇数直接输出零;
1. 数学解法:
首先考虑没有绕圈的情况,则问题变为从 n 步中选出 n/2 步顺时针移动,剩下的自然确定为逆时针移动,则情况数为
接下来考虑顺时针绕一圈的情况,则顺时针步数变为 n/2 + 6,逆时针变为 n/2 - 6,则情况数为 ,逆时针同理,乘二即可;
绕 m 圈就是 n/2 + 6*m,所以最终答案是 ,当然绕圈的圈数不能超过 n/12 ;
2. 动态规划解法:
定义 dp 矩阵 dp[n+1][12],dp[i][j] 代表 i 步走到 j 位置的情况总数;
首先不考虑边界情况,则 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1],也就是说,i 步停在 j 位置处当且仅当 i-1 步停在 j-1 或 j+1 处,则情况数为两者之和;
然后我们考虑在0时刻或11时刻如何处理:我们发现这两个时刻在表盘上没有任何特殊,i 步停在 0 位置处当且仅当 i-1 步停在 11 或 1 处,i 步停在 11 位置处当且仅当 i-1 步停在 10 或 0 处,则我们只需要将每一行都处理为循环数组,让 0 列与 11 列相邻即可;
最终递推关系:dp[i][j] = dp[i-1][(j>0?j-1:j+11)] + dp[i-1][(j<11?j+1:j-11)],初始条件为 dp[0][0] = 1,dp[0][j] = 0 ( j 不为0),最终结果为 dp[n][0] 处的值;
空间复杂度优化的话,观察到每次更新只需要上一步的数值,且矩阵每行都只有一半的元素不为零(受制于步数奇偶性),可以进一步将 dp 矩阵压缩为常数空间,dp[12] 就够了~
代码已在评论区更新~

另外 LRU 的题,有一个重要要求,要求 put 和 get 操作的时间复杂度均为 O(1),已在内容中更新;

其他问题也欢迎大家留言讨论~
祝好~


#字节跳动##面经##校招##C++工程师#
全部评论
点赞 回复 分享
发布于 2019-08-04 23:45
老哥稳嗷😎
点赞 回复 分享
发布于 2019-08-04 23:55
能不能分享一下从0刻出发那道题的解法
点赞 回复 分享
发布于 2019-08-05 01:21
表盘那道能否说下两种解法,并解释一下,没思路呀,大佬
点赞 回复 分享
发布于 2019-08-05 10:35
恭喜恭喜
点赞 回复 分享
发布于 2019-08-05 11:59
表盘问题已更~
点赞 回复 分享
发布于 2019-08-05 12:59
public int question1(int n){ return helper(0, n); } private int helper(int position, int remain){ if (position == 0){ return 1; } if (remain == 0){ return 0; } int nextRight = (position + 1) >= 12 ? (position + 1) % 12 : (position + 1); int nextLeft = (position - 1) < 0 ? (position - 1) +12 : (position - 1); return helper(nextRight, remain - 1) + helper(nextLeft, remain - 1); }
点赞 回复 分享
发布于 2019-08-05 14:57
int clockPath(int n) {     if (n & 1) return 0;     int dp[n+1][12];     dp[0][0] = 1;     for (int j = 1; j < 12; j ++ ) dp[0][j] = 0;     for (int i = 1; i <= n; i ++ ) {         for (int j = 0; j < 12; j ++ )             dp[i][j] = dp[i-1][(j==0?11:j-1)] + dp[i-1][(j==11?0:j+1)];     }     return dp[n][0]; } 这个是比较直接的动态规划解法,空间复杂度较大
点赞 回复 分享
发布于 2019-08-05 16:32
int clockPath(int n) {     if (n & 1) return 0;     int dp[12] = {0};     dp[0] = 1;     for (int i = 1; i <= n; i ++ ) {         if (i & 1) {             for (int j = 1; j < 12; j += 2 )                 dp[j] = dp[j-1] + dp[(j==11?0:j+1)];         }         else {             for (int j = 0; j < 12; j += 2 )                 dp[j] = dp[(j==0?11:j-1)] + dp[j+1];         }     }     return dp[0]; } 这个是改进后的动态规划算法,空间复杂度降为O(1),需要稍微想一下,其实就是利用奇偶性错位更新
点赞 回复 分享
发布于 2019-08-05 16:34
楼主请问那道概率题是咋做的哇🤣没思路....求教 一道概率题:在一个圆上任取三个点,每个点在圆上服从均匀分布,点与点间相互独立,问三个点围成锐角三角形的概率:
点赞 回复 分享
发布于 2019-08-09 14:49

相关推荐

在努力的外卷侠很靠谱:怎么,大家都没保底吗?我这美团已经入职了,不说了,系统派单了。
点赞 评论 收藏
分享
牛客279957775号:铁暗恋
点赞 评论 收藏
分享
牛客868257804号:九个中铁八个中建
点赞 评论 收藏
分享
15 103 评论
分享
牛客网
牛客企业服务