美团网面试问题

美团网面试问题

2014年9月25日星期四，上午10点去参加面试;面试地点是一个大教室，你坐在工程师右边就行了;首先让你做一个简单的自我介绍，他顺便看一下简历，然后就步入主题了。

开门见山：(以下简称A工程师和B 我)

题目一：

A 你面试的是android?恩，下面问几个简单问题?

B 恩。

A android 里面的Intent 有什么作用?

B 用于Activity之间的跳转，还有数据传递。

A 恩。那么还有什么作用?

B (还是坦白吧!不要不懂装懂)其实android研究的不是很深，其实我用的最多的是算法?

A 志愿里面有一个算法工程师?为什么没选?

B 我以为要求很高，所以没敢填，所以写在了第二志愿!!!囧

A 好吧，那我就问一下的算法题，过了就把你转到算法工程师那里去二面!

B 好

A那你主要研究的算法有哪些?

B 我平时研究的是dp和博弈。

A 博弈?

B 恩，主要是：背包问题(01,完全，多重，二维费用等)，威佐夫博奕，nim游戏，SG定理以及取走分割游戏。

A 我们来看一个问题：n位的01串组成的集合S1(共个)，找出一个母串的所有同构串所组成集合S，S1属于S.

有点抽象，看个栗子：

比如 n=2 所有的01串有：00 01 10 110110 的所有2位的循环同构串有：01 11 10 00符合条件，不能找到更短的了，因为至少得有2个0和1.你分析一下如何找一个最短的母串!

B 然后想了一下，应该这个串长度最少应该>=2n，大约想了5min，感觉没什么思路!

A 你想一下，编程怎么解决?怎么找出这个串?

B 构造?

A 不是，你把n位的所有01串全部列出来，再去选!

B 暴力!

A 恩

B 我说：这样的话复杂度是()阶乘。

A 这个串肯定包含连续n个1和连续n个0的情况，可以去掉很多情况，复杂度可以降很多

B (无语，(!) 你这么点优化，无语)

A 下面，我们来讨论简单点的问题：

32位操作系统可识别的内存多大?

B 理论值是4G。

A 为什么是4G?

B 因为32位bit可编码的地址空间是2^32 ，所以是4G。

A 那么你简单说一下操作系统是如何分配内存的?

B 从开机开始?

A 恩

B 首先，计算机加电，cpu直接将cs+ip置为BIOS第一行代码的地址，读取BIOS代码…..直到启动桌面。

A 恩，那么下面说一下32位int如何每一段如何划分的?内存分页，最小的段是多少位?

B 好像是15位?

A 偏移位占几位?

B 2位吧!

A 好吧，那么 ….

B (坦白吧!直接打断他)这个我没怎么研究过!

A 下面我们还是来做几个题：

如何判断一个单链表有环?

B 想了一下，Hash判重，每次查询是O(1)效率是O(n)，如果访问过重复访问的点说明有环，如果为NULL，说明无环?

A 不错，那么辅助空间是多少?

B O(n)

A 可不可以不用辅助空间呢?或者只用O(1)的辅助空间

B 让我想想?

About 5min,.....

B 好像没什么想法，因为你都忘记了你自己走过的路!!好像不好搞耶!

/***后来google之(吐槽一下：自从前几个月google加密搜索字段之后，有关部门墙了，修改本地host文件就行了)，发现google才是学术帝，龟兔算法!!(亦称快慢指针)stackoverflow上有这样的问题!!还可以求环，效率O(n),突然发现优化无止境。

***/

A 恩，那么我们来看下一个题!

给你一个严格递增的序列，从中间某个未知的地方切成两段，将前一段放到后面，求最大值?注意划开的位置你不知道!

B O(n)的遍历可以，我觉得你是要更高效率的算法!

A 恩

B 在纸上简单画了画，大约两分钟thinking，发现可以二分搞!立马给面试官讲了思路!

A 恩，写代码实现一下。

B 下手就写，写完之后，发现L

A 面试官看了下，你的边界是不是有问题?

