TreeviewCopyright © aleen42 all right reserved, powered by aleen42

Google Interview University - 一套完整的学习手册帮助自己准备 Google 的面试 Back

xitu

这是?

这是我为了从 web 开发者(自学、非计算机科学学位)蜕变至 Google 软件工程师所制定的计划,其内容历时数月。

白板上编程 ———— 来自 HBO 频道的剧集,“硅谷”

这一长列表是从 Google 的指导笔记 中萃取出来并进行扩展。因此,有些事情你必须去了解一下。我在列表的底部添加了一些额外项,用于解决面试中可能会出现的问题。这些额外项大部分是来自于 Steve Yegge 的“得到在 Google 工作的机会”。而在 Google 指导笔记的逐字间,它们有时也会被反映出来。

为何要用到它?

我一直都是遵循该计划去准备 Google 的面试。自 1997 年以来,我一直从事于 web 程序的构建、服务器的构建及创业型公司的创办。对于只有着一个经济学学位,而不是计算机科学学位(CS degree)的我来说,在职业生涯中所取得的都非常成功。然而,我想在 Google 工作,并进入大型系统中,真正地去理解计算机系统、算法效率、数据结构性能、低级别编程语言及其工作原理。可一项都不了解的我,怎么会被 Google 所应聘呢?

当我创建该项目时,我从一个堆栈到一个堆都不了解。那时的我,完全不了解 Big-O 、树,或如何去遍历一个图。如果非要我去编写一个排序算法的话,我只能说我所写的肯定是很糟糕。一直以来,我所用的任何数据结构都是内建于编程语言当中。至于它们在背后是如何运作,对此我一概不清楚。此外,以前的我并不需要对内存进行管理,最多就只是在一个正在执行的进程抛出了“内存不足”的错误后,采取一些权变措施。而在我的编程生活中,也甚少使用到多维数组,可关联数组却成千上万。而且,从一开始到现在,我都还未曾自己实现过数据结构。

就是这样的我,在经过该学习计划后,已然对被 Google 所雇佣充满信心。这是一个漫长的计划,以至于花费了我数月的时间。若您早已熟悉大部分的知识,那么也许能节省大量的时间。

如何使用它

下面所有的东西都只是一个概述。因此,你需要由上而下逐一地去处理它。

在学习过程中,我是使用 GitHub 特殊的语法特性 markdown flavor 去检查计划的进展,包括使用任务列表。

  • [x] 创建一个新的分支,以使得你可以像这样去检查计划的进展。直接往方括号中填写一个字符 x 即可:[x]

更多关于 Github-flavored markdown 的详情

拥有一名 Googler 的心态

把一个(或两个)印有“future Googler”的图案打印出来,并用你誓要成功的眼神盯着它。

future Googler sign

我得到了工作吗?

我还没去应聘。

因为我离完成学习(完成该疯狂的计划列表)还需要数天的时间,并打算在下周开始用一整天的时间,以编程的方式去解决问题。当然,这将会持续数周的时间。然后,我才通过使用在二月份所得到的一个介绍资格,去正式应聘 Google(没错,是二月份时就得到的)。

感谢 JP 的这次介绍。

跟着我的脚步

目前我仍在该计划的执行过程中,如果你想跟随我脚步去学习的话,可以登进我在 GoogleyAsHeck.com 上所写的博客。

下面是我的联系方式:

John Washam - Google Interview University

不要妄自菲薄

  • Google 的工程师都是才智过人的。但是,就算是工作在 Google 的他们,仍然会因为觉得自己不够聪明而感到一种不安。
  • 天才程序员的神话

关于 Google

相关视频资源

部分视频只能通过在 Coursera、Edx 或 Lynda.com class 上注册登录才能观看。这些视频被称为网络公开课程(MOOC)。即便是免费观看,部分课程可能会由于不在时间段内而无法获取。因此,你需要多等待几个月。

很感谢您能帮我把网络公开课程的视频链接转换成公开的视频源,以代替那些在线课程的视频。此外,一些大学的讲座视频也是我所青睐的。

面试过程 & 通用的面试准备

为你的面试选择一种语言

在这,我就以下话题写一篇短文 —— 重点:为在 Google 的面试选择一种语言

在大多数公司的面试当中,你可以在编程这一环节,使用一种自己用起来较为舒适的语言去完成编程。但在 Google,你只有三种固定的选择:

  • C++
  • Java
  • Python

