美团点评2019届机器学习/数据挖掘算法实习生一面

Altieri

3.14网申的（北京，基础研发平台），3.22笔试。二十多天没消息，然后今天（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：（一个月前算法课上刚学，课下还实现了一下Prim算法）有两种，一种是Prim，另一种不太会读，好像是Krus...
Q：Kruskal，你说一下这个算法的具体过程吧。
A：最小生成树的背景是从一个无向图里找到一条路径将所有节点都连起来，这里每条边都是带权重的，要找的路径是权重最小的那条。（现在想想用路径这个词不太合适）然后先将所有边按权重从小到大排序，从小的开始找起，每次需要判断一下这条边有没有效。我说一下怎样是无效吧，就是这条边加进去之后没有将新的节点连起来或没有将两颗树连起来，就是如果这条边的两个节点已经被连起来了，这条边就是无效的。
Q：那怎么判断两个节点有没有连起来呢？
A：用一个unordered_set存每一棵树，这里不需要排序，所以不需要用set。如果这条边的两个节点同时存在于任何一个集合中，就是已经被连起来了。
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。各种排序算法还得看的更细一点。操作系统方面的知识得好好看看了，以为机器学习岗基本不问这些的。另外，居然基本没问机器学习相关的问题。项目方面，我刚说了本科做的智能车竞赛，就没让我继续说项目了。感觉面得很一般，能不能过看运气了。
（这么多人光收藏不点赞的）

转载自：https://www.nowcoder.com/discuss/73783