面试地点是一个大教室，一对一的一个面试。
首先让你做一个简单的自我介绍，他顺便看一下简历，然后就步入主题了（以下简称A工程师和B 我）：
A：你面试的是android?恩，下面问几个简单问题？android 里面的Intent 有什么作用？
B：用于Activity之间的跳转，还有数据传递。
A：还有什么作用？
B：(还是坦白吧！不要不懂装懂)其实android研究的不是很深，其实我用的最多的是算法？
A：志愿里面有一个算法工程师？为什么没选？
B：我以为要求很高，所以没敢填，所以写在了第二志愿！
A：好吧，那我就问一下的算法题，过了就把你转到算法工程师那里去二面！那你主要研究的算法有哪些？
B ：我平时研究的是dp和博弈。
A：博弈？
B：主要是背包问题（01,完全，多重，二维费用等），威佐夫博奕，nim游戏，SG定理以及取走分割游戏。
A：我们来看一个问题：n位的01串组成的集合S1（共个），找出一个母串的所有同构串所组成集合S，S1属于S。有点抽象，看个栗子：
比如 n=2 所有的01串有：00 01 10 11
0110 的所有2位的循环同构串有：01 11 10 00符合条件，不能找到更短的了，因为至少得有2个0和1.你分析一下如何找一个最短的母串！
B：然后想了一下，应该这个串长度最少应该>=2n，大约想了5min，感觉没什么思路！
A：你想一下，编程怎么解决？怎么找出这个串？
B：构造？
A：不是，你把n位的所有01串全部列出来，再去选！
B：暴力？这样的话复杂度是()阶乘。
A：这个串肯定包含连续n个1和连续n个0的情况，可以去掉很多情况，复杂度可以降很多
B：（无语，(!) 你这么点优化，无语）
A：下面，我们来讨论简单点的问题：32位操作系统可识别的内存多大？
B：理论值是4G。
A：为什么是4G？
B：因为32位bit可编码的地址空间是2^32 ，所以是4G。
A ：那么你简单说一下操作系统是如何分配内存的？
B 从开机开始？
B：首先，计算机加电，cpu直接将cs+ip置为BIOS第一行代码的地址，读取BIOS代码…..直到启动桌面。
A：那么下面说一下32位int如何每一段如何划分的？内存分页，最小的段是多少位？
A：下面我们还是来做几个题：如何判断一个单链表有环？
B：想了一下，Hash判重，每次查询是O(1)效率是O(n)，如果访问过重复访问的点说明有环，如果为NULL，说明无环？
A：不错，那么辅助空间是多少？
B：O（n）
A：可不可以不用辅助空间呢？或者只用O（1）的辅助空间
B：让我想想？好像没什么想法，因为你都忘记了你自己走过的路，好像不好搞耶！
A：那么我们来看下一个题：给你一个严格递增的序列，从中间某个未知的地方切成两段，将前一段放到后面，求最大值？注意划开的位置你不知道！
B：O(n)的遍历可以，我觉得你是要更高效率的算法！然后在纸上简单画了画，大约两分钟thinking，发现可以二分搞！立马给面试官讲了思路！
A：写代码实现一下。
B：下手就写，写完之后，发现L<R有点小问题，没去管！
A：面试官看了下，你的边界是不是有问题？
B：想了1min，改成L+1<R返回的时候min(a[L],a[R])就没事了。
A：判断一个二叉树是否关于根节点左右对称！
B：想了想，遍历树的方式，发现“左根右”==“右跟左”即可判断是否“手性对称”（这是高中在书上看到的一个词）。
A：如果一个做孩子为空，一个右孩子为NULL，那就不对了。
B：加一个-1到遍历序列。
A：你这个方法可以，但是你得保存遍历序列，可不可以不要辅助空间？
B：（好吧！原来优化了时间，再想空间优化，一般我只做前一个）想了想，遍历！
A：写一下代码。
B：下笔就开始，发现自己没写好，又自己重写了一次，大约花了7~8min，好了。
A：再看一个题：一个二叉树，层次遍历！写一下代码。如果你想记录下来一起输出也行。
B：（搞的我好像很喜欢开数组似的，还有没有完！）BFS层次遍历就行。
写完代码先到外面等一下，大约5min，通知进去二面。
A：做，先简单介绍一下！
A：下面我们来讨论一下CS.
B：不好意思，没听太清CS是？
A：Computer Science（不屑）
B：哦，计算机科学！（汗）
A：看了你的简历，平时都研究哪方面的算法？
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：那今天就到这里吧！你先回去吧！
最后的最后：没有深入的了解TCP/IP，觉得各种解释都是那么苍白无力！
满意的地方：
面试官还是挺专业的。
不满意的地方：
被虐的太惨了！
