前言“开裂编码采访”是一本被许多人极力推荐的程序员面试书籍，详情可见：http://www.careercup.com/book里面有150道程序员面试题目及相应的解答。书中大部分是编程题目， https://github.com/Hawstein/cracking-the-coding-interview 那真真是再好不过了：P 目录第1章数组和字符串 1.1 实现的算法，以确定是否一个字符串的所有独特的字符。如果你不能使用额外的数据结构？ 1.2 写代码来扭转一个C风格字符串。（C-字符串表示，“ABCD”表示为5个字符，包括空字符）。 1.3 设计一个算法，并编写代码来删除重复的字符串中的字符，而无需使用任何额外的缓冲。注：一个或两个额外的变量的罚款 。数组的一个额外副本是没有的。跟进写这种方法的测试案例。 1.4 写一个方法来决定两个字符串是否字谜或没有。 1.5 写一个方法，“％20”替换字符串中的所有空格。 1.6 由于一个NxN矩阵，其中每一个图像中的像素为4个字节，写一个方法将图像旋转90度所表示的图像。你能做到这一点的地方吗？ 1.7 写的算法，例如，如果一个M×N个矩阵中的一个元素是0，其整个的行和列被设置为0。 1.8 假设你有一个方法isSubstring，检查如果用一个词是另外的一个子。鉴于两个字符串，s1和s2，编写代码，以检查是否s2是s1的旋转只使用一个呼叫isSubstring（即的“waterbottle”是一个旋转的“erbottlewat”）。 第2章|链表 2.1 编写代码来删除重复的从一个无序的链接列表。跟进你将如何解决这个问题，如果一个临时的缓冲区是不允许的？ 2.2 实现一个算法找到的第n个单链表的最后一个元素。 2.3 实施一种算法来删除单链表的中间，由于只能访问到该节点中的一个节点。例如输入：'从链表节点c-> B-> C-> D->结果：什么也没有返回，但看起来像新的链接列表A-> B-> D-> 2.4 有两个数字表示的一个链表，其中每个节点包含一个单一的数字。以相反的顺序存储的数字，这样的数字是1的列表头。写一个函数，增加了两个数字，并返回链表的总和。实施例输入：（3 - > 1 - > 5）+（5 - > 9 - > 2）输出：8 - > 0 - > 8 2.5 循环链表，实现一个算法返回循环的开始节点。定义循环链表：（腐败）链表节点的下一个指针指向较早的节点，从而使一个循环链表中。例如输入：A - > B - > C - > D - > - > C（C为更早）输出：C 第3章栈和队列 3.1 说明你可以使用一个单一的阵列来实现三栈。 3.2 你会如何设计一个堆栈，除了push和pop，还有另外一种功能分钟返回的最小元素？PUSH，POP和最小值都应该运行在O（1）的时间。 3.3 想象一下，一个板（文字）堆栈。如果堆栈变得过高的话，可能会倾倒。因此，在现实生活中，我们可能会开始前一个堆栈超过一定的阈值时，一个新的堆栈。实现一个的数据结构SetOfStacks模仿这个。应该由几个栈SetOfStacks，一旦前一个超过容量，应该创建一个新的堆栈。SetOfStacks.push（）和SetOfStacks.pop（）的行为相同到一个单一的堆栈，pop（）方法应该返回相同的值，如果有只是一个单一的协议栈。跟进实现一个的功能popAt（INT指数）在一个特定的子堆栈进行弹出操作。 3.4 汉诺塔的经典问题，你有3棒和N的不同大小的磁盘可以滑动到任何塔。拼图开始从上到下（例如按规模由小到大排序的磁盘，每个磁盘坐在更大的顶部）。你有下列限制：（一）一次只有一个可移动磁盘。（B）磁盘到下一杆一杆的顶部滑出。©磁盘只能被放置在一个更大的磁盘之上。写一个程序从第一棒到最后的使用堆栈移动磁盘。 3.5 实现一个MyQueue的类，它实现了一个队列使用两个栈。 3.6 写一个程序，以升序排序堆栈。栈是如何实现的，你不应该做任何假设。下面是唯一应该被用来编写这个程序的功能：推|流行|偷看的isEmpty。 第4章树和图 4.1 实现一个函数来检查，如果一棵树是平衡的。对于这个问题的目的，平衡树被定义为，使得没有两个叶子节点由一个以上的不同的距离，从根的树。 4.2 给定一个有向图，设计一个算法，找出是否有两个节点之间的路由。 4.3 鉴于一个排序（递增顺序）阵列，写一个算法创建一个二叉树的最小高度。 4.4 鉴于二叉搜索树，设计一个算法，它创建了一个链表，在每个深度的所有节点（即，如果你有一个树的深度D，你就必须ð链表）。 4.5 写一个算法来找到'下一个'二叉搜索树中的某个节点，每个节点都有一个链接到它的父节点（即顺序继承人）。 4.6 设计一个算法，并编写代码来查找二叉树中的两个节点的共同祖先。避免存储在数据结构中的附加 节点。注：这不一定是一个二叉搜索树。 4.7 你有两个非常大的二进制树：与数以百万计的节点，T1，T2，与数百个节点。创建一个算法来决定，如果T2是T1的子树。 4.8 给你一个二进制树，其中每个节点都包含一个值。设计一个算法，打印所有的路径，总结该值。请注意，它可以是任何在树中的路径信息-它不具有从根开始。 第5章位操作 5.1 两个32位数字，N和M两个位的位置，i和j。写一个方法来设置i和j之间的所有位在N等于M（例如，M为一个子串的N i和位于在j起）。例：输入：N = 10000000000，M = 10101，I = 2，J = 6输出：N = 10001010100 5.2 鉴于（十进制-例如3.72）的数量，作为一个字符串，通过打印的二进制表示。如果数量不能精确表示二进制，打印“ERROR” 5.3 给定的整数，打印具有相同数量的1个比特的二进制表示的下一个最小的和下一个最大的数字。 5.4 解释下面的代码：（（N（N-1））== 0）。 5.5 写一个函数来确定转换整数到整数B.输入所需的比特数：31，14输出：2 5.6 写一个程序，以尽可能几条指令（例如，第0位和第1位交换，第2位和第3位被换等）交换奇数和偶数位整数。 5.7 数组A [1 ... n]的包含了所有的除了缺少一个数字从0到n的整数。在这个问题上，我们不能访问一个单一的操作在A整个整数。元素二进制表示的，我们可以用它来 访问它们唯一的操作是“取第j个二进制位的A [I]”，这需要恒定的时间。写代码寻找失踪的整数。你能做到在O（n）的时间？ 第6章|脑筋急转弯 破解编码采访Q6.1〜Q6.6 第7章面向对象设计 XDDDDDD 第8章递归 8.1 写一个方法来生成第n个Fibonacci数。 8.2 想象一下，一个机器人坐在一个NxN网格的左上角。该机器人只能朝着两个方向：向右和向下。机器人有多少种可能的路径吗？跟进想象的某些方块是“禁区”，比如机器人可以不踩。设计一个算法，机器人得到所有可能的路径。 8.3 写一个方法，返回一个集合的所有子集。 8.4 写一个方法来计算一个字符串的所有排列。 8.5 实现一个算法打印所有有效（例如，正确开启和关闭）组合正对括号。例如：输入：3（例如，3双括号）输出：（）（）（）（）（（）），（（））（），（（（））） 8.6 实施“颜料填充”功能，人们可能会看到许多图像编辑程序。也就是说，给出一个屏幕（2维数组颜色表示），一个点，和一个新的颜色，填写在周边地区，直到你碰到一个边框，颜色。 8.7 鉴于无限数量的季度（25美分），助攻（10美分），镍（5美分）和便士（1分），写代码的数量来计算的代表ñ美分的方式。 8.8 写一个算法来打印，所以，他们没有安排八皇后棋盘上的所有方式共享同一行，列或对角线。 第9章排序和搜索 9.1 两个排序数组A和B，A有一个足够大的缓冲区，在年底举行B.写的方法来合并B进入A的排序顺序。 9.2 写一个字符串数组的排序方式，使所有的字谜是彼此相邻的。 9.3 鉴于已旋转一个未知的次数，给一个O（log n）的算法，发现一个数组中的元素n个整数排序数组。你可以假设该数组最初是在递增的顺序排序。例如：输入：5阵列（15 16 19 20 25 1 3 4 5 7 10 14）输出：8（在数组中的索引5） 9.4 如果你有一个2 GB的文件，每行一个字符串，你会用排序算法对文件进行排序，为什么？ 9.5 鉴于穿插空字符串的字符串数组的排序，写一个方法，找到一个给定的字符串的位置。实施例：找到“球”[“上面”，“”，“”，“”，“球”，“”，“”，“汽车”，“”，“”，“爸爸”，“”，“”将返回4示例：查找[“在”“ballcar”，“”，“”，“”，“”，“球”，“汽车”，“”，“”，“爸爸”，“”，“ “]将返回-1 9.6 给定一个矩阵，其中每一行和每一列进行排序，写一个方法，找到一个元素。 9.7 马戏团设计塔常规组成的人站在彼此的肩膀之上。实用和美观的原因，每个人都必须比下面的人他或她更短，重量更轻。由于每个人的身高和体重在马戏团，写一个方法来计算最大的尽可能多的人，在这样一个塔。例如：输入（HT，重量）：（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） 第10章|数学 破解编码采访Q10.1〜Q10.7 第11章测试 破解编码采访Q11.1〜Q11.6 第12章系统设计和内存限制 12.1 如果被整合进料结束一天（开，高，低，收市价）为5000家企业的股票价格信息，你会怎么做呢？你是负责饲料的开发，部署和持续的监控和维护。说明不同的方法，你认为，为什么你会建议你的方法。饲料交付每个交易日以逗号分隔的格式通过一个FTP站点。每天1000的用户在一个Web应用程序将使用该饲料。 12.2 你会如何设计数据结构的一个非常大的社会网络（脸谱，LinkedIn等）？描述你将如何设计一个算法，显示连接或路径，两个人之间的（例如，ME - >鲍勃- >苏珊- >杰森- >你）。 12.3 40亿整数给定一个输入文件，提供一种算法，这是不包含在文件中生成的整数。假设你有1 GB的内存。跟进什么，如果你只有10 MB的内存？ 12.4 您有一个数组的所有号码从1到N，其中N是最多32,000。阵列可能有重复的条目，你不知道N是什么。只有4KB的内存，你会怎么打印所有重复的数组中的元素？ 12.5 如果你在设计一个网络爬虫，怎么会你避免陷入无限循环？ 12.6 你有一个亿的网址，其中每个是一个巨大的页面。如何检测重复的文件？ 12.7 你要设计一个数据库，可以存储TB级的数据。它应该支持高效的范围查询。你会怎么做呢？ 第13章C + + 13.1 写一个方法打印最后K线的输入文件，使用C + +。 13.2 比较和对比哈希表与STL地图。如何实现一个哈希表？如果投入的数量是很小的，什么样的数据结构选项可以用来代替一个哈希表？ 13.3 虚函数是如何工作的C + +？ 13.4 深拷贝和浅拷贝之间的区别是什么？解释你将如何使用每个。 关键字“挥发”在C 13.5 的意义是什么？ 13.6 名躲藏在C + +？ 13.7 为什么需要在基类的析构函数被声明为虚？ 13.8 写一个方法，需要一个节点结构指针作为参数，并返回传入的数据结构的完整副本。节点结构包含两个指针到其他节点结构。 13.9 写一个智能指针（smart_ptr）类。 第14章| JAVA 通过 第15章|数据库 15.1 写的方法找到各部门的员工人数。 15.2 有什么不同类型的连接？请解释他们是如何的不同，以及为什么在某些情况下，某些类型更好。 15.3 什么是反正规化？解释的利弊。 15.4 绘制实体关系图数据库的公司，人员和专业人员（谁的公司工作的人）。 15.5 试想一个简单的数据库存储信息，学生的成绩。设计数据库可能这是什么样子，并提供一个SQL查询返回一个列表光荣榜学生（前10％），他们的平均等级分排序。 第16章|水平低 16.1 解释以下条款：虚拟内存的页面故障，颠簸。 16.5 写一个程序，发现一台机器是否是big endian还是little endian的。 16.10 写一个的函数调用my2DAlloc分配一个二维数组。最小化的呼叫数量malloc和确保内存访问的符号到达[I] [J]。 第17章|网络 17.1 解释发生了什么，一步一步来，以后你在浏览器中键入一个URL。使用尽可能详细。
17.2 解释任何常见的路由协议的细节。例如：BGP，OSPF，RIP。 17.3 比较和对比IPv4和IPv6协议。 17.4 什么是网络/子网掩码？解释如何主机A发送一个消息/包到主机B时：（一）在同一网络上，及（b）在不同的网络。解释层的路由决策，以及如何。 17.5 TCP和UDP之间有什么区别？解释TCP如何处理可靠的传送（解释ACK机制），流量控制（解释TCP发送器/接收器的窗口）和拥塞控制。
第18章线程和锁 18.1 线程与进程之间的区别是什么？ 18.2 如何测量上下文切换所花费的时间？ 18.3 实现一个singleton设计模式作为模板等，对于任何给定的类Foo，您可以致电的辛格尔顿:: instance（）单身Foo类型的一个实例，并得到一个指针。其中有一类锁定收购（假设存在）和释放（）方法。你怎么能够使您实现线程安全和异常安全吗？ 18.5 假设我们有下面的代码：i）你能够设计一个机制，以确保经过A，B的执行，和C B之后执行？二）假设我们有下面的代码使用类Foo。我们不知道在操作系统中线程是如何将如期。你可以设计一个机制，以确保所有的方法将被执行的顺序吗？ 第19章|中等 19.1 写一个函数来交换一些地方没有临时变量。 19.2 设计一个算法找出如果有人赢了一场井字脚趾。 19.3 写尾随零数n的阶乘的算法计算。 19.4 写一个方法发现的最大的两个数字。你不应该使用if-else或任何其他比较操作符。
19.5 智囊团的游戏的玩法如下：
电脑有四个插槽，包含球是红®，黄色（Y），绿（G）或蓝色（B）。例如，计算机可能有RGGB（例如，插槽＃1是红色的，是绿色的插槽＃2和＃3，插槽＃4是蓝色的）。你的用户，尝试猜解。例如，您可能猜测YRGB。当你猜正确的颜色，正确的插槽，你会得到一个“打”。如果你猜的颜色存在，但是在错误的插槽，你会得到一个“伪命中”。例如，猜YRGB有2安打和一个伪命中。对于每一个猜测，你被告知的点击数和伪命中。写一个方法，猜测和解决方案，返回的点击数和伪命中。 19.7 现在给你一个整数数组（正面和负面的）。查找连续最大的一笔。返回的总和。
19.8 设计的方法找到任何给定的单词在一本书中出现的频率。 19.10 撰写方法1和7之间产生一个随机数，给定的一个方法，该方法在1和5之间产生一个随机数（即，实施rand7（）使用rand5（））。
19.11 设计一个算法来找出所有对整数数组内的指定值的总和。 hawstein的博客 http://hawstein.com/posts/ctci-solutions-contents.html | 
