美团点评2019届机器学习/数据挖掘算法实习生一面
3.14网申的（北京，基础研究部门），3.20笔试。二十多天没消息，然后今天（4.12）下午接到美团面试电话，当然是前两天约好的，面试官大概迟到了十多分钟。
Q：介绍一下做过的项目
A：balabala...
Q：一千万个整数，每个数的范围在[-1000,1000]，怎样对他们排序最快？
A：计数排序
Q：复杂度呢？
A：O（N）
Q：如果不是整数呢？是浮点数怎么办？数的个数再增加到10亿个呢？
A：...说了一堆没用的
Q：我给点提示吧，这其实不是一道纯算法题，是一道设计与算法结合的题
A：要最快的话，用分布式吧
Q：细节呢？怎么分配任务？
A：平均分给N台机器快速排序，再归并排序每台机器的结果
Q：至少需要多少台机器能得到较好的性能呢？总不能有一亿台机器，然后全用上吧？
A：（没说到点上）在数的个数小于30时，快速排序的性能比归并排序慢大概10%
Q：为什么用快排排序，而不是归并排序或堆排序呢？
A：实践证明快速排序的平均效率最高
Q：能证明一下快排比归并排序快吗？
A：orz
Q：你考虑过数的个数在哪个范围内用哪个排序最好吗？能证明吗？
A：没...
Q：说一下堆排序的过程
A：balabala
Q：建堆的复杂度是多少？
A：O（N）
Q：能证明吗？
A：orz
Q：你简历里说你看过STL源码？看过里面的sort()函数怎么实现的吗？
A：这个没看过，主要看的顺序容器的那部分
Q：那set怎么实现的
A：set是关系容器，我看的是顺序容器部分。set是排序了的，应该是用红黑树实现的。
Q：你简历上写你LeetCode全球排名前10%，你总共写了多少题?
A：一百八、九十吧
Q：这么点能前百分之十吗？因为我也在其他平台写题，LeetCode没怎么用过，你能发一下你的id我看看你的页面吗？
A：这个排名不是写题的数量排名，是每周的比赛的积分排名。
Q：等下挂了电话你把你页面的链接发到我邮箱里。问点操作系统方面的吧，死锁的条件有哪些？
A：balabala
Q：银行家算法知道吗？
A：以前看过，现在基本不记得了。
Q：进程间通信知道吗？
A：不知道
Q：你的项目里没用到进程间通信吗？
A：没
Q：你会Python吗？用的多吗？
A：大四的时候用得比较多，毕业设计里用Python调用sk-learn的库以及显示结果。另外，当时在《机器学习实战》这本书，里面的代码都是Python实现的。
Q：Python多线程会吗？
A：没用过
Q：操作系统内存管理知道吗？
A：不会（思考了几秒，还是说了不会。我本科不是计算机的，根本没学过操作系统好吗？虽然零碎地看过一些，已哭瞎，看来之后还是要准备一下这些）
Q：下面我给你邮箱发个链接，你看一下，大概给你半个小时写出来。
A：好。
题目在邮件里，英文描述的一道题，大意是：一个0~1e18范围内的整数，可以交换k（0<=k<=100）次，每次只能交换相邻位置的数字。问能得到的最大数字是多少？
然后给了 collabedit.com网站上一个白板，让在这里实现。
和面试官讨论了一下思路，先说的是广度优先搜索，不过k最大100，每次有最多17种交换情况，复杂度爆炸，虽然有一些剪枝方法。肯定有贪心的方法，大概说一下思路吧，优先让高位的数字尽可能大，记录一个当前要处理的位置start，就是在k步范围内找是否有比这个数大的数，找到的话，就从这个位置依次和前一个数交换，直到start这个数，然后k减去交换的次数，start++；没找到的话，直接start++；当k==0或start==n（n是位数）时结束循环。
给面试官说这个网站很难用，总提示我刷新，当前行有重影，有时候无法输入等问题，面试官让我用IDE实现，然后把代码发邮件给他，然后挂了电话。
大概写了十几分钟，测试了一下也没问题，就发过去了。
然后又发邮件给面试官LeetCode上的个人页面了，然后附带解释了下前几天刚获得蓝桥杯省赛一等奖和排名，并进入决赛。（面试官看的简历还是一个月前的）
二十分钟后，面试官电话过来说代码他看了。
Q：你现在研几？哪年毕业？可实习时间？
A：balabala
Q：你有什么问题问我吗？
A：美团一共有几面？
Q：实习生是一共两面，还有什么问题吗？
A：美团主要将机器学习用在哪些方面？
Q：很多方面啦，比如机器人、对话系统、推荐、调度、无人车....
A：没什么问题了，就这样吧
Q：接下来等hr联系你就好，拜拜
总结：美团很看重基础，各种让证明orz。各种排序算法还得看的更细一点。操作系统方面的知识得好好看看了，以为机器学习岗基本不问这些的。另外，居然基本没问机器学习相关的问题。项目方面，我刚说了本科做的智能车竞赛，就没让我继续说项目了。感觉面得很一般，能不能过看运气了。