2017.08.31依图面试
今晚连着面了三轮依图。。毫无间隔。。累pee= =
第一轮
自我介绍+介绍项目
算法题1
一个长度为n的数组，其中有一个数字出现次数大于n/2次，找出这个数字。
这个题貌似是个竞赛经典题。。之前一个同事给我讲过这个题，但是我给忘了！但是现场给出了两种解法。。第三种面试官怎么提示都想不出了。。
第一种：一个dictionary记每个元素出现次数，如果出现次数大于n/2，中断当前遍历并返回，O(n)的复杂度
第二种：转换为找第n/2大的数字的问题，解决。平均O(n) //我当时第一次说的是排序之后然后中间那个数字就是要找的，结果面试官让我写排序算法，我写着写着快排反应过来的。。
查了一下，是http://blademastercoder.github.io/2015/02/04/leetcode-MajorityElement.html 的思路2的解法
算法题2
给出一个m行n列的矩阵，由元素0和1组成，元素0表示当前位置可以走，元素1表示当前位置是围墙不能走。找出从(x0, y0)到(x1, y1)的任意一条路径
深度优先搜索
第二轮
自我介绍+职业规划聊天=。=
算法题1
n皇后问题，n*n矩阵里放n个皇后，给出一种解法
算法题2
已有一个Rand2()函数，可以等概率地生成0和1(都是1/2)，问利用这个函数如何等概率地生成0, 1, 2, 3, 4, 5, 6。
面试官给出提示，先考虑如何等概率地生成0-7
每个出现的概率是1/8，这个可以用三位二进制表示法，每位是一个Rand2()
然后到等概率地生成0-6，只需在生成111的时候，再生成一次就可以
第三轮
自我介绍+项目介绍
算法题1
进阶：
算法题2
然鹅我还是不知道解法现场想的。。。
进阶：
从最多只能进行一次买卖改为最多可以进行两次买卖，问最大收益是多少
这个面到第三面脑子已经完全不转了。。。面试官给的解法。。
从前往后扫一次，找前i天最大收益A[i]；从后往前扫一次，找后i天最大收益B[i]；这两个可以一次遍历做完。
然后再遍历一遍，找A[i]+B[i]最大值
最后的吐槽。。无间断连续三场(我开始还以为只面一场。。也怪自己没问清楚。。于是晚饭都没吃就去了。。还好男票在面试前跑去给买了面包和水，在前两场中间塞了一个面包= =)还是挺懵以及挺难一直集中注意力的。。一个大屋子里，就3v3的面试别人说话也听得很清楚，于是话到了脑子里脑子就会处理一下，于是思路也就会断一下= =不过感觉面试官都很有趣~他们做的东西也都挺有趣的233(感觉自己被洗脑成功了。。
