项目简介
算法面试圣经(俗称cc150)《Cracking the Coding Interview: 150 Programming Interview Questions and Solutions》。LeetCode上很多的题目都是来自这本书的。
这本书覆盖了后端开发知识体系的方方面面。(第六版)。官方给出的是Java版，这整理了第六版的Python实现。由于是个人的业余实现，可能存在错误。
本项目使用jupyter编写，导出markdown格式。这样既可以像阅读ppt一样浏览，也可以随时动手验证自己的想法。
使用指南
# 安装jupyter
pip3 install jupyter
# 进入项目下的jupter目录,启动jupyter服务器.访问地址http://localhost:8888/tree
jupyter notebook备注
- 链表节点的定义：
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None- 相关的公共放在了
jupyter/common目录，引入方式如下：
import os
import sys
sys.path.insert(0, os.path.abspath('./common'))第六版题目列表
| 序号 | 题目 | 描述 |
|---|---|---|
数组与字符串 |
||
| 1.1 | 判定字符是否唯一 | 实现一个算法,确定一个字符串的所有字符是否全都不同。假使不允许使用额外的数据结构,又该如何处理? |
| 1.2 | 判定是否互为字符重排 | 给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。 |
| 1.3 | URL化 | 编写一种方法,将字符串中的空格全部替换为 %20 。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的“真实”长度。(注:用 Java 实现的话,请使用字符数组实现,以便直接在数组上操作。) 示例: 输入: "Mr John Smith", 13 输出: "Mr%20John%20Smith" |
| 1.4 | 回文排列 | 给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。回文串不一定是字典当中的单词。 示例: 输入: Tact Coa 输出: True (排列有 "taco cat" 、 "atco cta" ,等等) |
| 1.5 | 一次编辑 | 字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。 示例: pale, ple -> true pales, pale -> true pale, bale -> true pale, bake -> false |
| 1.6 | 字符串压缩 | 利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串 aabcccccaaa 会变为 a2b1c5a3 。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a 至 z) |
| 1.7 | 旋转矩阵 | 给定一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节,编写一种方法,将图像旋转 90 度。不占用额外内存空间能否做到? |
| 1.8 | 零矩阵 | 编写一种算法,若 M × N 矩阵中某个元素为 0,则将其所在的行与列清零。 |
| 1.9 | 字符串轮转 | 假定有一种 isSubstring 方法,可检查一个单词是否为其他字符串的子串。给定两个字符串 s1 和 s2 ,请编写代码检查 s2 是否为 s1 旋转而成,要求只能调用一次isSubstring (比如, waterbottle 是 erbottlewat 旋转后的字符串)。 |
链表 |
||
| 2.1 | 移除重复节点 | 编写代码，移除未排序链表中的重复节点。 进阶： 如果不得使用临时缓冲区，该怎么解决？ |
| 2.2 | 返回l倒数第k个节点 | 实现一种算法，找出单向链表中倒数第k 个节点。 |
| 2.3 | 删除中间节点 | 实现一种算法，删除单向链表中间的某个节点（除了第一个和最后一个节点，不一定是中间节点），假定你只能访问该节点。 示例： 输入： 单向链表a->b->c->d->e->f 中的节点c 结果： 不返回任何数据，但该链表变为a->b->d->e->f |
| 2.4 | 分割链表 | 编写程序以x 为基准分割链表，使得所有小于x 的节点排在大于或等于x 的节点之前。如果链表中包含x，x 只需出现在小于x 的元素之前（如下所示）。分割元素x只需处于“右半部分”即可，其不需要被置于左右两部分之间。 示例： 输入：3 -> 5 -> 8-> 5 -> 10 -> 2 -> 1 [分节点为5] 输出：3 -> 1 -> 2 -> 10 -> 5-> 5 -> 8 |
| 2.5 | 链表求和 | 给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。 示例： 输入：(7-> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912 进阶：假设这些数位是正向存放的，请再做一遍。 示例： 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295 输出：9 -> 1 -> 2，即912 |
| 2.6 | 回文链表 | 编写一个函数，检查链表是否为回文。 |
| 2.7 | 链表相交 | 给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k 个节点与另一个链表的第j 个节点是同一节点（引用完全相同），则这两个链表相交。 |
| 2.8 | 环路检测 | 给定一个有环链表，实现一个算法返回环路的开头节点。有环链表的定义：在链表中某个节点的next 元素指向在它前面出现过的节点，则表明该链表存在环路。 示例： 输入：A -> B -> C -> D -> E -> C（C 节点出现了两次） 输出：C |
栈和队列 |
||
| 3.1 | 三合一 | 描述如何只用一个数组来实现三个栈。 |
| 3.2 | 栈的最小 | 请设计一个栈，除了pop 与push 函数，还支持min 函数，其可返回栈元素中的最小值。执行push、pop 和min 操作的时间复杂度必须为O(1)。 |
| 3.3 | 堆盘子 | 设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks 应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop 操作。 |
| 3.4 | 化栈为队 | 实现一个MyQueue 类，该类用两个栈来实现一个队列。 |
| 3.5 | 栈排序 | 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和isEmpty。 |
| 3.6 | 动物收容所 | 有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog 和dequeueCat。允许使用Java 内置的LinkedList 数据结构。 |
树与图 |
||
| 4.1 | 节点间通路 | 给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。 |
| 4.2 | 最小高度树 | 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。 |
| 4.3 | 特定深度节点链表 | 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为D，则会创建出D 个链表） |
| 4.4 | 检查平衡性 | 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过1。 |
| 4.5 | 合法二叉搜索树 | 实现一个函数，检查一棵二叉树是否为二叉搜索树。 |
| 4.6 | 后继者 | 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。可以假定每个节点都含有指向父节点的连接。 |
| 4.7 | 编译顺序 | 给你一系列项目（projects）和一系列依赖关系（依赖关系dependencies为一个链表，其中每个元素为两个项目的编组，且第二个项目依赖于第一个项目）。所有项目的依赖项必须在该项目被编译前编译。请找出可以使得所有项目顺利编译的顺序。如果没有合法的编译顺序，返回错误。 示例： 输入： projects: a, b, c, d, e, f dependencies: (a, d), (f, b), (b, d), (f, a), (d, c) 输出：f, e, a, b, d, c |
| 4.8 | 首个共同祖先 | 设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。 |
| 4.9 | 二叉搜索树序列 | 从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉树，输出所有可能生成此树的数组。 |
| 4.10 | 检查子树 | 你有两棵非常大的二叉树：T1，有几百万个节点；T2，有几百个节点。设计一个算法，判断T2 是否为T1 的子树。 如果T1 有这么一个节点n，其子树与T2 一模一样，则T2 为T1 的子树，也就是说，从节点n 处把树砍断，得到的树与T2 完全相同。 |
| 4.11 | 随机节点 | 你现在要从头开始实现一个二叉树类，该类除了插入（insert）、查找（find）和删除（delete）方法外，需要实现getRandomNode()方法用于返回树中的任意节点。该方法应该以相同的概率选择任意的节点。设计并实现getRandomNode 方法并解释如何实现其他方法。 |
| 4.12 | 求和路径 | 给定一棵二叉树，其中每个节点都含有一个整数数值（该值或正或负）。设计一个算法，打印节点数值总和等于某个给定值的所有路径。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下（只能从父节点指向子节点方向）。 |
位操作 |
||
| 5.1 | 插入 | 给定两个32 位的整数N 与M，以及表示比特位置的i 与j。编写一种方法，将M插入N，使得M从N 的第j 位开始，到第i 位结束。假定从j 位到i 位足以容纳M，也即若M = 10 011，那么j 和i 之间至少可容纳5 个位。例如，不可能出现j = 3 和i = 2 的情况，因为第3 位和第2 位之间放不下M。 示例： 输入：N = 10000000000, M = 10011, i = 2, j = 6 输出：N = 10001001100 |
| 5.2 | 二进制数转字符串 | 给定一个介于0 和1 之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32 位以内的二进制表示，则打印“ERROR”。 |
| 5.3 | 翻转数位 | 给定一个整数，你可以将一个数位从0 变为1。请编写一个程序，找出你能够获得的最长的一串1 的长度。 示例： 输入：1775（或者：11011101111） 输出：8 |
| 5.4 | 下一个数 | 给定一个正整数，找出与其二进制表达式中1 的个数相同且大小最接近的那两个数（一个略大，一个略小）。 |
| 5.5 | 调试 | 解释代码((n & (n-1)) == 0)的具体含义。 |
| 5.6 | 整数转换 | 编写一个函数，确定需要改变几个位才能将整数A 转成整数B。 示例： 输入：29（或者: 11101），15（或者: 01111） 输出：2 |
| 5.7 | 配对交换 | 编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0 与位1 交换，位2 与位3 交换，以此类推）。 |
| 5.8 | 绘制直线 | 有个单色屏幕存储在一个一维字节数组中，使得8 个连续像素可以存放在一个字节里。屏幕宽度为w，且w 可被8 整除（即一个字节不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水线。该方法的签名应形似于drawLine(byte[] screen, int width, int x1, int x2, int y)。 |
数学与逻辑题 |
||
| 6.1 | 较重的药丸 | 有20 瓶药丸，其中19 瓶装有1.0 克的药丸，余下1 瓶装有1.1 克的药丸。 给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次。 |
| 6.2 | 篮球问题 | 有个篮球框，下面两种玩法可任选一种。 玩法1：一次出手机会，投篮命中得分。 玩法2：三次出手机会，必须投中两次。 如果p 是某次投篮命中的概率，则p 的值为多少时才会选择玩法1 或玩法2？ |
| 6.3 | 多米诺骨牌 | 有个8 × 8 棋盘，其中对角的角落上，两个方格被切掉了。给定31 块多米诺骨牌，一块骨牌恰好可以覆盖两个方格。用这31 块骨牌能否盖住整个棋盘？请证明你的答案（提供范例或证明为什么不能）。 |
| 6.4 | 三角形上的蚂蚁 | 三角形的三个顶点上各有一只蚂蚁。如果蚂蚁开始沿着三角形的边爬行，两只或三只蚂蚁撞在一起的概率有多大？假定每只蚂蚁会随机选一个方向，每个方向被选到的概率相等，而且三只蚂蚁的爬行速度相同。 类似问题：在n 个顶点的多边形上有n 只蚂蚁，求出这些蚂蚁发生碰撞的概率。 |
| 6.5 | 水壶问题 | 有两个水壶，容量分别为3 夸脱①和5 夸脱，若水的供应不限量（但没有量杯），怎么用这两个水壶得到刚好的水？注意，这两个水壶呈不规则状，无法精准地装满“半壶”水。 |
| 6.6 | 蓝眸岛 | 有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8 点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人有蓝眼睛，只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛？ |
| 6.7 | 大灾难 | 在大灾难后的新世界，世界女王非常关心出生率。 因此，她规定所有家庭都必须有一个女孩，否则将面临巨额罚款。如果所有的家庭都遵守这个政策——所有家庭在得到一个女孩之前不断生育，生了女孩之后立即停止生育——那么新一代的性别比例是多少（假设每次怀孕后生男生女的概率是相等的）？通过逻辑推理解决这个问题，然后使用计算机进行模拟。 |
| 6.8 | 扔鸡蛋问题 | 有栋建筑物高100 层，若从第N 层或更高的楼层扔下来，鸡蛋就会破碎；若从第N 层以下的楼层扔下来则不会破碎。给你两个鸡蛋，请找出N，并要求最差情况下扔鸡蛋的次数为最少。 |
| 6.9 | 100个储物柜 | 走廊上有100 个关上的储物柜。有个人先是将100 个柜子全都打开。接着，每数两个柜子关上一个。然后，在第三轮时，再每隔两个就切换第三个柜子的开关状态（也就是将关上的柜子打开，将打开的关上）。照此规律反复操作100 次，在第i 轮，这个人会每数i 个就切换第i 个柜子的状态。当第100 轮经过走廊时，只切换第100 个柜子的开关状态，此时有几个柜子是开着的？ |
| 6.10 | 有毒的苏打水 | 你有1000 瓶苏打水，其中有一瓶有毒。 你有10 条可用于检测毒物的试纸。一滴毒药会使试纸永久变黄。你可以一次性地将任意数量的液滴置于试纸上，你也可以多次重复使用试纸（只要结果是阴性的即可）。 但是，每天只能进行一次测试，用时7 天才可得到测试结果。你如何用尽量少的时间找出哪瓶苏打水有毒？ 进阶：编写程序模拟你的方法。 |
面向对象设计 |
||
| 7.1 | 扑克牌 | 请设计用于通用扑克牌的数据结构，并说明你会如何创建该数据结构的子类，实现“二十一点”游戏。 |
| 7.2 | 呼叫中心 | 设想你有个呼叫中心，员工分3 级：接线员、主管和经理。客户来电会先分配给有空的接线员。若接线员处理不了，就必须将来电往上转给主管。若主管没空或是无法处理，则将来电往上转给经理。请设计这个问题的类和数据结构，并实现一种dispatchCall()方法，将客户来电分配给第一个有空的员工。 |
| 7.3 | 音乐点唱机 | 运用面向对象原则，设计一款音乐点唱机。 |
| 7.4 | 停车场 | 运用面向对象原则，设计一个停车场。 |
| 7.5 | 在线图书阅读器 | 请设计在线图书阅读器系统的数据结构。 |
| 7.6 | 拼图 | 实现一个N × N 的拼图程序。设计相关数据结构并提供一种拼图算法。假设你有一种fitsWith 方法，传入两块拼图，若两块拼图能拼在一起，则返回true。 |
| 7.7 | 聊天服务器 | 请描述该如何设计一个聊天服务器。要求给出各种后台组件、类和方法的细节，并说明其中最难解决的问题会是什么。 |
| 7.8 | 黑白棋 | “奥赛罗棋”（黑白棋）的玩法如下：每一枚棋子的一面为白，一面为黑。游戏双方各执黑、白棋子对决，当一枚棋子的左右或上下同时被对方棋子夹住，这枚棋子就算是被吃掉了，随即翻面为对方棋子的颜色。轮到你落子时，必须至少吃掉对方一枚棋子。任意一方无子可落时，游戏即告结束。最后，棋盘上棋子较多的一方获胜。请运用面向对象设计方法，实现“奥赛罗棋”。 |
| 7.9 | 环状数组 | 实现一个CircularArray 类。该类需要支持类似于数组的数据结构且该数组可以被高效地轮转。如果可以的话，该类应该使用泛型类型（也被称作模板），同时可以通过标准循环语句for (Obj o : circularArray)进行迭代。 |
| 7.10 | 扫雷 | 设计和实现一个基于文字的扫雷游戏。扫雷游戏是经典的单人电脑游戏，其中在N × N 的网格上隐藏了B 个矿产资源（或炸弹）。网格中的单元格后面或者是空白的，或者存在一个数字。数字反映了周围8 个单元格中的炸弹数量。游戏开始之后，用户点开一个单元格。如果是一个炸弹，玩家即失败。如果是一个数字，数字就会显示出来。如果它是空白单元格，则该单元格和所有相邻的空白单元格（直到遇到数字单元格，数字单元格也会显示出来）会显示出来。当所有非炸弹单元格显示时，玩家即获胜。 玩家也可以将某些地方标记为潜在的炸弹。这不会影响游戏进行，只是会防止用户意外点击那些认为有炸弹的单元格。（读者提示：如果你不熟悉此游戏，请先在网上玩几轮。）  |
| 7.11 | 文件系统 | 设计一种内存文件系统（in-memory file system）的数据结构和算法，并说明其具体做法。如若可行，请用代码举例说明。 |
| 7.12 | 散列表 | 设计并实现一个散列表，使用链接（即链表）处理碰撞冲突。 |
递归与动态规划 |
||
| 8.1 | 三步问题 | 有个小孩正在上楼梯,楼梯有 n 阶台阶,小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法,计算小孩有多少种上楼梯的方式。 |
| 8.２ | 迷路的机器人 | 设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格。设计一种算法,寻找机器人从左上角移动到右下角的路径。 |
| 8.3 | 魔术索引 | 在数组 A[0...n-1] 中,有所谓的魔术索引,满足条件 A[i] = i 。给定一个有序整数数组,元素值各不相同,编写一种方法找出魔术索引,若有的话,在数组 A 中找出一个魔术索引。 进阶:如果数组元素有重复值,又该如何处理呢? |
| 8.4 | 幂集 | 编写一种方法,返回某集合的所有子集。 |
| 8.5 | 递归乘法 | 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。 |
| 8.6 | 汉诺塔问题 | 在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它的盘子上。 请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。 |
| 8.7 | 无重复字符串的排列组合 | 编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。 |
| 8.8 | 重复字符串的排列组合 | 编写一种方法,计算字符串所有的排列组合,字符串中可能有字符相同,但结果不能有重复组合。 |
| 8.9 | 括号 | 设计一种算法,打印 n 对括号的所有合法的(例如,开闭一一对应)组合。 示例: 输入: 3 输出: ((())), (()()), (())(), ()(()), ()()() |
| 8.10 | 颜色填充 | 编写函数,实现许多图片编辑软件都支持的“颜色填充”功能。给定一个屏幕(以二维数组表示,元素为颜色值)、一个点和一个新的颜色值,将新颜色值填入这个点的周围区域,直到原来的颜色值全都改变。 |
| 8.11 | 硬币 | 给定数量不限的硬币,币值为 25 分、10 分、5 分和 1 分,编写代码计算 n 分有几种表示法。 |
| 8.12 | 八皇后 | 设计一种算法,打印八皇后在 8 × 8 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。 |
| 8.13 | 堆箱子 | 给你一堆 n 个箱子,箱子宽 w i 、高 h i 、深 d i 。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。 |
| 8.14 | 布尔运算 | 给定一个布尔表达式和一个期望的布尔结果 result ,布尔表达式由 0 、 1、 & 、| 和 ^ 符号组成。实现一个函数,算出有几种可使该表达式得出 result 值的括号方法。该表达式要用全括号(如 (0)^(1) )表示,而不能包含半括号(如 (((0))^(1)) )。 示例: countEval("1^0|0|1", false) -> 2 countEval("0&0&0&1^1|0", true) -> 10 |
系统设计与可扩展性 |
||
| 9.1 | 股票数据 | 假设你正在搭建某种服务,有多达 1000 个客户端软件会调用该服务,取得每天盘后股票价格信息(开盘价、收盘价、最高价与最低价)。假设你手里已有这些数据,存储格式可自行定义。你会如何设计这套面向客户端的服务从而向客户端软件提供信息?你将负责该服务的研发、部署、持续监控和维护。描述你想到的各种实现方案,以及为何推荐采用你的方案。该服务的实现技术可任选,此外,可以选用任何机制向客户端分发信息。 |
| 9.2 | 社交网络 | 你会如何设计诸如 Facebook 或 LinkedIn 的超大型社交网站的数据结构?请设计一种算法,展示两人之间最短的社交路径(比如,我 → 鲍勃 → 苏珊 → 杰森 → 你)。 |
| 9.3 | 网络爬虫 | 如果要设计一个网络爬虫,该怎样避免陷入死循环呢? |
| 9.4 | 重复网址 | 给定 100 亿个网址(URL),如何检测出重复的文件?这里所谓的“重复”是指两个 URL 完全相同。 |
| 9.5 | 缓存 | 想象有个 Web 服务器,实现简化版搜索引擎。这套系统有 100 台机器来响应搜索查询,可能会对另外的机器集群调用 processSearch(string query) 以得到真正的结果。响应查询请求的机器是随机挑选的,因此两个同样的请求不一定由同一台机器响应。processSearch 方法过于昂贵,请设计一种缓存机制,缓存最近几次查询的结果。当数据发生变化时,请解释说明该如何更新缓存。 |
| 9.6 | 销售排名 | 一家大型电子商务公司希望列出所有类别及每个类别最畅销的产品,例如,在所有类别中,一款产品可能是第 1056 个畅销产品,但在“ 运动器械 ”类排名第 13,在“ 安全 ”类排名第 24。简述你要如何设计这个系统。 |
| 9.7 | 个人理财管理 | 要你设计款个人理财管理系统(类似 Mint.com),简述你的设计思路。系统的功能可以连接到你的银行账户,分析你的消费习惯,并给出建议。 |
| 9.8 | 文本分享 | 设计一个类似于 Pastebin 1 的系统,用户输入一段文本,就可以得到一个随机生成的 URL 来访问该系统。 |
排序与查找 |
||
| 10.1 | 合并排序的数组 | 给定两个排序后的数组 A 和 B ,其中 A 的末端有足够的缓冲空间容纳B 。编写一个方法,将 B 合并入 A 并排序。 |
| 10.2 | 变位词组 | 编写一种方法,对字符串数组进行排序,将所有变位词排在相邻的位置。 |
| 10.3 | 搜索旋转数组 | 给定一个排序后的数组,包含 n 个整数,但这个数组已被旋转过很多次了,次数不详。请编写代码找出数组中的某个元素,假设数组元素原先是按升序排列的。 示例: 输入:在数组 {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14} 中找出 5 输出: 8 (元素 5 在该数组中的索引) |
| 10.4 | 排序集合的查找 | 给定一个类似数组的长度可变的数据结构 Listy ,它有个 elementAt(i)方法,可以在 O(1)的时间内返回下标为 i 的值,但越界会返回1。因此,该数据结构只支持正整数。给定一个排好序的正整数 Listy ,找到值为 x 的下标。如果 x 多次出现,任选一个返回。 |
| 10.5 | 稀疏数组搜索 | 有个排好序的字符串数组,其中散布着一些空字符串,编写一种方法,找出给定字符串的位置。 示例: 输入:在字符串数组 {"at", "", "", "", "ball", "", "", "car", "","","dad", "", ""} 中查找“ ball ” 输出: 4 |
| 10.6 | 大文件排序 | 设想你有个 20 GB 的文件,每行有一个字符串,请阐述一下将如何对这个文件进行排序。 |
| 10.7 | 失踪的整数 | 给定一个输入文件,包含 40 亿个非负整数,请设计一种算法,生成一个不包含在该文件中的整数,假定你有 1 GB 内存来完成这项任务。 进阶:如果只有 10 MB 内存可用,该怎么办?假设所有值均不同,且有不超过 10 亿个非负整数。 |
| 10.8 | 寻找重复数 | 给定一个数组,包含 1 到 N 的整数,N 最大为 32 000,数组可能含有重复的值,且 N 的取值不定。若只有 4 KB 内存可用,该如何打印数组中所有重复的元素。 |
| 10.9 | 排序矩阵查找 | 给定 M × N 矩阵,每一行、每一列都按升序排列,请编写代码找出某元素。 |
| 10.10 | 数字流的秩 | 假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作,也就是说,实现track(int x) 方法,每读入一个数字都会调用该方法;实现 getRankOfNumber(int x)方法,返回小于或等于 x(x 除外)的值的个数。 示例: 数据流为(按出现的先后顺序): 5, 1, 4, 4, 5, 9, 7, 13, 3 getRankOfNumber(1) = 0 getRankOfNumber(3) = 1 getRankOfNumber(4) = 3 |
| 10.11 | 峰与谷 | 在一个整数数组中,“峰”是大于或等于相邻整数的元素,相应地,“谷”是小于或等于相邻整数的元素。例如,在数组 {5, 8, 6, 2, 3, 4, 6} 中, {8, 6} 是峰,{5, 2} 是谷。现在给定一个整数数组,将该数组按峰与谷的交替顺序排序。 示例: 输入: [5, 3, 1, 2, 3] 输出: [5, 1, 3, 2, 3] |
测试 |
||
| 11.1 | 找错 | 找出以下代码中的错误(可能不止一处)。 unsigned int i; for (i = 100; i >= 0; --i) printf("%d\n", i); |
| 11.2 | 随机崩溃 | 有个应用程序一运行就崩溃,现在你拿到了源码。在调试器中运行10次之后,你发现该应用每次崩溃的位置都不一样。这个应用只有一个线程,并且只调用 C 标准库函数。究竟是什么样的编程错误导致程序崩溃?该如何逐一测试每种错误? |
| 11.3 | 测试国际象棋 | 有个国际象棋游戏程序使用了 boolean canMoveTo(int x, int y)方法,这个方法是 Piece 类的一部分,可以判断某个棋子能否移动到位置(x, y)。请阐述你会如何测试该方法。 |
| 11.4 | 无工具测试 | 不借助任何测试工具,该如何对网页进行负载测试? |
| 11.5 | 测试一支笔 | 如何测试一支笔? |
| 11.6 | 测试 ATM | 在一个分布式银行系统中,该如何测试一台自动柜员机(ATM)? |
C和C++ |
||
| 12.1 | 最后K行 | 用C++写个方法,打印输入文件的最后K行。 |
| 12.2 | 反转字符串 | 用 C 或 C++实现一个名为reverse(char* str)的函数,它可以反转一个null 结尾的字符串。 |
| 12.3 | 散列表与 STL map | 比较并对比散列表和 STL map。散列表是怎么实现的?如果输入的数据量不大,可以选用哪些数据结构替代散列表? |
| 12.4 | 虚函数原理 | C++虚函数的工作原理是什么? |
| 12.5 | 浅复制与深复制 | 浅复制和深复制之间有何区别?请阐述两者的不同用法。 |
| 12.6 | volatile 关键字 | C++语言的关键字volatile有何作用? |
| 12.7 | 虚基类 | 基类的析构函数为何要声明为virtual? |
| 12.8 | 复制节点 | 编写一种方法,传入参数为指向 Node 结构的指针,返回传入数据结构的完整副本,其中, Node 数据结构含有两个指向其他 Node 的指针。 |
| 12.9 | 智能指针 | 编写一个智能指针类。智能指针是一种数据类型,一般用模板实现,模拟指针行为的同时还提供自动垃圾回收机制。它会自动记录SmartPointer<T*> 对象的引用计数,一旦 T 类型对象的引用计数为 0,就会释放该对象。 |
| 12.10 | 分配内存 | 编写支持对齐分配的 malloc 和 free 函数,分配内存时, malloc 函数返回的地址必须能被 2 的 n 次方整除。 示例: align_malloc(1000,128)返回的内存地址可被128整除,并指向一块1000字节大小的内存。 aligned_free() 会释放 align_malloc 分配的内存。 |
| 12.11 | 二维数组分配 | 用 C 编写一个 my2DAlloc 函数,可分配二维数组。将 malloc 函数的调用次数降到最少,并确保可通过 arr[i][j] 访问该内存。 |
Java |
||
| 13.1 | 私有构造函数 | 从继承的角度看,把构造函数声明为私有会有何作用? |
| 13.2 | 异常处理中的返回 | 在 Java 中,若在 try-catch-finally 的 try 语句块中插入 return语句, finally 语句块是否还会执行? |
| 13.3 | final 们 | final 、 finally 和 finalize 之间有何差异? |
| 13.4 | 泛型与模板 | C++模板和 Java 泛型之间有何不同? |
| 13.5 | TreeMap 、 HashMap 、 LinkedHashMap | 解释一下TreeMap 、 HashMap 、 LinkedHashMap三者的不同之处。举例说明各自最适合的情况。 |
| 13.6 | 反射 | 解释下 Java 中对象反射是什么,有什么用处。 |
| 13.7 | lambda 表达式 | 有一个名为 Country 的类,它有两种方法,一种是 getContinent() 返回该国家所在大洲,另一种是 getPopulation() 返回本国人口。实现一种名为 getPopulation (List counties,String continent) 的方法,返回值类型为 int 。它能根据指定的大洲名和国家列表计算出该大洲的人口总数。 |
| 13.8 | lambda 随机数 | 使用 lambda 表达式写一种名为 getRandomSubset(List list)的方法,返回值类型为 List ,返回一个任意大小的随机子集,所有子集(包括空子集)选中的概率都一样。 |
数据库 |
||
| 14.1 | 多套公寓 | 编写SQL查询,列出租住不止一套公寓的承租人。 |
| 14.2 | “ open ”的申请数量 | 编写 SQL 查询,列出所有建筑物,并取得状态为“ Open ”的申请数量( Requests 表中 Status 为“ Open ”的条目)。 |
| 14.3 | 关闭所有请求 | 11 号建筑物正在进行大翻修。编写 SQL 查询,关闭这栋建筑物里所有公寓的入住申请。 |
| 14.4 | 连接 | 连接有哪些不同类型?请说明这些类型之间的差异,以及为何在某些情形下,某种连接会比较好。 |
| 14.5 | 反规范化 | 什么是反规范化?请说明其优缺点。 |
| 14.6 | 画一个实体关系图 | 有个数据库,里面有公司( companies )、人( people )和在职专业人员( professional ),请绘制实体关系图。 |
| 14.7 | 设计分级数据库 | 给定一个存储学生成绩的简单数据库。设计这个数据库的大体框架,并编写 SQL 查询,返回以平均分排序的优等生名单(排名前 10%)。 |
线程与锁 |
||
| 15.1 | 进程与线程 | 进程和线程有何区别? |
| 15.2 | 上下文切换 | 如何测量上下文切换时间? |
| 15.3 | 哲学家用餐 | 在著名的哲学家用餐问题中,一群哲学家围坐在圆桌周围,每两位哲学家之间有一根筷子。每位哲学家需要两根筷子才能用餐,并且一定会先拿起左手边的筷子,然后才会去拿右手边的筷子。如果所有哲学家在同一时间拿起左手边的筷子,就有可能造成死锁。请使用线程和锁,编写代码模拟哲学家用餐问题,避免出现死锁。 |
| 15.4 | 无死锁的类 | 设计一个类,只有在不可能发生死锁的情况下,才会提供锁。 |
| 15.5 | 顺序调用 | 给定以下代码: public class Foo { public Foo() { ... } public void first() { ... } public void second() { ... } public void third() { ... } } 同一个 Foo 实例会被传入 3 个不同的线程。 threadA 会调用 first , threadB 会调用second , threadC 会调用 third 。设计一种机制,确保 first 会在 second 之前调用,second 会在 third 之前调用。 |
| 15.6 | 同步方法 | 给定一个类,内含同步方法 A 和普通方法 B 。在同一个程序实例中,有两个线程,能否同时执行 A ?两者能否同时执行 A 和 B ? |
| 15.7 | FizzBuzz | 在经典面试题 FizzBuzz 中,要求你从 1 到 n 打印数字。并且,当数字能被3整除时,打印 Fizz,能被 5 整除时,打印 Buzz。倘若同时能被 3 和 5 整除,就打印FizzBuzz。但与以往不同的是,这里要求你用 4 个线程,实现一个多线程版本的 FizzBuzz,其中,一个用来检测是否被 3 整除和打印 Fizz,另一个用来检测是否被 5 整除和打印 Buzz。第三个线程检测能否被 3 和 5 整除和打印 FizzBuzz。第四个线程负责遍历数字。 |
中等难题 |
||
| 16.1 | 交换数字 | 编写一个函数,不用临时变量,直接交换两个数。 |
| 16.2 | 单词频率 | 设计一个方法,找出任意指定单词在一本书中的出现频率。如果我们多次使用此方法,应该怎么办? |
| 16.3 | 交点 | 给定两条线段(表示为起点和终点),如果它们有交点,请计算其交点。 |
| 16.4 | 井字游戏 | 设计一个算法,判断玩家是否赢了井字游戏。 |
| 16.5 | 阶乘尾数 | 设计一个算法,算出 n 阶乘有多少个尾随零。 |
| 16.6 | 最小差 | 给定两个整数数组,计算具有最小差(非负)的一对数值(每个数组中取一个值),并返回该对数值的差。 示例: 输入: {1, 3, 15, 11, 2}, {23, 127, 235, 19, 8} 输出: 3 ,即数值对 (11, 8) |
| 16.7 | 最大数值 | 编写一个方法,找出两个数字中最大的那一个。不得使用 if-else 或其他比较运算符。 |
| 16.8 | 整数的英语表示 | 给定一个整数,打印该整数的英文描述(例如“One Thousand, Two Hundred Thirty Four”)。 |
| 16.9 | 运算 | 请实现整数数字的乘法、减法和除法运算,运算结果均为整数数字,程序中只允许使用加法运算符。 |
| 16.10 | 生存人数 | 给定一个列有出生年份和死亡年份的名单,实现一个方法以计算生存人数最多的年份。你可以假设所有人都出生于 1900 年至 2000 年(含 1900 和 2000)之间。如果一个人在某一年的任意时期都处于生存状态,那么他们应该被纳入那一年的统计中。例如,生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。 |
| 16.11 | 跳水板 | 你正在使用一堆木板建造跳水板。 有两种类型的木板,其中一种长度较短(长度记为 shorter ),一种长度较长(长度记为 longer )。你必须正好使用 K 块木板。编写一个方法,生成跳水板所有可能的长度。 |
高难度题 |
||
| 17.1 | 不用加号的加法 | 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 |
| 17.2 | 洗牌 | 设计一个用来洗牌的函数。要求做到完美洗牌,也就是说,这副牌 52! 种排列组合出现的概率相同。假设给定一个完美的随机数发生器。 |
| 17.3 | 随机集合 | 编写一个方法,从大小为 n 的数组中随机选出 m 个整数。要求每个元素被选中的概率相同。 |
| 17.4 | 消失的数字 | 数组 A 包含从 0 到 n 的所有整数,但其中缺了一个。在这个问题中,只用一次操作无法取得数组 A 里某个整数的完整内容。此外,数组 A 的元素皆以二进制表示,唯一可用的访问操作是“从 A[i] 中取出第 j 位数据”,该操作的时间复杂度为常量。请编写代码找出那个缺失的整数。你有办法在 O(n)时间内完成吗? |
| 17.5 | 字母与数字 | 给定一个放有字符和数字的数组,找到最长的子数组,且包含的字符和数字的个数相同。 |
| 17.6 | 2 出现的次数 | 编写一个方法,计算从 0 到 n(含 n)中数字 2 出现的次数。 示例: 输入: 25 输出: 9(2, 12, 20, 21, 22, 23, 24, 25) (注意 22 应该算作两次) |
| 17.7 | 婴儿名字 | 每年,政府都会公布一万个最常见的婴儿名字和它们出现的频率,也就是同名婴儿的数量。有些名字有多种拼法,例如,John 和 Jon 本质上是相同的名字,但被当成了两个名字公布出来。给定两个列表,一个是名字及对应的频率,另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意,如果 John 和 Jon 是相同的,并且 Jon 和 Johnny 相同,则 John 与 Johnny 也相同,即它们有传递性和对称性。 在结果列表中,任选一个名字做为真实名字就可以。 示例: 输入: Names: John(15)、Jon(12)、Chris(13)、Kris(4)、Christopher(19) Synonyms: (Jon, John)、(John, Johnny)、(Chris, Kris)、(Chris, Christopher) 输出: John(27)、Kris(36) |
| 17.8 | 马戏团人塔 | 有个马戏团正在设计叠罗汉的表演节目,一个人要站在另一人的肩膀上。出于实际和美观的考虑,在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重,请编写代码计算叠罗汉最多能叠几个人。 示例: 输入: (ht, wt) : (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) 输出:从上往下数,叠罗汉最多能叠 6 层: (56, 90) (60,95) (65,100) (68,110) |
| (70,150) (75,190) | ||
| 17.9 | 第k个数 | 有些数的素因子只有 3,5,7,请设计一个算法找出第k个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 1,3,5,7,9,15,21。 |
| 17.10 | 主要元素 | 有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 1,3,5,7,9,15,21。 |
| 17.11 | 单词距离 | 有个内含单词的超大文本文件,给定任意两个单词,找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次,而每次寻找的单词不同,你能对此优化吗? |
| 17.12 | BiNode | 有个名为 BiNode 的简单数据结构,包含指向另外两个节点的指针。 public class BiNode { public BiNode node1, node2; public int data; } BiNode 可用来表示二叉树(其中 node1 为左子节点, node2 为右子节点)或双向链表(其中 node1 为前趋节点, node2 为后继节点)。实现一个方法,把用 BiNode 实现的二叉搜索树转换为双向链表,要求值的顺序保持不变,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。 |
| 17.13 | 恢复空格 | 哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子“ I reset the computer. It still didn’t boot! ”已经变成了“ iresetthecomputeritstilldidntboot ”。在处理标点符号和大小写之前,你得先把它断成词语。当然了,你有一本厚厚的词典,用一个 string 的集合表示。不过,有些词没在词典里。假设文章用 string 表示,设计一个算法,把文章断开,要求未识别的字符最少。 示例: 输入: jesslookedjustliketimherbrother 输出: jess looked just like tim her brother (7 个未识别的字符) |
| 17.14 | 最小k个数 | 设计一个算法,找出数组中最小的 k 个数。 |
| 17.15 | 最长单词 | 给定一组单词,编写一个程序,找出其中的最长单词,且该单词由这组单词中的其他单词组合而成。 示例: 输入: cat, banana, dog, nana, walk, walker, dogwalker 输出: dogwalker |
| 17.16 | 按摩师 | 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有 15 分钟的休息时间,因此她不能接受时间相邻的预约。给定一个预约请求序列(都是 15 分钟的倍数,没有重叠,也无法移动),替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。 示例: 输入: {30, 15, 60, 75, 45, 15, 15, 45} 输出: 180 minutes ({30, 60, 45, 45}) |
| 17.17 | 多次搜索 | 给定一个字符串 b 和一个包含较短字符串的数组 T ,设计一个方法,根据T中的每一个较短字符串,对 b 进行搜索。 |
| 17.18 | 最短超串 | 假设你有两个数组,一个长一个短,短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组,其出现顺序无关紧要。 示例: 输入: {1, 5, 9} |
| 17.19 | 消失的两个数字 | 给定一个数组,包含从 1 到 N 所有的整数,但其中缺了一个。你能在O(N)时间内只用 O(1)的空间找到它吗?如果是缺了两个数字呢? |
| 17.20 | 连续中值 | 随机产生数字并传递给一个方法。你能否完成这个方法,在每次产生新值时,寻找当前所有值的中间值并保存。 |
| 17.21 | 直方图的水量 | 给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 1。 示例(黑色部分是直方图,灰色部分是水): 输入: {0, 0, 4, 0, 0, 6, 0, 0, 3, 0, 5, 0, 1, 0, 0, 0} 输出: 26  |
| 17.22 | 单词转换 | 给定字典中的两个词,长度相等。写一个方法,把一个词转换成另一个词,但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。 示例: 输入: DAMP, LIKE 输出: DAMP -> LAMP ->LIMP ->LIME ->LIKE |
| 17.23 | 最大黑方阵 | 给定一个方阵,其中每个单元(像素)非黑即白。设计一个算法,找出条边皆为黑色像素的最大子方阵。 |
| 17.24 | 最大子矩阵 | 给定一个正整数和负整数组成的 N × N 矩阵,编写代码找出元素总和最大的子矩阵。 |
| 17.25 | 单词矩阵 | 给定一份几百万个单词的清单,设计一个算法,创建由字母组成的最大矩形,其中每一行组成一个单词(自左向右),每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现,但要求所有行等长,所有列等高。 |
| 17.26 | 稀疏相似度 | 两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数,就是这两个文档的相似度。例如, {1, 5, 3} 和 {1, 7, 2, 3}的相似度是 0.4,其中,交集的元素有 2 个,并集的元素有 5 个。给定一系列的长篇文档,每个文档元素各不相同,并与一个 ID 相关联。它们的相似度非常“稀疏”,也就是说任选 2 个文档,相似度都很接近 0。请设计一个算法返回每对文档的 ID 及其相似度。 只需输出相似度大于 0 的组合。请忽略空文档。为简单起见,可以假定每个文档由一个含有不同整数的数组表示。 示例: 输入: 13: {14, 15, 100, 9, 3} 16: {32, 1, 9, 3, 5} 19: {15, 29, 2, 6, 8, 7} 24: {7, 10} 输出: ID1, ID2 : SIMILARITY 13, 19 : 0.1 13, 16 : 0.25 19, 24 : 0.14285714285714285 |
系统设计
todo
一个OnlineJuge的实现思路
面向对象
LeetCode题目归类
cc150的题目，知识面广，但是难度相对较小，相当于leetcode的easy题。但是在这些题型中受到启蒙以后，leetcode的题型也会打开思路的。为了扩充一些题量，整理leetcode的类型总结。
计划表
- 统一代码格式
- 美化文字格式，提升阅读体验
- 增加LeetCode的相关专题
- 完成后续的章节
- 增加示意图或动画
- 增加第六版的内容
- 对比官方的Java版答案，校验一次
- 抽象测试用例运行框架，实现一个Online judge