有时你也可以使用下面两种,但需要事先查阅说明。因为,说明中会有警告:

  • JavaScript
  • Ruby

你需要对你所选择的语言感到非常舒适且足够了解。

更多关于语言选择的阅读:

在此查看相关语言的资源

由于,我正在学习C、C++ 和 Python。因此,在下面你会看到部分关于它们的学习资料。相关书籍请看文章的底部。

在你开始之前

该列表已经持续更新了很长的一段时间,所以,我们的确很容易会对其失去控制。

这里列出了一些我所犯过的错误,希望您不要重滔覆辙。

1. 你不可能把所有的东西都记住

就算我查看了数小时的视频,并记录了大量的笔记。几个月后的我,仍然会忘却其中大部分的东西。所以,我翻阅了我的笔记,并将可回顾的东西制作成抽认卡(flashcard)(请往下看)

2. 使用抽认卡

为了解决善忘的问题,我制作了一些关于抽认卡的页面,用于添加两种抽认卡:正常的及带有代码的。每种卡都会有不同的格式设计。

而且,我还以移动设备为先去设计这些网页,以使得在任何地方的我,都能通过我的手机及平板去回顾知识。

你也可以免费制作属于你自己的抽认卡网站:

  • 抽认卡页面的代码仓库
  • 我的抽认卡数据库:有一点需要记住的是,我做事有点过头,以至于把卡片都覆盖到所有的东西上。从汇编语言和 Python 的细枝末节,乃至到机器学习和统计都被覆盖到卡片上。而这种做法,对于 Google 的要求来说,却是多余。

在抽认卡上做笔记: 若你第一次发现你知道问题的答案时,先不要急着把其标注成“已懂”。你需要做的,是去查看一下是否有同样的抽认卡,并在你真正懂得如何解决问题之前,多问自己几次。重复地问答可帮助您深刻记住该知识点。

3. 回顾,回顾,回顾

我留有一组 ASCII 码表、OSI 堆栈、Big-O 记号及更多的小抄纸,以便在空余的时候可以学习。

每编程半个小时就要休息一下,并去回顾你的抽认卡。

4. 专注

在学习的过程中,往往会有许多令人分心的事占据着我们宝贵的时间。因此,专注和集中注意力是非常困难的。

你所看不到的

由于,这个巨大的列表一开始是作为我个人从 Google 面试指导笔记所形成的一个事件处理列表。因此,有一些我熟悉且普遍的技术在此都未被谈及到:

  • SQL
  • Javascript
  • HTML、CSS 和其他前端技术

日常计划

部分问题可能会花费一天的时间去学习,而部分则会花费多天。当然,有些学习并不需要我们懂得如何实现。

因此,每一天我都会在下面所列出的列表中选择一项,并查看相关的视频。然后,使用以下的一种语言去实现:

  • C —— 使用结构体和函数,该函数会接受一个结构体指针 * 及其他数据作为参数。
  • C++ —— 不使用内建的数据类型。
  • C++ —— 使用内建的数据类型,如使用 STL 的 std::list 来作为链表。
  • Python —— 使用内建的数据类型(为了持续练习 Python),并编写一些测试去保证自己代码的正确性。有时,只需要使用断言函数 assert() 即可。

此外,你也可以使用 Java 或其他语言。以上只是我的个人偏好而已。

为何要在这些语言上分别实现一次?

因为可以练习,练习,练习,直至我厌倦它,并完美地实现出来。(若有部分边缘条件没想到时,我会用书写的形式记录下来并去记忆)

因为可以在纯原生的条件下工作(不需垃圾回收机制的帮助下,分配/释放内存(除了 Python))

因为可以利用上内建的数据类型,以使得我拥有在现实中使用内建工具的经验(在生产环境中,我不会去实现自己的链表)

就算我没有时间去每一项都这么做,但我也会尽我所能的。

在这里,你可以查看到我的代码:

你不需要记住每一个算法的内部原理。

在一个白板上写代码,而不要直接在计算机上编写。在测试完部分简单的输入后,到计算机上再测试一遍。

必备知识

算法复杂度 / Big-O / 渐进分析法

如果部分课程过于学术性,你可直接跳到文章底部,去查看离散数学的视频以获取相关背景知识。

数据结构

