Skip to content

Latest commit

 

History

History
1901 lines (1579 loc) · 133 KB

File metadata and controls

1901 lines (1579 loc) · 133 KB

编程面试大学

原先我为了成为一个软件工程师而建立这份简单的学习主题清单, 但这份清单随着时间的推移而膨胀成今天这样。在做完这份清单上的每个目标后,我成为了 Amazon 的软件开发工程师! 你或许不需要像我一样学习这么多。但是,让你成为一位称职工程师所需要的知识都在这里了。

我每天自学8~12小时,这样持续了好几个月。这是我的故事:为什么我为了 Google 面试而自学了8个月

在这份清单内的主题会让你拥有足够的知识去面对几乎每家软件公司的技术面试,包括科技巨头:Amazon、Facebook、Google,以及 Microsoft。

祝你好运!

这是?

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

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

这份清单适用于 新手软件工程师,或者想从软件/网站开发转向软件工程(需要计算机科学知识)的人员。如果你有多年的经验,并且声称拥有多年的软件工程经验,并且期待一次更艰难的面试。

如果你具有多年的软件/网页开发经验,请注意,大型软件公司(例如 Google,Amazon,Facebook 和 Microsoft)将软件工程视为不同于软件/网页开发,并且它们需要计算机科学知识。

如果你想成为可靠性工程师或运维工程师,请从可选列表(网络,安全)中学习更多。


目录

---------------- 下面的内容是可选的 ----------------


为何要用到它?

当我开始这个项目时,我不知道堆和栈的区别,不了解时间复杂度(Big-O)、树,或如何去遍历一个图。如果非要我去编写一个排序算法的话,我只能说我所写的肯定是很糟糕。一直以来,我所用的任何数据结构都是内建于编程语言当中。至于它们在背后是如何运作,对此我一概不清楚。此外,以前的我并不需要对内存进行管理,最多就只是在一个正在执行的进程抛出了“内存不足”的错误后,才会去找解决方法。在我的编程生涯中,虽然我有用过多维数组,也用过关联数组成千上万次,但我从来没有自己实现过数据结构。

这是一个漫长的计划,以至于花费了我数月的时间。若你早已熟悉大部分的知识,那么也许能节省大量的时间。

如何使用它

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

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

如果你不想使用 Git

在该页面上,单击顶部附近的 Code 按钮,然后单击“Download ZIP”。解压文件,就可以使用文本文件了。

如果你打开一个代码编辑器,你会看到所有格式都很好。

How to download the repo as a zip file

如果你不介意 Git

  1. 通过单击 Fork 按钮来 fork GitHub 仓库:https://github.com/jwasham/coding-interview-university

    Fork the GitHub repo

  2. 克隆项目到本地:

    git clone [email protected]:<your_github_username>/coding-interview-university.git
    cd coding-interview-university
    git checkout -b progress
    git remote add jwasham https://github.com/jwasham/coding-interview-university
    git fetch --all
  3. 在你完成了一些修改后,在框框中打 x:

    git add .
    git commit -m "Marked x"
    git rebase jwasham/main
    git push --set-upstream origin progress
    git push --force

不要觉得自己不够聪明

相关视频资源

部分视频只能通过在 Coursera 或者 Edx 课程上注册登录才能观看。这些视频被称为网络公开课程(MOOC)。有时候某些课程需要等待好几个月才能获取,这期间你无法观看这些课程的影片。

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

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

为你的面试选择一种语言

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

  • C++
  • Java
  • Python

你也可以使用下面两种编程语言,但可能会有某些限制,你需要事先查明:

  • JavaScript
  • Ruby

我之前写过一篇关于在面试时选择编程语言的文章:为编程面试选择一种语言

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

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

在此查看相关语言的资源

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

书单

为了节省你的时间,以下是比我使用过的更缩减的书单。

面试准备

如果你有额外的时间:

选择以下之一:

编程语言精选

你需要选择面试语言(请参见上文)。

