想在谷歌、Facebook、苹果等公司工作？很多时候他们的采访令人望而生畏。不要害怕，我们已经涵盖了他们的常规面试问题。近日，麻省理工学院（MIT）计算机科学与人工智能实验室（CSAIL）新版《程序员面试教程》信息公开。无论您是初级程序员还是经验丰富的专业人士，本课程都适合您。课程链接：http://courses.csail.mit.edu/iap/interview/index.php这门课程主要针对科技公司在面试时经常问到的计算机科学问题，包括时间复杂度，哈希表，二叉树搜索，以及什么会出现在麻省理工学院的“算法设计与分析”（麻省理工学院6.046）课程中。但是，大部分时间会专注于您在课堂上学不到的东西，例如棘手的按位逻辑和解决问题的技巧。面试技巧当被问到一个问题时，开始与面试官交谈，让面试官知道你在想什么。例如，您可能会提供较慢或部分解决问题的方法（让他们知道这不安全），提及对问题的一些观察，或说出任何可能有助于解决问题的想法。如果你卡住了，面试官通常会给你提示。在面试过程中，通常会要求您编写程序。出于某种原因，面试官通常会让某人在黑板或纸上写字，而不是给你一台电脑。所以面试前有必要在板子上练习写代码，以备不时之需。以下是编程面试中的一些注意事项：这些事情要做：如果您对问题不理解或有歧义，请问清楚；让面试官知道你在想什么；提出问题的多种解决方案；与官员交流想法（例如关于数据结构和算法的想法）。如果您遇到困难，不要害怕让他们知道，并礼貌地寻求提示。不要做这些事情：不要放弃！放弃不会帮助您展示解决问题的能力；不要只是静静地坐在那里思考。面试官需要在有限的时间内尽可能多地了解你，不与他们沟通就不能传递任何信息给他们；如果您已经知道问题的答案，请不要脱口而出！否则他们会认为你已经提前阅读了问题并写下了答案。至少假装想了一会儿再给出答案。好吧，如果你对自己的考试准备有信心，这里有一些经典问题：问题1：硬币拼图假设你有8个大小相同的硬币，但其中1个比其他7个稍重（但你不知道不知道具体是哪一个）。同时，你还有一个老式的天平，可以给你称重，找出哪一枚硬币稍微重一点（或者是否重量相同）。那么，找到较轻的硬币最少需要称多少次呢？极好的答案：从8个硬币中取出6个，分别将3个放在天平的左右盘上。这样一来，就会出现三种情况：如果天平左边的3枚硬币比右边重，则较重的硬币在左边；如果天平右侧的3个硬币比左侧重，则较重的在右侧；如果天平左右两盘的重量相同，则称取剩余的2个硬币，取稍重的硬币。不好回答：取4个硬币分别放在天平的左右盘上，找出较轻的一组（4个硬币），把这组硬币分成两组分别放在天平的左右盘上平衡，找出较轻的一组（2件），再次重复此步骤，找到最轻的一组。问题2：在数组中查找给定一个已排序的整数数组，如何找到特定整数x的位置？优秀的答案：使用二进制搜索。将数组中间的数字与x进行比较。如果相同，则找到x。如果数组中的数字较大，则需要查看数组的后半部分。如果数字很小，则需要查看数组的前半部分。通过将数组的中间元素与x进行比较，我们可以重复搜索数组的前后部分，再次将搜索范围缩小2倍。我们重复此过程，直到找到x。该算法需要O(logn)时间。不太好的答案：按顺序遍历数组的每个数字，与x进行比较。该算法需要O(n)时间。问题3：AtoI写一个函数将字符串转换为整数（这个函数叫做AtoI或atoi()），因为我们要将ASCII字符串转换为整数。优秀答案：从头到尾查看整个字符串。如果***字符是减号，请将其写下来。累计求和从0开始，每得到一个新数，就将总数乘以10，加上新数。计算完成后，返回当前总数，或者在负号的情况下，返回该数字的倒数。温馨的回答：另一种方法是从头到尾查看整个字符串，然后再次进行累加。记住数字x代表你当前所在的数字，x从1开始。对于每个字符，将当前数字乘以x并添加到运行总数中，同时将x乘以10。当你到达字符串的开头时，返回当前总数，或者如果出现减号，则返回该数字的倒数。注意：面试官可能会问到你自己方法的局限性。您应该回答：只有当字符串在每个数字前包含一个可选的减号时，此方法才有效。另外，你应该提到：如果数字太大，结果将因溢出而不正确。问题4：反转字符串中单词的顺序编写一个函数来反转字符串中单词的顺序。答案：交换第一个和最后一个字符、第二个和最后一个字符等的顺序，反转整个字符串。之后，查看整个字符串中的空格，这样您就可以发现每个单词的位置。再次将第一个单词的顺序与倒数第一个单词交换，第二个单词与倒数第二个单词交换，依此类推，颠倒您遇到的每个单词的顺序。问题5：最近邻假设您有一个包含n个个体的数组。每个人都由一个字符串（他们的名字）和一个数字（他们在数字行上的位置）表示。每个人有3个朋友，也就是号码最接近他的三个人。编写一个算法，找出每个人的三个朋友。优秀答案：按照每个人的编号升序对数组进行排序。再看每个人旁边的三个人，他们的朋友就会出现在这六个人当中。该算法需要O(nlogn)时间，因为对人进行分类也需要那么多时间。问题6：洗牌问题给定一组不同的整数数组，给出一个随机排序这些整数的算法，使得每种重新排序方法的可能性相同。换句话说，给定一副纸牌，您如何洗牌以使每张纸牌排列的可能性相同？优秀答案：将元素按顺序排列，用数组中某个元素之前没有出现的随机元素与这个元素交换。所需时间为O(n)。请注意，这个问题有多个可能的答案，还有几个看起来不错但实际上并不正确的答案。例如，对上述算法稍作修改，将每个元素与数组中的任意元素交换并不能确保每个重排顺序以相等的概率发生。这里给出的答案是（笔者认为的）***答案。如果想知道其他答案，可以在维基百科上搜索“Shuffling”。问题7：单向链表中的循环如何判断单向链表是否有循环？优秀答案：跟踪链表中的两个指针，并从链表的开头开始。在算法的每次迭代中，第一个指针向前移动一个节点，第二个指针向前移动两个节点。如果两个指针始终相同（不在算法的开头），则存在循环。如果指针在两个指针相同之前到达链表的末尾，则链表中没有循环。实际上，指针不需要一次移动一个或两个节点；指针也不需要以不同的速率移动。这个过程需要O(n)时间。这是一个聪明的答案，面试官会以某种方式喜欢它。舒适的答案1：对于您在遍历链表时遇到的每个节点，在O(1)中放置一个指向该节点的指针-查找时间数据结构，如哈希集。接下来，当您遇到一个新节点时，请检查您的哈希集中是否已存在指向该节点的指针。这个过程需要O(n)时间，但也需要O(n)空间。得心应手的答案2：浏览链表中的元素。“标记”您到达的每个节点。如果在到达终点之前到达标记节点，则链表有环，否则无环。这个过程也需要O(n)的时间。请注意，这个问题在技术上是不合适的。正常的链表不会有循环。它们的意思是让您决定是否可以从包含最多具有一条出边的节点的图中的节点到达循环。问题8：计算2^x如何快速计算2^x？优秀答案：1<
