微软
2月2日 一面试
-
自我介绍
常规的自我介绍。但当时我一开始还是紧张，就稍微说了下学历。
-
问做过什么Project
我说了下我现在在弄的Research Assistance以及本科的Final Year Project。然后面试小哥就问了下详细内容，比如说用什么语言写的，用来干嘛，loss function是怎么写的之类。也没问一些特别基础刁钻的东西。然后就进入做题环节了。
-
做题
做题是在一个白板网页上写，这白板的编辑器唯一的功能是换行时自动跟上一行对齐，其它任何功能都没有，包括自动补齐。
-
找链表倒数第K个节点 （剑指Offer 22）
要求在 $O(n)$ 时间内完成。我第一时间是想到把所有节点都存到数组里，然后返回数组倒数第K个。然后仔细想想之后发现是双指针。第二个指针比第一个指针晚K次再出发，第一个指针为null时第二个指针即为结果。于是我就跟面试小哥说了下我的思路，然后一分钟就写了出来。面试小哥看了下说我没判断输入参数是否合法。我发现确实，平常在LeetCode上做题基本没有输入参数不合法的，最多就是一个空参数。于是补了个判断条件就过了进行下一题。
-
数二进制数1的个数 （LeetCode 191、剑指Offer 15）
一开始我想的是一位一位的往右移判断最后一位是否为1，直到所有位为0。写完之后小哥跟我说如果输入是负数怎么办。然后我就想了下，结果就卡在这了。负数右移的话是在左边补1，所以我就想要不往左移，取最左边的1。然而我平常用开的Python整型是无限大的，所以如果往左移的话数字只会越来越大，永远不会停下来直到爆内存。所以也就不知道最左边的1在哪。于是在这我就纠结了很久。期间也跟小哥沟通过，但他对Python也不是很熟，没能很好了解这情况，最后提示时他还是跟我说往左移。最后我就说我就假设是个8位的吧就加了个
n & 0b10000000的判断，然后再跟他解释了下。也不知道他有没有算我过。就时间关系就准备结束面试了。到了最后的最后他跟我说其实可以直接n & (n-1)来移除最右边的一个1，我才恍然大悟。
-
结束这一轮面试之后我感觉我无了，因为最后一题卡了差不多得用半个小时。结果吃完饭后又收到了约第二轮面试的时间，就突然感到又有了希望。
2月5日 第二轮面试
-
例行的自我介绍。
-
也是问了做了什么Project，就照着上次那样说了。
-
然后前后不到五分钟就到做题了。这回没有用白板，而是让我共享屏幕让我在我自己电脑写。
-
单例模式
面试官问我有没有听说过单例模式。我说没有。我还以为是“单立”==Standalone。然后他跟我解释啥叫单例，即每个类只能有一个实例。然后让我写这么一个单例的类。我没听说过就只好瞎蒙了，用一个静态变量当计数器，每有一个实例计数器就加一，计数大于一时就抛出错误。然后面试官问我如何不抛出错误实现。然后我想了几分钟，瞎写了几下，说不会，他就让我做下一题了。
-
合并区间 （LeetCode 56）
挺简单的一道题，就排个序然后首尾相连就好。写完之后面试官让我自己出几个测试用例。我就随机打了几个。他说这样不行，问我测试用例的目的是啥。我说测试程序有没有bug。他就跟我说要测试到每一条语句，每个if else都要有用例测到。然后我就按着他要求写了几个用例。然后他也没评价，就直接说面试时间结束了。
-
整轮面试不到半小时。面试完一整天也没收到邮件什么的。不知道是当场放假了还是无了。
2月18日
凉凉。
阿里
测评
-
阅读理解 约10题
-
表格分析 约10题
-
找规律 约10题
-
性格测试 约100题
笔试
-
翻转次数
小明现在手里有两个数$a$和$b$，你需要进行若干次操作使得$a$和$b$的值等于$c$，每次操作可以任选$a$, $b$两数之一的某一个二进制位进行取反操作，即0变1，1变0。 其中 | 是按位或运算，其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位中有一个为1时，结果位就为1，否则为0. 现在想让你求最少的翻转次数，使得$a | b = c$成立。
-
蜡烛
有一根长度为n厘米的蜡烛，每分钟可以燃烧1厘米。现在我们会把这根蜡烛随机分成两根蜡烛。如图：有$n –1$个可以分的位置，在每个位置分开的概率都为$\frac{1}{n-1}$然后就可以得到两根蜡烛，把没有燃烧的蜡烛点燃，如果这两根蜡烛其中一根燃完时，另外一根的长度>=2那么我们还必须对剩下的这根蜡烛再进行一次随机分开，再点燃的操作。这次操作后不能再进行任何操作。问所有的蜡烛全部烧完的期望时间(分钟数)。
面试
-
自我介绍
-
问项目
米哈游
笔试
-
1807
输入一个字符串，求最长的包含且只包含1807这四个字符且按1→8→0→7顺序的子串的长度。
我一开始想的是$O(n^2)$的动态规划。后来发现不太对，就直接改成用一个字典来分别计算以1、8、0、7结尾的最长子串的长度，一次遍历$O(n)$。
-
【C、C++、C# 限定】牛牛的游戏俱乐部
有$n$个游戏，每个游戏需要1单位时间来完成。第$i$个游戏必须在$t_i$时间或之前完成，完成则获得$w_i$分，没完成则扣除$w_i$分。求最大获分。
我的想法是用一个字典来储存每个时间段的所有游戏分数。然后每个时间段取最大值减去所有剩下的值得出答案。然而语言成了我最大的障碍，特别是我平常用惯Python，各种变量类型声明整得我头大。
-
平衡数
求$[L,R]$区间内奇数位和等于偶数位和的数的个数。
由于上一题语言问题卡了许久，这题我就只写了个暴力解，通过13.33%。
-
中序遍历
字符串$A(B(C,),D(,E))$表示二叉树
。求这类字符串表示的二叉树的中序遍历。
结合用栈实现树的遍历。节点值按顺序入栈，空值也入栈。遇到逗号弹出两次，遇到右括号弹出一次。弹出顺序去掉空值即答案。
-
是否凸多边形
给定$n$个点坐标，按顺序连成一个多边形，求该多边形是否凸多边形。
提示：对于一个多边形的任意边，若所有不在该边的点都在该边所在的直线的同一侧，则该多边形为凸多边形。
对于任意边的两点$(x_1,y_1)(x_2,y_2)$，用直线的两点式表示该边所在直线
\[\frac{x-x_1}{x_1-x_2}=\frac{y-y_1}{y_1-y_2}\]对于其余点$(x_i,y_i)$分别代入该式的$x$、$y$，若均为大于或小于，则都在同一侧，即该多边形为凸多边形。
面试
一开始就直接开门见山问问题，没有自我介绍，也没有问做了什么项目、项目做了啥。
上来就先问对C、C++、C#熟悉吗，学校有教吗。我说我们学校基本不教语言，就教理论、算法，语言基本靠自学，C#会比较熟。然后我说我很久没用这几门语言了，所以可能会比较生疏。
见我说我C#比较熟，于是他就问了些C#的问题。比如值类型和引用类型、ref和out、重载和重写等。然后又穿插了一些C和C++的，比如C的malloc和C++的new的区别等。然后见我Python比较熟又问了些Python的问题，比如list和tuple、修饰器的原理和作用等。
然后到算法部分。问了下排序算法有哪些、队列和栈、深搜和广搜、树的遍历、红黑树之类的。还问了些面向对象的特性和原则、多态、继承之类的。
最后就问玩过什么游戏，游戏引擎了解多少。然后就结束了，大概二十来分钟。
过了三天，就收到了感谢信。