2019秋招头条大数据/数据挖掘面经

第一次发面经，好紧张，历经20+天，get头条意向书啦。过后补上美团面经～

一面 40min

• 【编程题】有两种数据，分别是被转发的用户和转发的用户，求原视频的用户以及转发的最长深度

  from：1，1，2，2，3，6
  to： 2，3，4，5，6，7
  面试官提示转换成树的结构，我写了求树的最大深度的函数，面试官说构造树比较复杂，差不多写这样可以。

• 【SQL题】有一张网页访问日志表，记录了user_id，session_id，page_id，timestamp

• 用户在每点击一个连接跳转，就会记录一个时间戳，并且page_id排序后与时间戳的排序一致，现要求每个用户的每个页面所停留的时间。
  比如：
  1 1 1 10:00
  1 1 3 12:00
  面试官看了后说差不多是这样，但要考虑一个边界的问题，最后一个page_id之类的 （请问这个怎么处理？

• HiveSQL底层是怎么实现的？比如两张表Join的时候会有哪些操作？需要shuffle这一步吗？

• mapReduce为什么需要Shuffle这一步

二面 40min

• TCP四次挥手过程中，time_wait字段的作用？
• 进程和线程的区别
• 有一个文件，每一行是一个数字，如何用 MapReduce 进行排序
• 【编程题】n=3 时的全排列
• 【编程题】二叉树的序列化和反序列化
• Hive 中的 Distribute by
• Partition By

三面 ～2h

三面的时候网真的好差，中间网络断了很多次，重新发起了4、5次视频面试，最后还是打电话了

• 【编程题】在一棵二叉排序树中，找到比给定数值小的最大节点。
• 【场景题】打车的场景下，poi记录了建筑物的坐标：poi(pid, x, y)，odr记录的是乘客上车点的坐标：odr(oid, x, y)；希望对所有的poi，获得其周围的100m的odr：结果(pid, oid)
  我开始用的是欧式距离的暴力求解，面试官让我提出优化的方案，我说可以计算出每个坐标点的geohash值，相等的值说明可以建立映射关系，面试官说geohash存在的一个问题是可能会出现两个相邻100m之内的点各自的geohash不同，这时怎么解决？
• 【SQL题】有两张表：文章分类表artical_cate（aid, cate）一个文章可能有多种类型; 用户阅读表user_read(uid, aid)，一个用户可能阅读多篇文章。
• 详细问了实习的项目，涉及到业务背景，有哪些特征，整体流程和方法，问到了基于现在这个版本我会怎么继续优化？

总结

编程基础仍然是关键，结合业务场景的问题更需要拓展思路，平时还要多独立思考。

三面由于一道题没做出来，面的不太好，回绝后隔了一段时间后捞我加面

加面 45min

• 自我介绍
• 介绍公司实习的项目，准确率和召回率怎么得到的，提升后达到了多少
• 二分类问题除了准确率和召回率还有什么别的指标？ROC曲线怎么绘制的
• 训练集效果很好，但在新的样本上效果不好是什么原因导致的？你用Xgboost训练时怎么解决这个问题
• 项目中运用MR任务来提高效率是怎么实现的？MapReduce的具体流程是怎么样的？
• 描述一下在count操作的MR过程
• 写一个SQL题，考察分组聚合、分区排序等
• 【编程题】给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
• 场景题：如何预测抖音明天的流量
• 开放题：如何估计一个湖里鱼的数量？你说的方法可能会出现什么问题
• 操作系统：32位操作系统的内存
• 数据结构：知道哪些排序算法？归并排序在任何适合空间复杂度都可以达到O(n)吗

五面 20min

聊天面，问能不能来提前实习，毕业论文，是否有别的offer，导师实验室是否自由等问题