[Powered by Google Translate] [讲座：技术访谈] [肯尼于哈佛大学] 这是CS50。[CS50.TV] 大家好，我是肯尼。我目前正在一个初中学习计算机科学。 我是一个CS TF前，我希望我有这个当我是低年级， 这就是为什么我给本次研讨会。 所以，我希望你喜欢它。 本次研讨会是技术面试， 和我所有的资源，可以发现在这个环节， 此链接在这里，一对夫妇的资源。 所以，我提出的问题清单，实际上，不少问题。 另外，一般的资源页面，在这里我们可以找到提示 如何准备接受记者采访时， 提示在实际的采访中你应该做的， 以及如何处理问题和资源，以备将来参考。 这一切都在网上。 而就在前言本次研讨会，免责声明， 这样不应该 - 你的面试准备 不应该被限制到该列表。 这只是意味着是一个指南， 你一定要我说的一切与一粒盐， 而且还用我来帮助你在你的面试准备的一切。 

我要加速通过下面的几张幻灯片 因此，我们可以得到的实际案例研究。 结构的软件工程现在的位置接受记者采访时， 它通常是30到45分钟， 多轮，根据公司。 你经常会在白板上进行编码。 因此，这样的白板，但往往在一个较小的规模。 如果你有一个接受电话采访时，你可能会被使用 collabedit或一个谷歌文档，这样他们就可以看到你住的编码 当你通过电话采访。 接受记者采访时本身通常是2个或3个问题 测试您的计算机科学知识。 它几乎肯定会涉及编码。 的问题的类型，你会看到通常是数据结构和算法。 而在做这些各种各样的问题， ，他们会问你喜欢什么，是时间和空间复杂度，大O？ 通常情况下，他们也要求更高层次的问题， 这样，设计系统时， 你怎么会躺在你的代码吗？ 什么样的接口，哪个班的，你有什么模块在您的系统， 怎么互动起来呢？ 因此，数据结构和算法，以及设计系统。 

一些通用的技巧之前，我们深入到我们的案例研究。 我认为最重要的规则总是在想大声。 采访应该是你的机会来炫耀你的思维过程。 在接受记者采访时的点是面试官评估 你怎么想的，你​​如何去通过一个问题。 在整个采访中，最糟糕的事情你能做的就是保持沉默。 这只是没有好。 当你一个问题，你要确保你明白的问题。 因此，重复的问题，早在你自己的话 并尝试工作的深入一些简单的测试用例 以确保您了解的问题。 通过一些测试案例，也会给你一个如何解决这个问题的直觉。 你甚至可能发现一些模式，以帮助您解决问题。 他们的大秘诀是不要沮丧。 不要沮丧。 面试是具有挑战性的，但你可以做的最糟糕的事情， 除了沉默，是明显受挫。 你不想给你那种印象的面试官。 有一件事你 - 所以，很多人，当他们进入接受记者采访时， 他们试图尝试找到最好的解决方案， 当真的，通常一个有目共睹的解决方案。 它可能是缓慢的，它可能是低效的，但你应该只说明它， 只要你有一个起点，更好地工作。 同时，指出了解决的办法是缓慢的，在 大O时间复杂度和空间复杂度， 将展示给面试官，你明白 这些问题在编写代码时。 所以，不要怕先拿出最简单的算法 ，然后从那里。 有任何疑问，这么远吗？好吧。 

