湾区求职分享：三个月刷题拿到 Google offer - Jing blog - Reading

有朋友指出“三个月”是不是哗众取宠博取眼球。其实我确实是实话实说（详见下文）三个月。我只是想分享如何高效的做题，让大家少走弯路。那些刷五遍十遍的朋友，在我看来是走了弯路的，如果大家都能一两遍做懂，何乐不为？

本人背景介绍：

本科国内某211，EE major Power
硕士研究生USC CS General

实习经历

Amazon Inc, Seattle, WA. 3-month intern
Tesla Motors, Fremont, CA. 4-month intern

简历

简历的意义：简历到底有多重要？是不是要把简历写的很Fancy？写的比较多比较夸张会不会被问到？

对于New Grad来说，简历只是敲门砖，好的简历的目的是让HR注意到你“哎哟，这个New Grad不错，给ta安排一个面试吧”。所以，你的最终目的还是有面试机会。好的简历能够帮助你通过机器筛选和HR的筛选，但是很多时候，简历普通也是可以拿到面试机会的。“简历普通”不代表“简历写的差”，下面我会详细说明一下。

一个优秀的简历大概的样子：

Name: John Doe      
Email:jd@gmail.com      
Phone:xxx-xxx-xxxx

EDUCATION:
08/2014 - 05/2016   University of Southern California (USC)
M. S. in Computer Science   Los Angeles, USA    GPA: 3.80
......
//这个没什么说的，简单明了就好

EXPERIENCE:
2015/05-2015/08 : Amazon Inc, Seattle, WA
Position: SDE Internship
- Design and develop a realtime data aggregation workflow...
- Use AWS Kinesis to consume the original chunk of data...
- Develop a Java data processor that runs on AWS EC2...

2014/07-2015/01 ......
//写一下自己曾经在哪工作／实习过，大概做了什么内容用了什么技术。

PROJECTS:
Web Search Engines on Arctic Data Information Retrieval
- Build a search engine based on Apache Solr for polar data analyzation.
- Design and develop web crawler to fetch data from polar science website
- Use SimHash algorithm for near-duplicates deduplication.
- Build a web search engine and apply page rank.
......

//需要对project技术性的描述。项目名称，之后以bullet point的形式写用了什么技术，实现了什么东西。

SKILLS:
- Programming Languages: Java, Python, PHP, JavaScript
- Operating Systems: RHEL, Debian, Mac OS X
Data Analysis: Hortonwork; AWS EC2, S3, CloudWatch, Kinesis; NoSQL, RDB 
- Web: LAMP
......

//SKILLS的建议是，不要写自己不会的，你写Python就要期待面试会用Python面你。任何写在SKILLS上的东西都会被问到。

总结：

好的简历不需要Fancy的排版，大方得体就行，不要有“酷炫”的感觉；
尽量安排在刚好一页。不需要超过一页（大牛除外）；
内容最起码要“基于真实”，可以“适当加工”；

标准是：任何写到简历上的东西面试官问道都可以详尽流畅的表达清楚。用了什么技术？哪些service？“看你简历写用AWS EC2了，给我详细讲一下AWS EC2和你使用的时候遇到的困难”这类问题。

实习的重要性：
如果说一个“完美的简历”是100%的话，一个好的工作／实习经历决定了这份简历的50%-80%，如果可以尽量去大公司实习，尽量多去几个不同的公司实习。除了实习之外：论文、Project、名校会分剩下的20%－50%。4.0会是一个小小的Plus，除此之外在3.0－3.9之间没什么区别，但是不要低于3.0，其实除了Oracle之外没多少人会看GPA。

如果说你没有实习经历，最好的建议是用从现在到毕业的这段时间给自己多找几个实习。
如果说你已经毕业或马上毕业没有时间实习，那么就把在学校做过的Proj多写一些。

刷题

三个月的过程：
2015年12月从特斯拉实习结束，到2016年4月面试完谷歌，一共四个多月时间。元旦给自己放了两周假期，过年给自己放了两周假期，中间再穿插着出去玩。连续的用在刷题的日子大概有三个月。我是每天“全职刷题”的，分派给每天的任务（x道题）会被我分成上午a道，下午b道，晚上c道。如果提前完成，剩余时间自由支配，放松一下。