这是我按语言给出的建议。我没有所有语言的资源,欢迎贡献。

如果你通读其中之一,你应该具备了开始解决编程问题所需的所有数据结构和算法知识。除非你需要复习,否则你可以跳过此项目中的所有视频讲座

额外编程语言的精选资源

C++

我没有读过这两本书,但是它们颇受好评,作者是 Sedgewick,他非常厉害。

如果你有更好的 C++ 书籍,请告诉我。我正在搜集全面的资源。

Java

或者:

  • Java 数据结构和算法
    • 作者:Goodrich、Tamassia、Goldwasser
    • 用作 UC Berkeley 的 CS 入门课程的可选教材
    • 请参阅下面有关 Python 版本的我的读书报告,这本书涵盖了相同的主题

Python

在你开始之前

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

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

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

就算我观看了数小时的视频,并记录了大量的笔记,几个月后的我,仍然会忘却其中大部分的东西。所以,我花了3天翻阅我的笔记,并制作成抽认卡(flashcard)帮助我复习:

请阅读以下的文章以免重蹈覆辙:

记住计算机科学知识

有人推荐给我的课程(但我还沒看过):学习如何学习

2. 使用抽认卡

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

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

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

有一点需要记住的是,我做事有点过头,以至于卡片都覆盖到所有的东西上,从汇编语言和 Python 的细枝末节,到机器学习和统计都被覆盖到卡片上。而这种做法,对于要求来说是多余的。

在抽认卡上做笔记: 若你第一次发现你知道问题的答案时,先不要急着把其标注成“已知”。反复复习这张抽认卡,直到每次都能答对后才是真正学会了这个问题。反复地问答可帮助你深刻记住该知识点。

这里有个替代我抽认卡的网站 Anki,很多人向我推荐过它。这个网站用同一个字卡重复出现的方式让你牢牢地记住知识。这个网站非常容易使用,支持多平台,并且有云端同步功能。在 iOS 平台上收费25美金,其他平台免费。

这是我用 Anki 这个网站里的格式所储存的抽认卡资料库: ankiweb.net/shared/info/25173560 (感谢 @xiewenya

3. 复习,复习,再复习

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

编程累了就休息半个小时,并去复习你的抽认卡。

4. 专注

在学习的过程中,往往会有许多令人分心的事占据着我们宝贵的时间。因此,专注和集中注意力是非常困难的。放点纯音乐能帮上一些忙。

没有包含的内容

有一些熟悉且普遍的技术在此未被谈及到:

  • 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)

更多的知识

树(Trees)

排序(Sorting)

总结一下,这是15种排序算法的可视化表示。如果你需要有关此主题的更多详细信息,请参阅“一些主题的额外内容”中的“排序”部分。

图(Graphs)

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

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

更多知识

如果你需要有关此主题的更多详细信息,请参阅“一些主题的额外内容”中的“字符串匹配”部分。

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

如果你已经拥有了4年以上的编程经验,那你可以来看看有关系统设计的问题


终面

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

编程问题练习

现在你已经了解了上面所有的计算机科学主题,是时候练习回答编程问题了。

编程问题的实践并不是要记住编程问题的答案

为什么需要练习编程问题:

  • 快速识别问题,以及如何应用正确的数据结构及算法
  • 收集问题的要求
  • 像在面试中一样谈论问题
  • 在白板或纸上而非计算机上编码
  • 计算解决方案的时间和空间的复杂性
  • 测试你的解决方案

这里有个很棒的入门教学,内容是如何在面试中有条不紊,并且有互动沟通地解决问题。这种能力可以从面试书籍中获得,但我觉得这个也很棒:算法设计画布

家里没有白板?那讲得通。我是一个怪人,有一个很大的白板。从白板商店买了一个大的绘图板,而不是白板。你可以坐在沙发上练习。这是我的“沙发白板”。我在照片中添加了笔以便进行缩放。如果你使用笔,则希望可以擦除。快速变得凌乱。我用铅笔和橡皮擦。

