2018-06-04 14:34 已编辑 hulu_Senior SDE

关注

渣硕面筋release v1.0(Google已跪)

最终入职了头条，有健身房有食堂，有游泳馆有房补，非常满意。

坐在靠窗的工位喝杯咖啡，顺便用我顶配的MacBook Pro打个内推广告：https://www.nowcoder.com/discuss/83305?type=7&order=0&pos=6&page=0

----------原文----------

网易有道

有道是投的第一家公司。对比了网易的业务后，感觉有道不错，通过同学内推。

笔试

有道的笔试分为3个部分，笔试难度：★★★

第一部分是性格测试和智力测试。会问一些类似于公***的题目，略。
第二部分是基础知识选择题。涵盖的内容很广，基本上本科计算机必修课程都会涉及到，包括二叉树遍历，数据库索引，操作系统调度算法之类的，感觉也没什么好的办法复习。
第三部分是编程题。好像不同岗位题目不一样。一共3道题目，具体题目记不清了，当天正是works applications写文档的最后一天（后面会讲这一段痛苦的回忆），状态很差，做出1.5个（按照ACM规则算的话，只能过一个签到题）。第一题很简单，属于送分题。第二题其实也很简单，就是一串数字往一个Dqueue里面放，第一次放在头部，第二次放在尾部，交替进行，最后输出这个Dqueue。我居然超出了内存限制，至今不知道为啥。第三题只记得不会，忘了是什么题。
笔试的神奇之处在于，我只做了1.5个题，居然通过了笔试。有的同学3题全做出来，结果没拿到面试资格，只能用玄学解释。

面试

面试一共3轮，在西二旗的网易大楼里，面试难度：★★★

第一轮面试

首先是自我介绍，然后根据简历上的项目问了一些Spring相关的东西。还有Java的volatile之类的问题。然后就是常规写代码。大约40分钟。
问了2个题目，第一个是给一个只包含RGB三个字符的字符串排序。第二个是求编辑距离，之前没有做过这个题目，想了一会觉得和最长公共子序列很像，DP搞定，有兴趣的同学可以去查一下，应该有原题。

第二轮面试

是个小姐姐，居然是北交的校友。也是自我介绍，问项目，问Hashmap，Hashtable之类的常规JDK数据结构。然后就是常规写代码。大约40分钟。
问了2个题目，第一个是二分查找变种，找符合要求的最左边的一个元素，答案我就不说了，稍微修改一下就行了。第二题是要求把字符串中所有的0移动到最前面，其他的顺序不变。

第三轮面试不是HR面

自我介绍，简单地聊了聊实习经历，个人做的项目，就结束了，我也不记得问啥了，好像是啥也没问。一共15分钟。

体验

面试舒适度：★★★

先说面试体验不够好的地方：

等候区座椅太少了，全程我基本属于蹲着等的状态，蓝瘦。
面试节奏太慢了。前两轮面试用了一下午，两轮之间间隔了1小时。第三轮面试和前两轮面试之间间隔了十几天，然后又过了二十天才通知结果。

再说说优点：

面试的房间还挺安静，没有乱七八糟的人。
提供矿泉水。
中秋节还给寄月饼了，点赞。

美团点评

美团是微信群里一个前辈内推的，其实并不认识，记得好像没有笔试，直接去面试了。（做了太多笔试，实在记不清做没做了）

面试

美团面试是3轮技术+1轮HR。面试难度：★★★

第一轮面试

是一个广东强调的小哥，说实话有一点点听不懂他在说什么。。。问了很多基础的东西，比如各种http状态码的含义，断点续传的下载实现，Spring的Session相关，hashmap等，都很常规。
最后写了一个题目，自己实现一个优先队列。

第二轮面试

依然是常规问题。后面聊了很多项目中遇到的问题，比如你如何解决遇到的问题，遇到的最难的问题等，我详细聊了一下自己做第三方登录过程中遇到的问题，也就是Spring Security的问题。
写了两个题目。

