Google 第一轮和第二轮面试

更新：我被拒了。明年继续努力！

被大神refer后居然拿到了intern面试机会。

第一轮：

从口音来看是个印度人大叔，tension很高。

Q1：给你一个data arr，要你在out arr里put数组和。

ie data： 1 2 3 4 5

    out:      1 3 6 10 15

这个很简单，就一个for loop搞定。秒速写完，对面来个good。

Q2：给你一个2d的 data arr，要你输出同样道理的out arr。

ie: data: 1 2 3

                2 5 6

               7 8 9

       out:  1 3 6

                3 10 19

               10 31 66

我的回答是先是横着加，然后再竖着加。idea没问题，他让我写。然后我就卡了。主要是太久2d arr没做过了。他建议我按照我的想法，把步骤的公式列一下然后再写。我列完后立刻就写了出来... code就不写了，就是两个 n方的loop。

Q3：他给了我这个interface，让我implement

public interface tables {

            void set(int x, int y, int val);

           int sum(int x, int y);

}

后来被陈趴趴教育说这是个online algor，set和sum之间有个trade off。理论上来说，有个两个都是log n的算法，但他也想不出。

休息了十五分钟。其实也算不上休息，就是喝了些水。大脑已经进入了兴奋状态，坐了一会儿然后第二个面试官就打来了电话。

听声音有点怀疑是中国人，声音感觉很严肃？就是一点语调都没有。

上来就来句“I am from Google.” 我硬生生地回了句，然后那哥们就开始出题了。

Q1 BST Level Order Traversal

几乎是leetcode原题。leetcode的是让你return一个list的list，这个是直接print。我先是按照原题把它存进了list里然后最后print。我一开始忘记在console里打空格了，但是后来终于改好了。然后哥们问我说，好，你这个O（n）是多少。我说，先traverse每个node，就是O（n），最后print也是O（n）啊。他说，嗯对其实是O（2n），你可不可以improve一下。我看了下，感觉result的那个list的list并不需要就把它删了。他说行，然后我又盯了一会，因为我觉得还有地方不够好。这个时候我想起了陈趴趴以前跟我说space complexity的问题，我就立刻反应过来说还有个improve的方法。然后面试官说，that sounds good to me。然后进入了下一题。

Q2 BST Level Order Reverse

题就是reverse，基本就是把code粘过去改了一下console。

这次面试结束我个人感觉还可以，然而第二天recruiter给我发邮件说要加面。

祝我好运吧。