因此，让我们深入到我们的第一个问题。 “给定一个数组，n为整数，写一个函数，打乱数组 等地方的所有排列的n个整数同样有可能。“ 假设你有一个随机整数发生器 生成的范围内的整数，从0到i，一半范围。 每个人都理解这个问题呢？ 我给你n个整数的数组，我希望你能洗牌。 在我的目录，我写了几个方案，以证明我的意思。 我要洗牌的20个元素的数组， 从-10到+9， 我要你这样输出的列表。 所以这是我已排序的数组中，我希望你能洗牌。 我们将继续这样做。 每个人都明白的问题吗？好吧。 所以这是给你的。 有哪些想法？你能做到这为n ^ 2，N日志N，N？ 开放的建议。 好吧。因此，一个想法，建议由艾美奖， 是第一计算一个随机数，随机整数，从0到20的范围内。 因此，假设我们的数组的长度为20。 在我们的20个元素的图， 这是我们的输入数组。 而现在，她的建议是，创建一个新的阵列， 所以这将是输出数组中。 并在此基础上，我回到兰特 -  所以，如果我是，比方说，17日， 复制17到第一位置的元件。 现在，我们需要删除 - 我们需要将所有元素 过来，使我们有一定的差距结束时，中间没有孔。 现在，我们重复这个过程。 现在，我们选择一个新的0和19之间的随机整数。 我们有一个新的我在这里，和我们这个元素复制到这个位置。 然后我们转移项目结束，我们重复这个过程，直到我们有充分的新的阵列。 该算法的运行时间是什么？ 那么，让我们来看看这方面的影响。 我们的每一个元素转移。 当我们除去这个，我，我们将所有的元素后，到左边。 这是一个O（n）的成本 因为如果我们删除第一个元素？ 因此，对于每个删除，我们会删除 -  每次删除会导致O（n）操作， ，因为我们有n清除，这将导致一个O（N ^ 2）洗牌。 好吧。因此，良好的开端。良好的开端。 

另一项建议是使用一种被称为高德纳洗牌， 或费雪耶茨洗牌的。 它实际上是一个线性时间的洗牌。 的想法是非常相似的。 同样，我们有我们的输入数组， 但我们的输入/输出，而不是使用两个数组， 我们使用的第一部分的阵列来跟踪我们的混洗部， 我们跟踪，然后我们离开的其余我们的阵列的unshuffled部分的。 因此，这里是我的意思。我们开始 - 我们选择的我， 从0到20的一个数组。 我们当前的指针指向第一个索引。 我们选择了一些我在这里 现在我们交换。 因此，如果这是5，这是4， 生成的数组将有5个在这里和这里。 现在，我们注意到这里的标志。 一切的左侧洗牌， 是unshuffled的一切权利。 现在，我们可以重复这个过程。 我们选择一个1到20之间的随机指数现在。 因此，假设我们的新的，我是在这里。 现在，我们交换这方面，我在这里与我们目前的新位置。 所以，我们做了这样的交换来回。 让我的代码，使之更加具体。 我们从我们的选择我 -  我们开始与我等于0，我们选择一个随机的位置j 在unshuffled一部分阵列，i到n-1。 所以，如果我在这里，在这里，其余的阵列之间选择一个随机指数， 和我们交换。 这是所有的代码需要重新洗牌您的阵列。 有什么问题吗？ 

那么，一个需要的问题是，为什么这是正确的吗？ 为什么每个排列同样有可能吗？ 我不会去通过证明了这一点， 但在计算机科学的许多问题可以证明，通过诱导。 你们有多少人是熟悉的感应吗？ 好吧。酷。 所以，你可以通过简单的归纳证明该算法的正确性， 归纳假设，假设 我的iPod Shuffle将返回每个置换同样可能 到第i个元素。 现在，我+ 1。 我们选择我们的指标j交换的方式， 这导致了 - 然后你工作的细节， 至少充分证明了该算法返回的原因 每个排列以同样可能的概率。 