数组(Arrays)

  • 实现一个可自动调整大小的动态数组。
  • 介绍:
  • 实现一个动态数组(可自动调整大小的可变数组):
    • 练习使用数组和指针去编码,并且指针是通过计算去跳转而不是使用索引
    • 通过分配内存来新建一个原生数据型数组
      • 可以使用 int 类型的数组,但不能使用其语法特性
      • 从大小为16或更大的数(使用2的倍数 —— 16、32、64、128)开始编写
    • size() —— 数组元素的个数
    • capacity() —— 可容纳元素的个数
    • is_empty()
    • at(index) —— 返回对应索引的元素,且若索引越界则愤然报错
    • push(item)
    • insert(index, item) —— 在指定索引中插入元素,并把后面的元素依次后移
    • prepend(item) —— 可以使用上面的 insert 函数,传参 index 为 0
    • pop() —— 删除在数组末端的元素,并返回其值
    • delete(index) —— 删除指定索引的元素,并把后面的元素依次前移
    • remove(item) —— 删除指定值的元素,并返回其索引(即使有多个元素)
    • find(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引,若未找到则返回 -1
    • resize(new_capacity) // 私有函数
      • 若数组的大小到达其容积,则变大一倍
      • 获取元素后,若数组大小为其容积的1/4,则缩小一半
  • 时间复杂度
    • 在数组末端增加/删除、定位、更新元素,只允许占 O(1) 的时间复杂度(平摊(amortized)去分配内存以获取更多空间)
    • 在数组任何地方插入/移除元素,只允许 O(n) 的时间复杂度
  • 空间复杂度
    • 因为在内存中分配的空间邻近,所以有助于提高性能
    • 空间需求 = (大于或等于 n 的数组容积)* 元素的大小。即便空间需求为 2n,其空间复杂度仍然是 O(n)

链表(Linked Lists)

  • 介绍:
  • C 代码(视频)
    • 并非看完整个视频,只需要看关于节点结果和内存分配那一部分即可
  • 链表 vs 数组:
  • 为什么你需要避免使用链表(视频)
  • 的确:你需要关于“指向指针的指针”的相关知识:(因为当你传递一个指针到一个函数时,该函数可能会改变指针所指向的地址)该页只是为了让你了解“指向指针的指针”这一概念。但我并不推荐这种链式遍历的风格。因为,这种风格的代码,其可读性和可维护性太低。
  • 实现(我实现了使用尾指针以及没有使用尾指针这两种情况):
    • size() —— 返回链表中数据元素的个数
    • empty() —— 若链表为空则返回一个布尔值 true
    • value_at(index) —— 返回第 n 个元素的值(从0开始计算)
    • push_front(value) —— 添加元素到链表的首部
    • pop_front() —— 删除首部元素并返回其值
    • push_back(value) —— 添加元素到链表的尾部
    • pop_back() —— 删除尾部元素并返回其值
    • front() —— 返回首部元素的值
    • back() —— 返回尾部元素的值
    • insert(index, value) —— 插入值到指定的索引,并把当前索引的元素指向到新的元素
    • erase(index) —— 删除指定索引的节点
    • value_n_from_end(n) —— 返回倒数第 n 个节点的值
    • reverse() —— 逆序链表
    • remove_value(value) —— 删除链表中指定值的第一个元素
  • 双向链表

堆栈(Stack)

队列(Queue)

  • 使用队列 —— 先进先出(视频)
  • 队列(视频)
  • 原型队列/先进先出(FIFO)
  • 优先级队列(视频)
  • 使用含有尾部指针的链表来实现:
    • enqueue(value) —— 在尾部添加值
    • dequeue() —— 删除最早添加的元素并返回其值(首部元素)
    • empty()
  • 使用固定大小的数组实现:
    • enqueue(value) —— 在可容的情况下添加元素到尾部
    • dequeue() —— 删除最早添加的元素并返回其值
    • empty()
    • full()
  • 花销:
    • 在糟糕的实现情况下,使用链表所实现的队列,其入列和出列的时间复杂度将会是 O(n)。因为,你需要找到下一个元素,以致循环整个队列
    • enqueue:O(1)(平摊(amortized)、链表和数组 [探测(probing)])
    • dequeue:O(1)(链表和数组)
    • empty:O(1)(链表和数组)

哈希表(Hash table)

更多的知识

二分查找(Binary search)

按位运算(Bitwise operations)

树(Trees)

树 —— 笔记 & 背景

  • 系列:基本树(视频)
  • 系列:树(视频)
  • 基本的树形结构
  • 遍历
  • 操作算法
  • BFS(广度优先检索,breadth-first search)
    • MIT(视频)
    • 层序遍历(使用队列的 BFS 算法)
      • 时间复杂度: O(n)
      • 空间复杂度:
        • 最好情况: O(1)
        • 最坏情况:O(n/2)=O(n)
  • DFS(深度优先检索,depth-first search)
    • MIT(视频)
    • 笔记:
      • 时间复杂度:O(n)
      • 空间复杂度:
        • 最好情况:O(log n) - 树的平均高度
        • 最坏情况:O(n)
    • 中序遍历(DFS:左、节点本身、右)
    • 后序遍历(DFS:左、右、节点本身)
    • 先序遍历(DFS:节点本身、左、右)

二叉查找树(Binary search trees):BSTs

堆(Heap) / 优先级队列(Priority Queue) / 二叉堆(Binary Heap)

字典树(Tries)

平衡查找树(Balanced search trees)

  • 掌握至少一种平衡查找树(并懂得如何实现):
  • “在各种平衡查找树当中,AVL 树和2-3树已经成为了过去,而红黑树(red-black trees)看似变得越来越受人青睐。这种令人特别感兴趣的数据结构,亦称伸展树(splay tree)。它可以自我管理,且会使用轮换来移除任何访问过根节点的 key。” —— Skiena
  • 因此,在各种各样的平衡查找树当中,我选择了伸展树来实现。虽然,通过我的阅读,我发现在 Google 的面试中并不会被要求实现一棵平衡查找树。但是,为了胜人一筹,我们还是应该看看如何去实现。在阅读了大量关于红黑树的代码后,我才发现伸展树的实现确实会使得各方面更为高效。
    • 伸展树:插入、查找、删除函数的实现,而如果你最终实现了红黑树,那么请尝试一下:
    • 跳过删除函数,直接实现搜索和插入功能
  • 我希望能阅读到更多关于 B 树的资料,因为它也被广泛地应用到大型的数据库当中。
  • 自平衡二叉查找树

  • AVL 树

    • 实际中:我能告诉你的是,该种树并无太多的用途,但我能看到有用的地方在哪里:AVL 树是另一种平衡查找树结构。其可支持时间复杂度为 O(log n) 的查询、插入及删除。它比红黑树严格意义上更为平衡,从而导致插入和删除更慢,但遍历却更快。正因如此,才彰显其结构的魅力。只需要构建一次,就可以在不重新构造的情况下读取,适合于实现诸如语言字典(或程序字典,如一个汇编程序或解释程序的操作码)。
    • MIT AVL 树 / AVL 树的排序(视频)
    • AVL 树(视频)
    • AVL 树的实现(视频)
    • 分离与合并
  • 伸展树

    • 实际中:伸展树一般用于缓存、内存分配者、路由器、垃圾回收者、数据压缩、ropes(字符串的一种替代品,用于存储长串的文本字符)、Windows NT(虚拟内存、网络及文件系统)等的实现。
    • CS 61B:伸展树(Splay trees)(视频)
    • MIT 教程:伸展树(Splay trees):
      • 该教程会过于学术,但请观看到最后的10分钟以确保掌握。
      • 视频
  • 2-3查找树

  • 2-3-4树 (亦称2-4树)

  • B 树

  • 红黑树

N 叉树(K 叉树、M 叉树)

  • 注意:N 或 K 指的是分支系数(即树的最大分支数):
    • 二叉树是一种分支系数为2的树
    • 2-3树是一种分支系数为3的树
  • K 叉树

排序(Sorting)

图(Graphs)

图论能解决计算机科学里的很多问题,所以这一节会比较长,像树和排序的部分一样。

可以从 Skiena 的书(参考下面的书推荐小节)和面试书籍中学习更多关于图的实践。

更多知识

递归(Recursion)

动态规划(Dynamic Programming)

组合(Combinatorics) (n 中选 k 个) & 概率(Probability)

NP, NP-完全和近似算法

缓存(Cache)

进程(Processe)和线程(Thread)

系统设计以及可伸缩性,要把软硬件的伸缩性设计的足够好有很多的东西要考虑,所以这是个包含非常多内容和资源的大主题。需要花费相当多的时间在这个主题上。

系统设计、可伸缩性、数据处理

论文

测试

调度

  • 在操作系统中是如何运作的
  • 在操作系统部分的视频里有很多资料

实现系统例程

  • 理解你使用的系统 API 底层有什么
  • 你能自己实现它们么?

字符串搜索和操作


终面

这一部分有一些短视频,你可以快速的观看和复习大多数重要概念。

这对经常性的巩固很有帮助。

综述:

  • 2-3 分钟的短视频系列 (23 个)
  • 2-5 分钟的短视频系列 - Michael Sambol (18 个):

排序:

书籍

Google Coaching 里提到的

阅读并做练习:

一旦你理解了每日计划里的所有内容,就去读上面所列的书并完成练习,然后开始读下面所列的书并做练习,之后就可以开始实战写代码了(本文再往后的部分)

首先阅读:

然后阅读 (这本获得了很多推荐, 但是不在 Google coaching 的文档里):

附加书单

这些没有被 Google 推荐阅读,不过我因为需要这些背景知识所以也把它们列在了这里。

如果你有时间

编码练习和挑战

一旦你学会了理论基础,就应该把它们拿出来练练。 尽量坚持每天做编码练习,越多越好。

编程问题预备:

编码练习平台:

当你临近面试时

你的简历

当面试来临的时候

随着下面列举的问题思考下你可能会遇到的 20 个面试问题

每个问题准备 2-3 种回答

准备点故事,不要只是摆一些你完成的事情的数据,相信我,人人都喜欢听故事

  • 你为什么想得到这份工作?
  • 你解决过的最有难度的问题是什么?
  • 面对过的最大挑战是什么?
  • 见过的最好或者最坏的设计是怎么样的?
  • 对某项 Google 产品提出改进建议。
  • 你作为一个个体同时也是团队的一员,如何达到最好的工作状态?
  • 你的什么技能或者经验是你的角色中不可或缺的?为什么?
  • 你在某份工作或某个项目中最享受的是什么?
  • 你在某份工作或某个项目中面临过的最大挑战是什么?
  • 你在某份工作或某个项目中遇到过的最蛋疼的 Bug 是什么样的?
  • 你在某份工作或某个项目中学到了什么?
  • 你在某份工作或某个项目中哪些地方还可以做的更好?

问面试官的问题

我会问的一些:(可能我已经知道了答案但我想听听面试官的看法或者了解团队的前景):

  • 团队多大规模?
  • 开发周期是怎样的? 会使用瀑布流/极限编程/敏捷开发么?
  • 经常会为 deadline 加班么? 或者是有弹性的?
  • 团队里怎么做技术选型?
  • 每周平均开多少次会?
  • 你觉得工作环境有助于员工集中精力吗?
  • 目前正在做什么工作?
  • 喜欢这些事情吗?
  • 工作期限是怎么样的?

当你获得了梦想的职位

我还能说些什么呢,恭喜你!

坚持继续学习。

得到这份工作只是一个开始。

下面的内容都是可选的。这些是我的推荐,不是 Google 的。

通过学习这些内容,你将会得到更多的有关 CS 的概念,并将为所有的软件工程工作做更好的准备。

附加的学习

Unicode

字节顺序

Emacs and vi(m)

Unix 命令行工具

  • 下列内容中的优秀工具由的 Yegge 推荐,Yegge 目前致力于 Amazon 人事招聘处。
  • bash
  • cat
  • grep
  • sed
  • awk
  • curl or wget
  • sort
  • tr
  • uniq
  • strace
  • tcpdump

信息资源 (视频)

奇偶校验位 & 汉明码 (视频)

系统熵值(系统复杂度)

密码学

压缩

网络 (视频)

计算机安全

释放缓存

并行/并发编程

设计模式

信息传输, 序列化,和队列化的系统

快速傅里叶变换

布隆过滤器

van Emde Boas 树

更深入的数据结构

跳表

网络流

不相交集 & 联合查找

快速处理数学

树堆(Treap)

线性规划(Linear Programming)(视频)

几何:凸包(Geometry, Convex hull)(视频)

离散数学

  • 查看下面的视频:(这里没看到视频= =)

机器学习(Machine Learning)

Go 语言


一些主题的额外内容

我为前面提到的某些主题增加了一些额外的内容,之所以没有直接添加到前面,是因为这样很容易导致某个主题内容过多。毕竟你想在本世纪找到一份工作,对吧?

视频系列

坐下来享受一下吧。"netflix and skill" :P

计算机科学课程

Empty Comments
Sign in GitHub

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.