从2015年12月开始刷题，就给自己制定了一个做题计划，在衣柜的镜子（没有白板-。-）上制作了一个表格，这个表格是我每天自我check的参考。原计划是两个月做完所有题（约340），但事实是一直到找到工作也没有真的做完所有题。最后做了250道unlock的和所有lock的题（我们几个朋友合买了一个leetcode会员）。

我之前的基础：
本科没有学过编程，研究生上的算法课也上的不是很懂，很多课堂上的概念反而是刷题的时候才理解。

2015年初，在面Amazon Intern的时候刷过一次题，做了大约100个 easy 和 medium。在学校一边上课一边做题，三天打鱼两天晒网效果不好，只学了个皮毛。

2015年底翻看做过的题，基本忘光了。干脆搞个新账号重新开始。这次是每做一道题进行一次总结。翻看leetcode的热门评论，把自己的解题思路和别人比自己写得好的解题思路都详细的记在笔记本上。遇到一道新题就尝试理解，归类，翻出老题做对比，写code，看热门答案，更正、优化自己的答案，为什么他能想出这个解，搜一下相关不熟悉的知识点。

这个方法开始起步会特别慢，没有什么成就感。但是效果出奇的好，刷了一半，只要做过的题，理解的十分透彻。遇到一个考到的算法或者数据结构，比如trie tree，就会回去看所有trie tree分类的题，主要是看题目，回忆解法，如果想不起来或者不是很自信，再写一次。反之很熟悉，脑子里过一遍就继续下去。看完trie tree也会想到Binary Search Tree, Segment Tree, Binary Index Tree。脑子里对这些数据结构过一遍。

这样做题到后来的感觉就是，everything is connected. 随便给一个题，就能找出这个题和什么题是类似的，或者其本质是这个算法的变形。简而言之，明确的感觉到，自己学懂了。

刷题是枯燥的，如果你想着用毅力用坚持，只会让它更枯燥。毅力是必须的但是坚持往往是痛苦的，何不让这个过程变的快乐。这个年代人人都是千里马，但是伯乐不常有。我们只能做自己的伯乐，给自己制定最合适的训练方法，因人而异因地制宜，自己既是“运动员”也是“教练”，毕竟还是自己最了解自己。时不时给自己一些奖励，给自己放一个小假出去转转。

其实辛苦几个月，没那么难。和农民伯伯一样，种地是辛苦的，可是丰收是喜悦的。当你发现你努力了一个月之后，做过的题可以得心应手，还可以给别人讲的头头是道，还是十分有成就感的。毕竟才几百道题嘛，比上高考差远了。做到炉火纯青很难，但是得心应手还是指日可待的。

怎么刷题：

最多被问到的问题是：刷题刷多少遍才够？我想说，答案因人而异，我一遍都没刷完，感觉就够了。因为刷题的目的并不是为了刷多少遍，而是为了做懂题。举个例子，参加过高考的都知道，高考是不会出你做过的题的，那做《5年高考3年模拟》还有用吗？答案是肯定的。刷算法题和做高考练习题的意义是一样的，你的目的是理解出题人想要考你什么，如何解题，几种思路，最后写出最优解。

如何“一遍都没刷完”而做懂题？

“善于总结”是核心。还是拿高考举例子，“不会做的题和做错的题”远比“做对的题”有意义，只有从错题中才能进步。做算法题也是一样的，不要在烂熟于心的题上面浪费时间，把时间用在错的，不理解的题上面。

拿到一道题，怎么做？
就拿Merge k sorted Lists这一题举例子：
Merge k sorted linked lists and return it as one sorted list. [Java]
1) First think about a simple merge idea. Go through k head elements each time, they are the smallest among their list, k pointers and totally nk elements.
time: O(nk^2) space:O(k);
[CODE] 略，自己写一下把，这个简单

2) Use heap. This is a classic question for heap. each time we change a heap value we only use Log(k) time
time: O(nkLogk) space:O(k)

1) A comparator used can be passed to Collections.sort(coll,comparator)
2) In java, heap is implemented as PriorityQueue. The constructor
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
constructor is initialized with capacity and compare rule.
3) Java anonymous class is used to simply create and use this comparator
4) The node inside list could be null
5) PriorityQueue use poll() method to pop out it’s first element

public class Solution {
      private static final Comparator<ListNode> comp = new Comparator<ListNode>(){
      public int compare(ListNode x, ListNode y){
        return x.val-y.val;
      }
    };