好吧，下一个问题。 因此，“给定一个整数数组，阳性，零，负， 写一个函数，计算的最高金额 的的任何continueous子数组的输入数组。“ 这里的一个例子是，在所有的数字是正的情况下， 那么目前最好的选择是采取全阵列。 1，2，3，4，等于10。 当你有一些底片，在那里， 在这种情况下，我们只是想第一 因为选择-1和/或-3带给我们的一笔。 有时候，我们可能要开始的数组中。 有时候，我们要选择什么都没有，最好不要采取任何。 有时，它采取的秋天， 因为事情后，超级大。因此，任何想法吗？ （学生，不知所云）>>呀。 如果我不采取-1。 任我选择1000和20000， 我只是选择了3亿美元。 那么，最好的选择是把所有的数字。 这个-1，尽管是消极的， 整个的总和比我不采取-1。 所以我前面提到的秘诀之一是要清楚地陈述明显 和暴力的解决方法。 蛮力解决方案，在这个问题上是什么？是吗？ [简]嗯，我觉得蛮力解决方案 将添加所有可能的组合（不知所云）。 记者：好。因此，简的想法是采取一切可能的 -  我释义 - 是采取一切可能的连续子数组， 计算其总和，然后采取所有可能的连续子数组的最大。 什么唯一地标识一个在我的输入数组子数组？ 一样，我需要做两件事情吗？是吗？ （学生，不知所云）>>右。 指数和上界指标的下限 唯一确定一个连续的子数组。 [女学生]我们估计它是一个数组的唯一的数字？ [于]第所以，她的问题是，我们假设我们的阵列 -  是我们的一系列独特的数字，答案是否定的。 

如果我们用我们的蛮力解决方案，然后开始/结束指数 我们唯一确定的连续子数组。 因此，如果我们遍历所有可能的启动条目， 所有项目>或=开始，和<N， 你计算的金额，然后我们的最高金额，到目前为止，我们已经看到的。 这是清楚了吗？ 该解决方案的大O是什么？ 在时间上。 不太N ^ 2。 请注意，我们遍历从0到n， 所以这是一个用于环路。 我们再次重复几乎从开始到结束，另一个循环。 而现在，在那个，我们要总结每一个项目， 所以这是一个循环。因此，我们有三个嵌套的for循环，n ^ 3个。 好吧。这正好为出发点。 我们的解决方案是毫不逊色于N ^ 3。 每个人都明白的蛮力解决方案吗？ 

好吧。一个更好的解决方案是使用的动态规划的想法。 如果你把CS124，这是算法和数据结构， 用这种方法，你就会变得很熟悉。 的想法是，尝试建立小问题的解决方案，以第一。 我的意思是，我们目前担心两件事情：开始和结束。 很烦人。如果我们能够摆脱这些参数之一，怎么办？ 一个想法是 - 我们给我们原来的问题， 找到任何子阵列的范围内的最大总和[O，n-1个]。 现在，我们有一个新的子问题，在这里我们知道，在我们目前的索引i， 我们知道我们必须得出结论。我们的子数组必须结束当前索引。 因此，剩下的问题是，我们应该在哪里开始我们的子数组？ 这有意义吗？好吧。 所以，我编码这件事，让我们来看看这是什么意思。 在的codirectory，有一个程序叫子阵， 和需要的项目数， 在我拖着列表，它返回的最大子数组的总和。 因此，在这种情况下，我们的最大子阵列是3。 而这只是用2和1的采取。 让我们再次运行它。这也是3。 但是这一次，注意我们是如何走到3。 我们采取了 - 我们只取3本身 因为它的四周底片两侧， 这将带来一个总和<3。 让我们运行10个项目。 这一次，它是7，我们以领先的3和4。 这一次它是8，和我们得到通过服用1，4及3。 所以如何给你的直觉就可以解决这个转变的问题， 让我们来看看在这个子数组。 我们在此输入数组，我们知道，答案是8。 我们以1，4，和3。 但是让我们看看我们如何实际上得到答案。 让我们来看看在最大的子数组的结束，这些指标。 什么是最大的子数组，结束在第一个位置？ [学生]：零。 >>零。只要不采取-5。 这里将是0。是吗？ （学生，不知所云） 记者：哦，对不起，这是一个-3。 因此，这是一个2，这是一个-3。 好吧。因此，-4，什么是最大的子数组结束位置 -4是在哪里呢？零。 一？ 1，5，8。 现在，我必须结束在位置-2是。 因此，6，5，7，和最后一个是4。 要知道，这些都是我的作品 转换的问题，在这里我必须结束这些指标， 然后我最后的答案是，一个横扫， 的最大数量。 因此，在这种情况下，它的8。 这意味着最大的子阵列端部在这个索引， 和以前在什么地方开始。 每个人都明白这个转换的子数组？ 