第一个是全排列，但是要输出当前字符串的字典序下一个排序。做完后我还提到可以用线段树优化一下，把一个O(n)的操作优化成O(logn)。

第二题他描述要实现Android上面图标移动的效果，可以移动若干个图标插入到前面某个图标之前，该怎么设计。我们讨论了很久我没有明白他的意思。最后面试结束面试官送我出去的时候我才搞明白，就是一个数组某相邻两段交换位置，各自翻转，然后整体翻转就可以了。

第三轮面试

没有手动写代码的问题了，看起来是个leader，主要聊自己的项目。还问了一些最近看的书啊，最近刷的比较难的题目有哪些之类的。

前三轮面试大概都是40分钟。

HR面

问了问老家是哪的，对自己面试表现感怎么样，都面了哪些公司，期望薪资等，就结束了。

体验

面试舒适度：★★

缺点

不光等候区座椅少人多，而且也没有水，中午也没有吃的
面试环境很乱，旁边有人在讨论工作，没有单独的会议室来面试

优点：

面试节奏快，一天就全搞定了

今日头条

准备的比较晚。有一天晚上同学们都收到了头条内推的笔试通知，我才想起来投了校招，所以没有和他们一起做笔试，但是看了内推的笔试题目，挺难的。

笔试

前面有没有选择题我忘了，只记得3道编程题，难度★★★★

第一题

比较简单，具体记不清了，就是那种没什么算法，按照题意写就能得到结果的题目。

第二题

有些难度。给一个数组，然后会有一些查询，比如查询3,6,4，表示数组从第3个元素到第6个元素中，4出现了多少次。题目保证查询的区间直接没有包含关系。直接查询时O(n^2)，需要优化一下。因为题目说了区间没有包含关系，所以我们把查询排个序，然后用离线的算法，依次把数组的元素加入到一个map中，记录它出现了几次，当达到一个查询的右边界时，输出map和查询数字对应的值。然后从查询的左边界扫到下一个查询的左边界，从map里面取出这些元素。这样做扫一遍就得到答案了。复杂度是排序的O(nlogn)。

第三题

不会做，我记得我用了个深度游戏搜索，跑出20%的数据后超时了。

其他题目

还记得我错过那场的一个题目。给一个数组，区间[l,r]的最小值乘以区间之和，问最大值是多少。首先求任意区间的和很容易，求前r项和减去前l项和，就是l到r的和。解题的思路是以任意一个数为最小值，向两边扩展，一直扩展到第一个比它小的值，那么答案就是这个区间和乘以这个值。这样做是O(n^2)，还是不行，怎么找到一个值左边第一个比它小的值呢？需要预处理一下，用一个上升的栈，扫一遍。右边同理。最后的复杂度是O(n)。

面试

一共3轮面试，面试题目范围很广，面试难度★★★★

第一轮

Docker的用处是什么，为什么需要它。
数据库分表如何做，有什么原则（数据库不熟，不会，只提到按hash分，按日期分，好像面试官不是很满意）
写一个sql语句，查询一张表中，发表批评最多的人
写单例模式（两种方式）
一个二叉树，从左边看，能看到的第一个节点，输出。也就是每一层的最左边的元素

第二轮

进程线程的区别（这个问得比较细，不只是简单的内存共享之类的，还包括操作系统的进程描述，写时复制，操作系统启动等问题，推荐《深入理解计算机系统》）
epoll，IO多路复用，聊到nginx的原理，和Apache的区别
常见的网络攻击方法，比如跨站脚本，sql注入之类的
Https，非对称加密等
一个秒杀系统的架构，包括CDN，反向***，session共享，由于分布式数据库我不熟，所以数据一致性那部分没有解决。
Hashmap的实现原理，优化方法（其实JDK 8已经用二叉树替换链表了，思路差不多就是这个）
脑筋急转弯，1000桶牛奶，1桶有毒，用10只小白鼠试出来。其实就是二进制，网上有答案，提示：2^10 = 1024.

第三轮