B (还真的看出来了!)想了1min，改成L+1

A 恩，不错。

A 判断一个二叉树是否关于根节点左右对称!

B 想了想，遍历树的方式，发现“左根右”==“右跟左”即可判断是否“手性对称”(这是高中在书上看到的一个词)。

A 如果一个做孩子为空，一个右孩子为NULL，那就不对了。

B 我说：加一个-1到遍历序列。

A (面试官，又在纸上画了画)~~~你这个方法可以，但是你得保存遍历序列，可不可以不要辅助空间?

B(好吧!原来优化了时间，再想空间优化，一般我只做前一个)想了想，遍历!

A 对!

B 哦，真的!(顿悟)递归实现，每次比较左右孩子即可!4种情况。

A 写一下代码。

B (好吧，习惯了!)下笔就开始，发现自己没写好，又自己重写了一次，大约花了7~8min，好了。

A 面试官看了看，行。

A 再看一个题：一个二叉树，层次遍历!写一下代码。如果你想记录下来一起输出也行。

B (搞的我好像很喜欢开数组似的，还有没有完!)BFS层次遍历就行。

。。。写完代码

A 你先到外面等一下!

B 恩。

大约5min，通知进去二面。

题目二：

A 做，先简单介绍一下!

B 恩我来自……(介绍完毕)

A 下面我们来讨论一下CS.

B 不好意思，没听太清CS是?

A Computer Science(不屑)

B 哦，计算机科学!(汗)

A 看了你的简历，平时都研究哪方面的算法?

B (又重复了一遍。。。)

A 我们先看一个问题：黑白棋盘，从左上角到右下角是否有路，只能访问上下左右4个位置，且为白色?问是否可达?

B (心中窃喜，BFS寻路，签到题)问：用不用记录步数?

A 不用!先看是否可达?

B 那就是BFS!

A 你写一下代码!

B 大约6min，写完!最坏的情况下，复杂度O(n*m)

A 他一行一行看了代码!好像没发现什么问题，说怎么没输出路径!!

B (晕!你不早说!)拿回代码，改之，开了一个标记数组，存储方向!到达终点，从终点回溯输出即可!

B 可不可以不回溯!你这多了一重循环!复杂度最多是(n*m+n+m)只是增加了O(n+m)，时间复杂度!总的时间复杂度根本没增加!!(真感觉，太没风度了，能不能找个心服口服的理由)!

A 不一样，能不能不开标记数组!能不能不要那重循环找路!

B 那就递归DFS，我写的是BFS!

A 能不能不用递归!

B 那就将递归DFS改成非递归DFS，那也得开数组记录状态啊!

A 能不能不开数组!

B 非递归，不开数组怎么保存状态!(我感觉，越来越…..)(声音好大，别人还以为我们吵起来了)

A 那么我们来换一个题：

现在，我们的服务器上有一个APK文件，你知道就是一个ZIP包，对于每一个用户请求，先建立连接，然后判断请求来源，把apk解包，在manifest后追加来源信息，再打包成apk，发给请求方。

问：1.如果多个用户同时请求，没有时差，怎么解决冲突?

2 .如何提高数据的发送效率?

B 单例模式?

A 单例模式解决不了。

B 如果多用户同时请求，可以建立一个请求队列，然后判断请求队列是否为空，不为空，则循环取队列中的请求建立连接!

A 如果两个用户的请求同时到达!

B 对文件加锁!!

A 如果两个请求同时请求加锁?

B 这个….我不是很清楚!

A 那么看第二个问题，如何提高数据的发送效率?

B 得先找瓶颈段，看哪段效率最低?我觉得的瓶颈段应该在节点的转发上!spfa寻最短路!

A 不是!!

B 哦，数据到公网上就不受发送者控制了!那就是服务器端，数据包分组发送?

A 那怎么分组?

B 这个不是默认就分好的吗!

A 你可以控制!

B 好吧!这个不是太懂!

A 那今天就到这里吧!你先回去吧!

B (估计没戏!回去好好学习吧!)