好吧。那么，让我们来看看复发。 让我们只考虑前几个项目。 因此，这里是0，0，0，1，5，8。 然后是-2这里，并把它下降到6。 所以，如果我调用的入口位置，我子问题（一） 我怎么能使用到以前的子问题的答案 以回答此子？ 如果我看，让我们说，此项目。 看我怎样才能计算出答案6 阵列和前面的子问题的答案，此数组中的组合？是吗？ [女学生]你把阵列的款项 的位置，所以， 然后添加在当前子。 记者：所以她的建议是看这两个数字， 这个数目和此号码。 所以这个8指的是子问题的答案（I  -  1）。 让我们叫我输入数组A. 为了找到一个最大的子数组，我结束位置， 我有两个选择：我可以继续的子数组 结束在上一个索引，或者开始一个新的数组。 如果我继续开始在以前的指数的子数组， 然后我可以达到的最高金额是前面的子问题的答案 加上当前的数组项。 但是，我也可以选择开始一个新的子阵， 在这种情况下的总和为0。 因此，答案是，子问题我最大的0  -  1，再加上目前的数组项。 这是否复发有意义吗？ 我们的复发，我们刚刚发现的部分问题是，我 是等于前面的子加我最大的数组项， 这意味着继续前面的子阵， 或0，在我目前的指数开始一个新的子阵。 一旦我们建立这个表的解决方案，那么我们最终的答案， 只是做了一个线性扫描整个子问题阵列 的最大数量。 我刚才说的，这是一个确切的实施。 因此，我们创建了一个新的子问题阵列，子。 第一项是0或第一个条目，这两个最大。 而对于其余的子 我们使用我们刚刚发现的确切复发。 现在我们计算我们的子阵列的最大的，这就是我们最终的答案。 

所以多大的空间，我们在该算法中使用吗？ 如果你只有采取CS50，那么你可能没有讨论的空间很大。 嗯，有一点要注意的是，我这里称为malloc的大小为n。 给你什么建议吗？ 该算法采用线性空间。 我们可以做的更好吗？ 有您发现来计算最终的答案是不必要的？ 我想一个更好的问题是，什么样的信息 我们需要随身携带，一路过关斩将，到最后呢？ 现在，如果我们看这两条线， 我们只关心前面的子， 我们只关心我们见过的最大的，到目前为止。 为了计算我们最终的答案，我们不需要整个阵列。 我们只需要在最后一个号码，最后两个数字。 最后的是，一阶数组，最后一个数字的最大数量。 因此，事实上，我们可以融合这些循环 从线性空间不变的空间。 目前的总和到目前为止，在这里，替换子问题，子问题阵列的作用。 因此，目前的总和，到目前为止，前面的子问题的答案。 而这一笔，到目前为止，以我们最大的地方。 我们计算最大的，因为我们走。 因此，我们从线性空间不变的空间， 我们也有一个线性的解决方案，我们的子数组的问题。 

这些类型的问题，你会得到在接受记者采访时。 是什么时间复杂度，空间复杂度是什么？ 你可以做的更好吗？是否有不必要的事情是保持周围吗？ 我这样做是为了突出自己的分析，你应该考虑 你的工作，通过这些问题。 应始终问自己，“我可以做的更好？” 事实上，我们可以做的比这更好的吗？ 排序的一个棘手的问题。你不能，因为你需要 至少读取输入的问题。 因此，事实上，你需要至少读取输入的问题 意味着你不能做的更好不是线性的时间， 你不能这样做比恒定的空间。 因此，这是，事实上，此问题的最佳解决方案。 有问题吗？好吧。 