做一个游戏，一套扑克牌，从上面拿一张放在桌上，再拿一张放在扑克牌最后，循环这个过程，最后得到一个序列。给定结果，要求把这个序列还原。我的做法是正向模拟这个过程，最后得到映射关系，反着填回去就好了。
问了个C语言的问题，strcpy有什么问题，怎么解决。我不太熟悉C，感觉可能存在src和dest有交集的时候会有覆盖问题，然后判断了一下是不是有交叉，如果是的话，src和dest谁在前谁在后，交叉的长度是多少，反着就是注意一下顺序问题（不熟C，不知道是不是这个问题）
点击一个网站后发生的所有事情，HTTP，DNS，CDN，TCP之类的东西全啰嗦一遍

常规聊天，薪资啊，规划啊，兴趣啊之类的，没什么特别

体验

面试舒适度★★★★

缺点：

在食堂面试，人很多

优点：

在食堂面试，有座位，有饮料，有午饭
面试时间可以自己选择，很灵活，这一点很棒。很多公司面试时间是定死的，有时候会和自己的事情冲突。
面试效率超级高，现场出结果。此前我一度以为，有道会是我的第一个offer，没想到等了一个月后，用一个上午就通过了头条，午饭吃得惊心动魄。

猿题库

猿题库没有笔试，直接面试。

这家公司比较低调，开始都没听说过，后来去知乎看到说猿题库出手很阔绰，并且个人感觉教育行业挺有前途，就去投了。

面试

一共两轮，没有HR面，感觉面试挺简单的，面试难度★★

第一轮

常规的自我介绍，聊了聊项目

问了一些Spring，自己的项目

写了一个括号匹配的题

给一个m*n的格子，总左上角走到右下角有多少种走法。简单的dp题目。此外，如果m==n的时候，是卡特兰数，但是当时不记得卡特兰数的公式了。

第二轮

聊项目，项目中遇到的问题，如何改进等

写一个循环队列

面试官简单介绍了公司的业务

体验

面试舒适度 ★★★★★

优点

有好多零食，旺仔牛奶，有座椅
不用前台前到，贴标签，直接到会议室等待，面试环境很好
HR小姐姐很漂亮

缺点

无

阿里巴巴

笔试难度 ★★★★★★★★★★

内推的时候，通知我有杭州的岗位。由于个人原因，我只打算在北京工作，所以没有面试。

校招的时候，笔试真的太难了。给定10个物品的长宽高，和箱子的规格，问最少需要多少箱子能装进去。至今不知道谁做出来这个题目。

京东

忘记了是不是有笔试

面试

面试难度 ★

一共三轮面试

第一轮

大约15分钟，自我介绍，简单聊Spring，就结束了

第二轮

40分钟，聊了Java异常处理，Kotlin的一些感想，好像也没聊啥

对京东的看法，个人的倾向，对面试的评价，大约十几分钟

体验

面试舒适度 ★

感觉面试全程谈笑风生，然后就悲剧了，不知道问题在哪，玄学。

缺点

三场面试分三天，效率低
每一场面试都没有按时进行，最短等了十几分钟，最长的等了半个多小时
全程没有写程序，总感觉这套路不太对

优点

貌似不同学校的面试地点不一样，我的面试地点就在北航附近，这一点还挺人性化

滴滴

内推笔试，感觉挺简单，但是挂了

校招笔试，感觉挺简单，但是挂了

Hulu

免笔试，电话一面跪

设计一个短网址，在线写一个n进制转换函数

当时那段代码确实写得很烂，挂掉没什么遗憾

WAP

这家公司是我面过的比较另类的公司，我需要简单介绍一下。

这是一家ERP公司，总部在日本，中国的办公地点是在上海。
其他公司的工资一般都是保密的，这家公司待遇是公开的，固定600w日元，大约34-36w人民币。可以说是应届生里面比较高的了。
不同于其他公司的面试，这家的面试是为期一周的短期实习。

笔试

笔试2道题目，笔试难度★★★★

