美团线上笔试经验分享：选择题与编程题详解及面试惊喜

笔试

美团的笔试属于线上笔试，它被分成了选择题和编程题这两部分。其中，选择题和之前在网上看到的题目有很多是相同的。编程题有 3 道，分别是：

求一个二维矩阵的最大横竖撇三个方向上的最大值。这道题较为简单，通过穷举的方法即可解决。然而，我因为忘记了较多的 C++知识，导致程序在调试过程中出现了问题，令人忧伤。之后在考完试后才发现，原来是输入参数不兼容所导致的问题。

我的实现代码

求两个字符串的编辑距离，这是一个较为常规的动态规划问题，它比较简单，很容易就能做出来。

我的实现代码

第三题是关于 K-means 聚类的。因为把时间都花费在第一题调 bug 上了，所以没有做这道题。

面试

笔试编程题目仅做出一题。原本以为无法进入面试环节。然而，在周一上班时，竟然接到了面试通知电话。这让人感到比较惊喜。

时间：2015.10.16

地点：厦门港湾大酒店

一面

自我介绍开始是一面的一个环节，接着会问一些具体的问题，具体的我记不清了。其中有让在现场写代码的，我被要求写的是一个 cache 替换策略的代码，这个代码是经过简化的。写好代码后，我与面试官进行了沟通，基本上没有什么问题。

面试官提出的第二个问题是：在二维坐标中有 n 个点，分别为(x1,y1)、(x2,y2)、…、(xn,yn)，需要在二维坐标中找出一个点，使得该点到这些点的距离最近。当时不知道是因为太紧张还是其他原因，竟然没有立刻想到答案，接着罗列公式并求导，之后发现坐标点就是 1/n(x1+x2+…+xn)、1/n(y1+y2+…+yn)，从直观上也容易理解。

面试官把题目改成了一维坐标上有 N 个点，分别是 x1、x2 等等一直到 xn 。要在一维坐标上找出一个点，让这个点到各个点的距离之和是最小的。从直观上看，应该去找这 n 个点的中位数。（首先得证明我们要找的这个点可以在这 n 个点里面，这个证明比较简单，就是在两个点之间的点到其他点的距离之和是相同的，这样就证明完了。）

一面也到了，出去外面等消息。

二面

二面的面试官显然并非从事数据挖掘工作，他向我询问了一些关于计算机网络以及系统的相关问题。我向他反馈称，自本科之后，我就没有过多地接触过这方面的知识。

主要问题想起来了有几个吧

hash 表的数据结构，经过长时间的沟通才得知他所询问的是 hash 表发生冲突之后的链式表处理事宜。

2、cpu的几个替换策略。

现场写代码：涉及两个字符串的距离（笔试曾考过编辑距离）。这里要求求出两个字符串的“与”以及两个字符串的“或”的比值。即在所有两个字符串的字符当中，都出现的字符占所有字符的比例问题，此问题较为简单。写完代码后，面试官指出了一些可以优化的地方。

实习期间做了几个项目，面试官对此完全不了解，主要看自己的扯皮能力。

其它七七八八的问题忘了。

三面（终面）

三面的情况最为尴尬。别人的三面都已经开始聊起人生了，而我的三面却在问我技术性问题，还纠结我论文中的几个问题。

问了一个概率性的问题：

一副扑克牌有 54 张，从中抽出 7 张。我们定义有 5 张连续的牌为顺子，那么要计算能抽到顺子的概率。

在面试官的提醒下（顺子的几种情况），我得出答案为：

9*4^5*C49取2 /C54 取7

面试官没有说对不对。（计算上有重复，应该是错误的）

面试结束后回到宿舍，发现了一个新的解法。这个解法是分别对顺子长度为 5、6、7 的情况进行考虑。这样的答案比较容易让人理解。

最后问了下我哪里人，是否考虑在北京发展？

研究生期间最得意一件事情是什么？？

还有什么问题要问的吗？

每个面试官都会问这个问题。我通常会询问他们目前团队的规模情况，以及是否有进行培训等事宜。同时，我也不清楚他们是否做了相关登记。

（一周后，通知结果，知道自己肯定没戏，主要是三面出现了。）

面试总结需要提前做好准备。除了复习专业知识之外，像自我介绍、询问自己的优点、缺点、最成功的事情等这些非专业性问题，都得事先进行整理。要端正好面试的态度，因为总会碰到不会的问题。每一次面试，都应该让自己有所成长。