股市的问题： “n个整数，正的，零或负的给定一个数组， 代表n天的股票价格， 写一个函数来计算最大的利润，你可以使 因为你买入和卖出股票在n天正好是1。“ 从本质上讲，我们希望低买高卖。 我们要找出我们可以做最好的利润。 让我们回到我的头，什么是立即清除，最简单的答案，但它的速度慢？ 是吗？ （学生，不知所云）“是的。 “等你去你看股票价格 在每个时间点上，（不知所云）。 记者：好了，所以她的解决方案 - 她的建议的计算 最低和计算最高不工作 因为之前可能会出现的最高最低。 那么，什么是蛮力解决这个问题呢？ 什么是两件事情，我需要唯一确定的利润，我做吗？右。 蛮力解决方案是 - 哦，所以，我们只需要两天，乔治的建议是 唯一地确定这两天的利润。 因此，我们计算每对，喜欢买/卖， 计算的利润，这可能是负数或正数或零。 计算后遍历所有天对我们最大的利润。 这将是我们最后的答案。 该解决方案将是O（N ^ 2），这是因为n选择2对 -  ，你可以选择结束日期之间的天数。 好了，所以我不打算在这里走了过来蛮力解决方案。 我要告诉你，有一个n日志n解决方案。 什么样的算法你知道这是n日志n？ 这是一个棘手的问题。 

合并排序。合并排序是n日志n， 而事实上，解决这个问题的一种方式是使用 合并排序样的想法，要求，在一般情况下，分而治之。 其思想是，如下所示。 你想计算出最佳的买/卖对的左半边。 你可以做，只是用了为期两天的第n寻找最佳的利润。 然后，你要oompute最好的买/卖对的右半部分， 所以最后n超过两天。 现在的问题是，我们如何合并这些解决方案一起回来吗？ 是吗？ （学生，不知所云） “好了。因此，让我画一幅画。 是吗？ （乔治，不知所云） “没错。乔治的解决方案是完全正确的。 因此，他的建议是，首先计算出最佳的买入/卖出一双， 中出现的左半边，让我们的呼吁，左，从左到右。 百思买/卖对发生在右半。 但是，如果我们只比较这两个数字，我们缺少的情况下 在我们这里买和卖的地方的右半边。 我们买的左半边，销售于右半边。 而最好的方法计算出最佳的买入/卖出对跨越两半 是计算出最小在这里和在这里计算的最大 它们的区别。 因此，在两种情况下，买/卖对只发生在这里， 只有在这里，这三个数字被定义为两半。 因此，我们的算法，我们的解决方案合并到一起， 我们要计算出最佳的买入/卖出对 在我们的左半边买和卖的右半部分。 而最好的方式做到这一点是上半年最低的价格来计算， 在右半边，最高价和它们的区别。 由此产生的利润，这三个数字，你最大的三个， 这是最好的利润，你可以对这些开始和结束的日子里。 在这里，重要的线是红色的。 这是一个递归调用计算的左半边中的回答。 这是一个递归调用计算的右半部分中的回答。 这些两个for循环计算上的左和右半边的最小和最大，分别。 现在，我计算的利润，跨越了两半， 和最后的答案是这三个最大。 好吧。 

所以，肯定的是，我们有一个算法，但更大的问题是， 的时间复杂度是什么？ 为什么我提到合并排序的原因是，这种形式的分裂的答案 一分为二，然后合并我们的解决方案 正是归并排序的形式。 所以，让我去的时间。 如果我们定义了一个函数的t（n）的步骤数 n天， 我们的两个递归调用 每个要花费T（N / 2）， 和这些调用。 现在我需要计算出最小的左半部分， 我可以做n / 2的时间，再加上​​最大的右半边。 所以，这仅仅是N。 然后再加上一些经常性工作。 而这个递推公式 正是归并排序的递推方程。 我们都知道，归并排序是n日志n时间。 因此，我们的算法也n日志n。 本次迭代中是否有意义吗？ 只是一个简单回顾一下： T（N）的步数计算最大的利润 超过n天的过程中。 这样，我们分手了递归调用 是第n / 2天致电我们的解决方案， 所以这是一个电话， 然后我们再次呼吁对下半年。 所以，这两个通话。 然后，我们找到一个最低的左半边，这是我们可以做的线性时间， 发现的最大的右半边，这是我们可以做的线性时间。 因此n / 2 + n / 2个是仅仅局限于N。 然后，我们有一些固定的工作，这是像做算术。 这个递推公式是完全合并排序的递推方程。 因此，我们的洗牌算法是n日志n。 因此，我们使用了多少空间？ 让我们回去的代码。 