第一题
这题我当时记下了题目，我们来分析一波

The prison garded by Tom has got N rooms wihich are numbered consecutively as 1...N. One inmate is held in one room. There are M provinces and every inmate may come from one fo the M provinces. If an inmate came from the same province with the one who is held in the next room, a prison break may happen. In how many situations will a prison break happen?

Input two integers M, N(1 <= M, N <= 10^9)

这个题首先能想到是个DP问题，dp[i][2]，i表示前i个人，2表示当前是否已经有越狱情况。转移方程也很简单，dp[i-1][0]表示前面i-1个人都没越狱，那么第i个人越狱只能是第i个人和前一个人属于同一个省，只有这一种情况。dp[i][1]表示前面i-1个人已经越狱了，所以第i个人可以有m中情况，随意哪个省都可以。同理，dp[i][0]也是类似的。

得到转移方程后，需要再考虑一个问题，看到数据范围是10^9,转移n次显然会超时。即使不考虑时间，光看内存也不够（其实内存可以使用滚动数组）。这是观察可以发现每次转移的方程是一样的。我们把状态i看作一个矩阵[dp[i][0],dp[i][1]]，转移方程就是乘以[[m-1,1],[0,m]]。每次都乘以一样的矩阵，就可以使用快速幂计算，复杂度log(n)，结合10^9的数据，完美解决。

作为一个笔试题目，这题还是挺难的。