    public ListNode mergeKLists(List<ListNode> lists) {
      if(lists.size()==0) return null;
      Queue<ListNode> heap = new PriorityQueue(lists.size(),comp);
      for(ListNode node : lists){
        if(node!=null) heap.add(node);
      }
      ListNode dummy = new ListNode(0);
      ListNode p = dummy;
      //heap did not implement isEmpty method
      while(heap.size()>0){
        ListNode node = heap.poll();
        if(node.next != null) heap.add(node.next);
        p.next = node;
        p=p.next;
      }
      return dummy.next;
    }
}

1、这一题明显是考Heap的，如果对Java PriorityQueue不够了解的，就应该去复习一下。Java7和Java8不太一样，Java8在传入comparator不再需要给定size。
2、代码中写到了Collections.sort()，和在sort中写匿名类。
3、为什么要写dummy？在那些题中需要写dummy而return dummy.next。那些题不需要？
4、为什么用Queue interface，用List－>LinkedList可以吗，是否要复习总结一下list，queue和它们的implementation? 如果对Object Oriented 不熟悉的，是否要再看看继承(Inheritence)和多态(Polymorphism)。那再往深处想一想，Abstract Class 和 Interface 的区别，优缺点呢？

这些 Java 基础就是做题的时候要想，不是很理解就要及时解决。基础不好的同学，刚开始做会比较慢，所以一道题做完过去了大半天，这很正常，等做多了，烂熟于心了，做题就快了。每次做题也都是对知识点的强化。

代码[CODE]部分和代码上面我自己的思考笔记都是写在Evernote上的，每次写完代码要把遇到这个题时候的想法，解题思路，看完别人答案之后自己的理解，基于答案对自己code的改进写进去。

Design：
Design可以基本分成Object-oriented Design(OOD) 和 System Design(SysD). 简单说一下我的理解：
OOD: 面向对象设计，顾名思义，针对开发过程中的结构，关系，逻辑进行设计。比如说：设计电梯；设计五子棋；设计各种游戏等
SysD: 更多是scalability侧重。比如：DB(Master-slave)，sharding，Cache(Redis, Memcached), Load-balancing等等

OOD 推荐：

CtCI(Cracking the Code Interview)
23种设计模式全解析
Head First Design Pattern(如果你还有时间)

SysD 推荐：
hiredintech
http://highscalability.com

一个很不错的帖子：https://www.evernote.com/shard/s576/sh/7e58b450-1abe-43a8-bf82-fbf07f1db13c/049802174415b418a2e65f75b744ab72

1、这个准备可是没有尽头的。对New Grad来说没必要在这上面投入太多时间。我用了两周时间，OOD和SysD各一周。
2、SysD把hiredintech网站的这个教程看两遍，尤其是Harvard 的那个1小时45分钟的视频，我先后看了三遍。第一次完全不懂讲什么，只是记笔记听课。然后上highscalability.com 看了几个例子。搜了搜所有视频里介绍到到概念。再看第二遍1.5倍速，基本理解透彻。面试前2倍速看了一半，回忆一下。
3、 OOD没有尽头。最起码记住，理解，会用Singleton和Factory这两个。剩下的吹牛逼就行。OOD很少有绝对的正确或者错误。通常看你能不能说出这样设计的优点和缺点，选择的得失。
4、不要在design上面花太多时间。这东西，你不用也记不住，也不理解。抽出两三周好好理解几个例题就好，记笔记，onsite之前再复习一下。
5、 SysD我跟着Harvard的lecture画了一个有普遍适用性的图，不同的公司／业务scalability都可以套用。仔细看lecture。

面试

面试Pipeline：
HR安排面试 -> (HR聊天) -> (OA) -> 电面 (x 2) -> onsite -> (加面)
备注：(括号内容)或许有，或许没有。

最关键的是如何让HR把你放进pipeline，给你安排面试。有几种方式：海投 < 校园招聘 < 内推< 直接和 HR 联系

所以说，最好的情况是，HR主动联系你。说明ta对你感兴趣。那么ta一定会给你安排进面试pipeline。那么如何做到让 HR 主动联系你呢？
1、优秀的简历（经历）；
2、 LinkedIn Allstar；
3、Hackathon，Hackerrank 等活动／平台比较出众；
4.、从有面试的人手里获得 HR 的Email，主动和 HR 联系，毛遂自荐。

1和4结合效果最好。推荐大家把简历写好，然后从你周围面试的朋友那里要到 HR 联系方式，然后毛遂自己。

