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。各种排序算法还得看的更细一点。操作系统方面的知识得好好看看了,以为机器学习岗基本不问这些的。另外,居然基本没问机器学习相关的问题。项目方面,我刚说了本科做的智能车竞赛,就没让我继续说项目了。感觉面得很一般,能不能过看运气了。
作者:Henry2017
本文来源于牛客网
——————————
牛客网(www.nowcoder.com)
- 互联网名企笔试真题
- 校招求职笔经&面经
- 程序员求职实习信息
- 程序员学习交流社区
网友评论