我的沙发白板

补充:

阅读并练习编程问题(按此顺序)

请参阅上方的书单

编程练习和挑战

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

编码面试问题视频:

编码练习平台:

语言学习网站,附带编码挑战:

编码挑战项目:

模拟面试:

当你临近面试时

你的简历

  • 请参阅“破解编码面试”和“编程面试的背面”中的建立准备项。

当面试来临的时候

随着下面列举的问题思考下你可能会遇到的 20 个面试问题,每个问题准备 2-3 种回答。准备点故事,不要只是摆一些你完成的事情的数据,相信我,人人都喜欢听故事。

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

问面试官的问题

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

当你获得了梦想的职位

恭喜你!

继续学习。

活到老,学到老。


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

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

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

额外书籍

你可以从以下的书单挑选你有兴趣的主题来研读。
  • UNIX环境高级编程

    • 老,但却很棒
  • Linux 命令行大全

    • 现代选择
  • TCP-IP详解系列

  • Head First 设计模式

    • 设计模式入门介绍
  • 设计模式:可复用面向对象软件的基础

    • 也被称为“四人帮”(Gang of Four(GOF))
    • 经典设计模式书籍
  • Linux 和 UNIX 系统管理技术手册(第五版)

  • 算法设计手冊(Skiena)

    • 作为复习以及问题辨别
    • 这本书中算法的部分难度已经超过面试会出现的
    • 本书分为两个部分:
      • 数据结构和算法课本
        • 优点:
          • 跟其他算法课本一样是个很棒的复习素材
          • 包含作者以往解决工业及学术上问题的经验的故事
          • 含C语言代码示例
        • 缺点:
          • 某些地方跟《算法导论》(CLRS)一样艰深,但在某些主题,算法导论或许是更好的选择。
          • 第7、8、9章有点难以消化,因为某些地方并没有解释得很清楚,或者根本上我就是个学渣
          • 别会错意了,我很喜欢 Skiena 的教学方法以及他的风格。
      • 算法目录:
        • 这个部分是买这本书的最大原因
        • 我即将着手进行这部分,一旦完成这部分我会再更新上来
    • 可以在 kindle 上租
    • 解答:
    • 勘误表
  • 编程卓越之道(第一卷):深入理解计算机

    • 该书于2004年出版,虽然有些过时,但是对于简单了解计算机而言,这是一个了不起的资源
    • 作者发明了高阶组合语言 HLA,所以提到,并且举了一些HLA的例子。里面没有用到很多,但都是很棒的组合语言的例子。
    • 这些章节值得阅读,为你提供良好的基础:
      • 第2章──数字表示
      • 第3章──二进制算术和位运算
      • 第4章──浮点表示
      • 第5章──字符表示
      • 第6章──内存组织和访问
      • 第7章──组合数据类型和内存对象
      • 第9章──CPU体系结构
      • 第10章──指令集架构
      • 第11章──内存体系结构和组织
  • 算法导论

    • 重要提示:读这本书的价值有限。本书很好地回顾了算法和数据结构,但不会教你如何编写良好的代码。你必须能够有效地编写一个不错的解决方案
    • 又称 CLR,有时是 CLRS,因为 Stein 最后才加入
  • 计算机体系结构:量化研究方法(第6版)

    • 更丰富、更新(2017年),但篇幅较长
  • 编程珠矶

    • 前几章介绍了解决编程问题(非常古老,甚至还用数据磁带)的巧妙解决方案,但这只是一个介绍。这是关于程序设计和体系结构的指南

附加学习

我把它们加进来是为了让你成为更全方位的软件工程师,并且留意一些技术以及算法,让你拥有更大的工具箱。

--

一些主题的额外内容

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

视频系列

坐下来享受一下吧。"netflix 和技能" :P

计算机科学课程

论文

LICENSE

CC-BY-SA-4.0