主动联系HR：
前文说到，能直接和 HR 联系是最好的。简单粗暴的方法是，从朋友那里要到 HR 的联系方式，主动发 Email 过去，自我描述外加简历。通常 HR 都会很快的回复你。

标题可以用：Strong Background Candidate You Might be Interested.
内容：简单介绍一下自己，和自己做过的proj。感觉和贵公司方向／产品／文化很match。
附件：简历

最好是直接联系校园招聘的 HR。HR的 level 和 focus 有很多，有些是专门招聘大牛的，工资，面试等都是单独谈的。有些是面对New Grad。有些面对普通跳槽的。有些公司HR是跟组的，比如Apple，某组的hr专门为这个组来找人。

通常情况下，如果HR认为你不match，会给你推荐给你对应level的HR／别的组的HR。

电面：
电面“通常”比Onsite简单，但是这个“通常”在Google Uber等“比较火”的公司这里不适用。Google的面经可以说“深不见底”，所以如果你是aim the top的话，还是推荐把题目做到融会贯通。

Onsite：
个人感觉onsite没有必然比电面难或者简单。出什么题，随机性很大。一个面试官大概有准备的题会有三五道，ta通常从自己熟悉的三五道题里出题来考你。
考核的内容是：

对问题的抽象和理解：这里期待你回答的内容是：”这道题可以抽象成拓扑排序，有些步骤需要在其他步骤之前执行，如果没有形成cycle那么整个就能完成。” 能够庖丁解牛的把这道题的本质分析清楚，剩下的就是实现了。当然，有些题没有见过，猛一看并不能说出个一二三来，那么就需要和面试官沟通了。

沟通能力：如何同面试官沟通？遇到一个没有见过的题，或者遇到写到一半写不下去卡了，这时候就需要“试探”面试官了。假如遇到一个有关比较大小的题，你不会，你总能想到 1排序 2DP 3divide conquer 那么你就说，目前我有几个不成熟的想法：1，2，3. 但是不确定哪个更合适，你怎么看？一个通情达理的面试官立刻就理解了，他会说，可以从排序试试。这里的核心思想是，不要不会就不说话，要去旁敲侧击试探性的提出几个假设，看面试官怎么回答。

Coding：和面试官“商量”的差不多，确定了思路，就可以开始写了。写代码其实没什么说的，刷题都刷够了。这里的建议是，白板写代码最好自己带笔，我面试都是自己带“粗细程度为fine的黑红蓝绿白板笔”（amazon买的），因为细一点的笔方便我写的清楚，节约白板空间，减少涂抹，清晰好看，和面试官讲自己代码时候用另一种颜色，清晰明了。

再有就是代码风格“努力让每个函数在20行之内”，能单独写成一个函数的尽量单独写出来，因为白板都是长宽的，竖着写得多了再拐弯就不好看，容易出错。比如
isGraphVerticallySymmetric()

Given a list of dots, return true iff the graph in the dot can form a vertically symmetric graph.

    EX:
    0 0 1 0 1
    0 0 0 1 0
    0 0 0 1 0
    0 0 1 0 1
    return true;

    0 1 0 1 0
    0 1 1 0 0
    return false;

分析：

For each x, find all it’s y and put it into a list. HashMap<Integer, List<Integer>>
For each x, calculate its list of y’s symmetric middle point.
If pre_middle_point != cur_middle_point return false.

那么分析中可以看出需要两个独立的函数，结构如下：

    isGraphVerticallySymmetric()
        preProcessGraphToMap()
        calculateAndCompareMiddlePoint()
            calculateMidPointOfList()

而isGraphVerticallySymmetric()分别调用这两个函数就能完成判断。写calculateAndCompareMiddlePoint()中发现可以单独再写一个calculate的函数，compare比较简单就在calculate函数之后做判断即可。[这一题挺不错的，建议大家自己写写加深理解]。

那么白板上应该有四个函数，每个函数都不会很长，逻辑清晰，代码明了。(optional)代码很好地写完之后，还有时间有思路的话，可以口头聊一聊一些比较有创意的解法，展现智力优越性。

总结：好的面试过程就像给一个不会这道题的学生讲课一样。要想办法十分清晰的给对方讲懂。如果有不明白的地方就多沟通，这样就算最坏结果你没有完整的写出代码，那么面试官也会觉得你思路清晰逻辑正确，虽然代码能力欠佳。给你一个中等评分。尽量不要获得差评。

看完了？留个评分呗？

[1人评了分，平均: 4/5]