[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]