附代码

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
public class Main {
    private static Scanner sc;
    private static final int MOD = 100003;
    static {
        String properties = System.getProperty("os.name");
        try {
            if (properties.endsWith("Mac OS X"))
                sc = new Scanner(new File("/Users/lixiaocong/Documents/nowCode/src/text.txt"));
            else
                sc = new Scanner(System.in);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
    public static void main(String[] args) {
        int m = sc.nextInt();
        int n = sc.nextInt();
        System.out.println(solve(m, n));
    }
    private static long solve(int m, int n) {
        if (m == 1)
            return 0;
        long[][] matrix = {{m - 1, 1}, {0, m}};
        long[][] ret = power(matrix, n - 1);
        return ret[0][1] * m % MOD;
    }
    private static long[][] power(long[][] matrix, int n) {
        if (n == 1)
            return matrix;
        long[][] ret = power(matrix, n / 2);
        if (n % 2 == 0)
            return time(ret, ret);
        else
            return time(matrix, time(ret, ret));
    }
    /**
     * 矩阵乘法
     */
    private static long[][] time(long[][] matrixA, long[][] matrixB) {
        long[][] ret = new long[2][2];
        ret[0][0] = matrixA[0][0] * matrixB[0][0] + matrixA[0][1] * matrixB[1][0];
        ret[0][1] = matrixA[0][0] * matrixB[0][1] + matrixA[0][1] * matrixB[1][1];
        ret[1][0] = matrixA[1][0] * matrixB[0][0] + matrixA[1][1] * matrixB[1][0];
        ret[1][1] = matrixA[1][0] * matrixB[0][1] + matrixA[1][1] * matrixB[1][1];
        ret[0][0] %= MOD;
        ret[0][1] %= MOD;
        ret[1][0] %= MOD;
        ret[1][1] %= MOD;
        return ret;
    }
}

第二题

题意忘了，是一个裸的线段树，单点更新，区间查询。

这个题目出得，感觉没什么意义。纯考现场想，肯定想不出来，而做过竞赛训练的人有觉得太基础了。

面试

在线面试，还是做题。

第一题

zigzag原题，去leetcode找

第二题

求最长回文子序列，直接反过来求最长公共子序列就好了

面试要求保密不能发

体验

面试舒适度★★

实验室的学弟拿到了offer，请问你们知道被学弟吊打是怎样一种体验吗？

Google

笔试

笔试难度：★★★★★

Google的流程和其他公司不一样。别的公司是先投简历，再做笔试。Google是先去做在线笔试，通过笔试的再投简历。
笔试地址在这里，每年校招前有5场比赛，参加任意一场即可，至于通过不通过，没有具体的标准，只能等Google通知。
一共有3个题目，3个小时的时间。每个题目包括small和large两组测试数据，每个题目有自己的分数。比赛按照分数的用时排名。我做的是E轮排153名。

第一题

在这里。大概意思是你有3中操作可以做：

在键盘上敲一个字符
复制一段现有字符串
粘贴剪切板上的字符到最后

请问，最少需要多少次操作才能生成一给定的字符串，字符串长度是100。这是个DP问题，最朴素的想法是dp[i][j][k]表示已经得到前i个字符，剪贴板上的内容是第j到第k个字符需要的最少操作数，然后状态转移也很简单，就是对应前面3种操作。
复杂度n^3，其实已经可以通过了。不过考虑到第j到第k对应的子串可能有重复，比如我们要得到aaaaaaaaaaa，那么dp[10][1][2],dp[10][2][3],dp[10][4][5]...dp[10][9][10]都是一样的。我把三维dp改为了二维，dp[i][s],表示处理到第i位，剪贴板上的内容是字符串s，然后用一个hashmap把s映射到一个数字上。具体代码可以在这里看到所有人的代码。

第二题和第三题我不会，只能用暴力把两个small的数据通过了，large的不知道怎么做，有兴趣的同学可以去看官方题解。

此外，我在做这个比赛之前去看了一些前一轮的题目，D轮的第一题也是一个DP问题。大概意思是你需要从城市1出发，依次路过城市，2，3，4...N，每个城市。每个城市i到城市i+1都有公交车，题目会给出每个城市公交车的发车时间，发车间隔，路程需要的时间。每个城市你可以选择游玩或者不游玩，如果游玩的话需要消耗给定的时间。问题是求出能够在给定时间内到达城市N情况下，能够游玩的最多城市数量。
很典型的DP问题，dp[i][j]表示到达第i个城市，已经游玩了j个城市需要的总时间。题目比较麻烦的地方是状态转移的时候，需要计算公交的发车时间，频率和路程，整体思路没什么难的。

面试内容要求保密不能发

体验

舒适度★★★★★

Google的题目还是挺难的，我觉得就笔试来讲，这个难度正好适合我。时间刚好把我会做的题目做出来，不会做的题目再给我一天也做不出来。今后想要尝试Google笔试的同学，需要去多刷点DP问题。
其实我并没有期待能拿到Google的offer，最初的想法是能够体验一下Google的面试就好，现在看来已经实现了。如果能有幸体验一下Google的食堂就更好了。
此外做这个笔试可能需要科学上网技巧。

--------------------分割线------------------

update：

今天去面了大Google。由于题目不能发，我只能说，也没有想象中那么难，面试官很nice。由于本来就没奢望能通过面试，所以心态很放松，早餐喝了杯咖啡就驾驶摩拜单车去了。这家404公司里面和其他公司也没什么不同，一点也不神秘。中午面试，但是也没吃到食堂，很遗憾，看到了一墙的零食，也没什么胃口，只喝了瓶水。

现在我有一种面试能过的错觉（手动笑哭）

优点：

面试时间可以协调
笔试有很多场可以选择
情怀加1分

缺点：

Google让你去面试你还敢提缺点？

--------------------分割线------------------

被告知已经GG了，感觉已经发挥了99%的能量，会的都做出来了，不会的确实是实力不够，没有遗憾。

Microsoft

笔试

4道题，难度★

一个一维的世界，给出父亲的坐标，然后父亲以n个格子为间隔，朝右边走了k步。给定儿子的坐标，儿子在父亲左边，儿子第一步一定要落到父亲的脚印上，问儿子以多大的步长走，能得到和父亲最多重合的脚印。
一个n*m的图，上面0代表空地，1代表树。相连的树组成一组。问，要留下k组树，最少要砍掉多少棵。
一个数组，查询最大值，第二大值，最小值，第二小值，还有个什么更新不记得了。用两个堆解决。
忘了