跳到主内容

plan

我的学习计划及完成情况汇总

大体是从/Google Interview University/ 中复制过来的, 但根据自己的兴趣增删了很多东西

TODO google介绍

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

为你的面试选择一种语言

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

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

  • C++
  • Java
  • Python

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

  • JavaScript
  • Ruby

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

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

在此查看相关语言的资源

3. 回顾,回顾,回顾

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

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

4. 专注

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

TODO 必备知识

算法复杂度 / 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 代码(视频)](https://www.youtube.com/watch?v=QN6FPiD0Gzo)
    • 并非看完整个视频,只需要看关于节点结果和内存分配那一部分即可
  • [ ] 链表 vs 数组:
  • [ ] [为什么你需要避免使用链表(视频)](https://www.youtube.com/watch?v=YQs6IC-vgmo)
  • [ ] 的确:你需要关于“指向指针的指针”的相关知识:(因为当你传递一个指针到一个函数时,该函数可能会改变指针所指向的地址)该页只是为了让你了解“指向指针的指针”这一概念。但我并不推荐这种链式遍历的风格。因为,这种风格的代码,其可读性和可维护性太低。
  • [ ] 实现(我实现了使用尾指针以及没有使用尾指针这两种情况):
    • [ ] 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)

优先级队列[33%]

  • [X] 二叉堆的实现
  • [ ] 复杂度分析(算法导论)
    • [ ] insert
    • [ ] top
    • [ ] pop
    • [ ] build
  • [ ] 堆排序的实现

哈希表(Hash table)

按位运算(Bitwise operations)

树 —— 笔记 & 背景

  • 基本的树形结构
  • 遍历
  • 操作算法
  • 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)

DONE 平衡查找树(Balanced search trees)

排序(Sorting)

图(Graphs)

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

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

更多知识

论文

测试

调度

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

实现系统例程

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

终面

    这一部分有一些短视频,你可以快速的观看和复习大多数重要概念。
    这对经常性的巩固很有帮助。

书籍

Google Coaching 里提到的

阅读并做练习:

  • [ ] 算法设计手册 (Skiena)

    read and do exercises from the books below. Then move to coding challenges (further down below) 一旦你理解了每日计划里的所有内容,就去读上面所列的书并完成练习,然后开始读下面所列的书并做练习,之后就可以开始实战写代码了(本文再往后的部分)

首先阅读: - [ ] [Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition](http://www.wiley.com/WileyCDA/WileyTitle/productCd-047012167X.html)

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

附加书单

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

如果你有时间

编码练习和挑战

你的简历

当面试来临的时候

    随着下面列举的问题思考下你可能会遇到的 20 个面试问题
    每个问题准备 2-3 种回答
    准备点故事,不要只是摆一些你完成的事情的数据,相信我,人人都喜欢听故事
  • 你为什么想得到这份工作?
  • 你解决过的最有难度的问题是什么?
  • 面对过的最大挑战是什么?
  • 见过的最好或者最坏的设计是怎么样的?
  • 对某项 Google 产品提出改进建议。
  • 你作为一个个体同时也是团队的一员,如何达到最好的工作状态?
  • 你的什么技能或者经验是你的角色中不可或缺的?为什么?
  • 你在某份工作或某个项目中最享受的是什么?
  • 你在某份工作或某个项目中面临过的最大挑战是什么?
  • 你在某份工作或某个项目中遇到过的最蛋疼的 Bug 是什么样的?
  • 你在某份工作或某个项目中学到了什么?
  • 你在某份工作或某个项目中哪些地方还可以做的更好?

问面试官的问题

    我会问的一些:(可能我已经知道了答案但我想听听面试官的看法或者了解团队的前景):
  • 团队多大规模?
  • 开发周期是怎样的? 会使用瀑布流/极限编程/敏捷开发么?
  • 经常会为 deadline 加班么? 或者是有弹性的?
  • 团队里怎么做技术选型?
  • 每周平均开多少次会?
  • 你觉得工作环境有助于员工集中精力吗?
  • 目前正在做什么工作?
  • 喜欢这些事情吗?
  • 工作期限是怎么样的?

当你获得了梦想的职位

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

坚持继续学习。

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


*****************************************************************************************************
*****************************************************************************************************

下面的内容都是可选的。这些是我的推荐,不是 Google 的。
通过学习这些内容,你将会得到更多的有关 CS 的概念,并将为所有的软件工程工作做更好的准备。

*****************************************************************************************************
*****************************************************************************************************

附加的学习

释放缓存

并行/并发编程

设计模式

布隆过滤器

更深入的数据结构

跳表

网络流

快速处理数学

树堆 (Treap)

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

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

离散数学

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

机器学习(Machine Learning)

一些主题的额外内容

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

视频系列

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

注释