一个更好的问题是，多少个堆栈帧，我们曾经有在任何给定的时刻吗？ 因为我们使用了递归， 堆栈帧的数量决定了我们的空间使用情况。 让我们考虑n = 8。 我们称之为洗牌月8日， 这将调用洗牌的前四个条目， 这将调用一个洗牌的前两个项目。 因此，我们的协议栈是 - 这是我们的协议栈。 然后，我们呼吁再次洗牌月1日， 这就是我们的基本情况是，所以我们立即返回。 我们有更多的比这多的栈帧吗？ 因为每次我们做了一个调用， 的递归调用重新洗牌， 我们把我们的规模的一半。 因此，堆栈帧的最大数量，我们有过在任何给定的时刻 是的日志n的栈帧顺序。 每个堆栈帧具有恒定的空间， 因此，总的空间量， 我们曾经使用过的最大空间量是O（log n）的空间 其中n是的天数。 

现在，要问自己，“我们可以做的更好？” 特别是，我们可以减少这种一个问题，我们已经解决了吗？ 一个提示：我们只讨论两个问题，在此之前，它不会被洗牌。 我们可以把这个股市的问题，最大的子数组的问题。 如何才能做到这一点呢？ 你们中的一个吗？艾美奖吗？ （艾美奖，不知所云） 记者：没错。 因此，最大的子数组的问题， 我们正在寻找一笔，在一个连续的子数组。 和艾美奖的股票问题的建议，， 考虑更改，或三角洲。 和图片，这是 - 这是一个股票的价格， 但如果我们采取了连续两天之间的差异 -  所以我们看到的最高价格，最大的利润，我们可以使 如果我们在这里买和卖在这里。 但是让我们看看在连续 - 让我们来看看子数组的问题。 所以在这里，我们可以 - 从这里到这里， 我们有一个积极的变化，然后再从这里到这里，我们有一个负面的变化。 但是，然后，从这里到这里，我们有一个巨大的积极变化。 这些变化，我们要总结，让我们的最终利润。 然后，我们在这里有更多的负面变化。 我们最大的子数组的问题的关键在于减少我们的库存问题 考虑天之间的增量。 因此，我们创建了一个新的数组三角洲， 初始化为0的第一个条目， ，然后为每个三角洲（I），那一定是在差异 我的输入数组（I），和数组（I  -  1）。 然后，我们呼吁我们的常规程序的最大子数组 通过三角洲的阵列中。 而且，由于最大的子数组是线性时间， 这种减少，在这个过程中，创建此增量阵列， 也是线性的时间， 那么股票的最终解决方案是O（n）的工作，加上O（n）的工作，仍然是O（n）的工作。 因此，我们有一个线性时间解决我们的问题。 是否每个人都明白这个转变？ 

在一般情况下，一个好主意，你应该始终有 尽量减少一个新的问题，你看到。 如果它看起来很像一个老问题， 请尝试降低到一个老问题。 如果你能使用所有的工具，你已经使用的老问题 要解决的新问题。 因此，包装，技术面试是具有挑战性的。 这些问题可能​​是一些比较困难的问题 你可能会看到在接受记者采访时， 所以，如果你不明白，我只是涵盖的所有问题，也没关系。 这些是一些更有挑战性的问题。 实践，实践，再实践。 我给了很多的讲义中存在的问题，所以一定要检查出这些。 祝你好运，你的采访。我所有的资源都贴在这个环节， 我的高中朋友提供了做模拟技术访谈 所以，如果你有兴趣，电子邮件将姚明的电子邮件地址。 如果你有问题，你可以问我。 你们是否有具体问题，相关技术访谈 到目前为止，我们已经看到的任何问题？ 好吧。那么你的采访，祝你好运。 [CS50.TV]