googleFacebook面试官:如何在算法面试中游刃有余?

facebook面试题集合

先一起来看看题目:

题目描述

Given an array of integers and an integer k, you need to find the tot!al number of contiguous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2Output: 2

[1, 1, 1]

[1, 1, 1]

考点解析

在访谈中,我们经常遇到一种类型的问题,该问题与输入数组中的所有子数组总和有关。

在这种类型的问题中,我们可以使用一种非常常见的预计算方法来优化: prefixSum array。

今天的练习进行了解释,我们将重点解释:

如何使用prefixSum数组的思想非常有效地解决Subarray Sum等于K的问题。

接下来,我们请严先生为我们详细解释该问题的答案:

主讲人:闫老师

来提供金老师

前Google高级程序员,面试官

多年来Google表现最佳


解题思路

在这个问题上,严老师解释了三种不同的解决方案, 从最幼稚的解决方案到优化的解决方案。并逐步解释该问题的优化过程

解决方案1:天真的解决方案

解决问题,这是我们可以快速想到的最直接的方法之一:

查找输入数组的所有可能的子数组,然后确定每个子数组的总和是否等于k。

一种更猛烈的方法是使用三层for循环,找到所有可能的子数组,然后遍历子数组中的每个数字以计算子数组的总和。

解决方案2:更好的解决方案

从先前的解决方案中,我们可以看到更明显的优化是 减少重复计算

在朴素的解决方案中,当计算子数组的总和时,我们需要每次遍历子数组中的每个数字。实际上,有很多重复。

以子数组(i,j)为例(i是子数组的起点,j是终点):

当i = 0,j = 1时,您需要遍历 nums[0], nums[1]

当i = 0,j = 2时,您需要遍历 nums[0], nums[1] , nums[2]

显然,前两个数字已经遍历了很多次。图中的蓝色部分是重复遍历的元素。

因此,减少重复的一种方法是 保存先前计算的子数组(i,j)的总和,当j ++时,我们只需要在原始总和的基础上添加新的nums [j] ,达到减少重复遍历的目的,还降低了时间复杂度。

解决方案3:线性解决方案

为了进一步优化,我们将使用非常重要的预计算技术: prefixSum array。

与prefixSum数组的每个索引对应的值与初始输入数组具有对应的关系:

通过这个prefixSum数组,我们可以使用 O(1) 是时候找到任何子数组的和了:

sum of subarray(i, j) = prefixSum[j] - prefixSum[i - 1]

请注意,上图中的红色0是在i == 0时求解子数组(i,j)的和,则相应的prefixSum [i-1]应为0

使用prefixSum数组,此问题变为

对于每个j:多少 i < j satisfies prefixSum[i] = prefixSum[j] - k

这意味着对于每个j,我们需要记录所有先前的prefixSum,然后在这些prefixSum == prefixSum [j] -k中找到多少个值

这是一个查找操作。为了更有效地解决此问题,我们可以使用 HashMap:

key: prefixSum value

value: number of occurence of the prefixSum value。

在实际的实现中,我们发现从左到右遍历整个数组,我们可以 只需要一个prefixSum变量 要按顺序计算所有prefixSum值并将其存储在HashMap中,无需事先计算整个prefixSum数组。

代码实现

请注意算法和代码中处理和分析时间和空间的细节。请观看视频进行解释。

E/N/D
有关更多技术求职信息,请关注“请柬”

“给您两个文件a和b。它们分别存储50亿个URL,每个URL占用64个字节,内存限制为4G。请编写代码以在文件a和b中找到相同的URL。”这是2016年秋季针对一家大公司的笔试。

您可以停下来想一想,如果您在面试时如何回答这个问题。 50亿个URL(每个64字节)加起来达到320G。使用大脑的最简单方法当然是将它们全部加载到内存中并直接进行比较,但是,如此大量的数据绝对是不可能的。

为了进行进一步的分析,您可能会考虑拆分文件,对URL进行排序,然后逐步进行分析和比较。但是,拥有如此大量的数据,该怎么办呢?这次绝对是面试官测试您的关键点。您不能总是说我将50亿个URL从前到后依次分为2000个文件,然后逐个比较每个文件。几次,结果出来了。是的,它可以工作,但这意味着您被淘汰了。

实际上,对于此类面试问题,面试官希望了解您是否可以想到分而治之,哈希或布隆过滤器等知识点。换句话说,这个问题实际上是算法问题,而不是简单的程序问题。

在面试过程中,许多大公司对候选人的算法能力特别感兴趣。他们甚至让应聘者当场编写代码。原因是算法的基本能力将直接决定程序员的素质。以武术小说为类比,该算法是“内在技能”,并且各种编程框架都像各种“技术”。

是的,算法对程序员来说非常重要。许多程序员发现他们的算法基础不好,所以他们疯狂地去LeetCode刷问题,但是经过一年的刷牙,他们发现他们并没有太大的进步。在面试中,面试官随机更改了问题。他要么紧张要么基础不好。 ,我无法回答。

自从我上大学以来,我就一直热爱算法,并且还获得了ACM亚洲部的金牌。多年来,我对算法的面试问题有很多感触。今天,我希望能够通过视频课程“ Algorithm Interview Clearance 40 Lectures”与您分享我的所有经验,其中包括对典型算法问题的分类和分析,算法理论基础,面试技巧,问题解决技巧等。

我是谁

我叫秦超。我曾在Facebook担任工程师。作为Facebook Messenger技术负责人,我参与了Facebook App,Facebook Messenger,Facebook Phone和其他产品的研发。实际上,在同济大学计算机科学专业学习期间,我对算法和数据结构非常感兴趣。我参加了各种程序竞赛,并在ACM亚洲部获得了金牌。因此,我从美国顶级大学卡内基·梅隆大学毕业后直接加入了Facebook。

在Facebook的三年中,我采访了数百名技术人员,并且在算法访谈的调查要点和问题解决方法方面拥有丰富的第一手经验。回顾互联网上现有的算法,数据结构文章和教科书,它们大多是零散的,并且经常会出现知识覆盖不足或研究内容过多的问题。因此,我希望通过本课程,我将帮助您解决一组算法问题并切入主意。同时,通过白板视频方法,您将带您现场解决问题,帮助您彻底理解问题背后的测试现场,锻炼算法思维,并让您面试以展现您在和平时期的工作技能。

你能获得什么?

“算法面试通过40堂”中共有40堂课。我结合多年的访问员经验,系统地整理和总结了高频知识点和常见的访问者解决问题的想法。完成课程后,您可以从以下四个方面获得收益:

  1. 常用算法知识点的理论解释

    当然,将近40%的空间是算法理论的常见解释。对于技术人员来说,计算机领域的知识理论是广阔的,如何开始?面试中出现的最常见的算法知识点是有规律的。根据我的总结,您应该能够找到学习的提示。

  2. 高频面试题思路分析

    本课程还包括有关高频面试问题的17个实践练习。无论是硅谷公司还是国内一线制造商,在盲目提出问题之前,我都会首先从面试官的角度为您澄清想法,以便您彼此了解并赢得胜利。 。

  3. LeetCode高效的四步问题解决方法

    在大工厂算法访谈中,仅仅给出正确答案是不够的。更重要的是,您应该让面试官看到他的清晰思维和良好的代码素养。我总结了适合大规模算法面试的LeetCode高效的四步问题解决方法。它教您使用标准化流程来处理面试中的算法调查,并帮助您脱颖而出。

  4. 有效提高算法面试合格率

    在过去的几年中,我一直致力于帮助更多的技术人员获得理想的报价。参加过我以前的辅导的学生将面试合格率提高了几何倍数。在硅谷和国内顶级互联网公司中获得报价的成功率得以保持。高于95%。我相信,只要您认真学习了这种算法面试通关方法,就不会离您最喜欢的公司的报价很近。

在这里见,发送精心准备的超级干货礼品包。

金额〜我已经准备了至少半年的时间。给予主题经验:

首先,强烈建议使用“标题策略”。今年有数十家公司开会,大多数问题都是原始问题。那么问题库在哪里?按照循序渐进的原则,一一介绍:
1. cc150,全名破解了编码面试-150编程问题与解答。在经典著作中,有人曾经什么都不做,刷了三到四遍这本书,然后接受了Google的报价(请注意,它在美国,甚至在中国...)这本书的优势在于在本章中,本章重点介绍了一些知识,对主题进行了精炼,并且很容易找到答案;缺点是您编写的代码需要深入检查,而cc150不是在线判断者。
2. leetcode。第一个供程序员审查面试问题的网站,有越来越多的问题,并且收取少量问题。刷的人很多,答案很容易找到。在线法官可以深入检查代码的正确性,刷leetcode是锻炼算法功能的最佳方法。如果时间有限,那么只能刷一次,必须是leetcode,如果有足够的时间... ljcode,meetqun和其他主要面试问题OJ欢迎您,此外还有许多国内外大学OJ。
----------------------------------------------------------------------------------------------------------------------------------------
以上是这两个主要力量,但是仅靠这两个力量无法达到“称职之海”的水平,并且由于其声誉,一些公司有时会避免内部出现问题。来吧,我们继续寻找问题。
3.编程的美感和精巧的技巧:将其视为两个问题集。有些问题用1、2重复,但是大多数问题仍然非常好并且很聪明。 重点是交叉对比,您将知道哪些是经典主题。
4. Careercup,Zunzhun.com等:每个公司都有自己喜欢的主题。这些网站可让您方便地找到面孔并跟踪公司的发展趋势。
5.“法律结构”博客:七月上帝的博客内容丰富,可以学习一年。这里只说说算法问题:“微软面试100个问题”(实际上几乎是500个问题)系列,可以称为算法问题的大型宝库,包罗万象,而且很多问题都很新,面试官的类型喜欢...但是,本系列的版面有些混乱,许多问题没有答案; “编程的编程艺术”系列非常详细,适合深入学习某些算法; “教您如何快速杀死:99%的海量数据处理面试问题”,非常实用的海量数据处理面试文章。
6.经典的库函数。由于有很多测试(例如atoi,strstr,memcpy等),因此分开介绍了这一部分。在“程序员的编程艺术”中,有许多相关的讨论,最好是自己组织起来。
------------------------------------------------------------------------------------------------------------------------------------------

好了,这些足以解决我们的问题。让我们讨论一下哪些是本主题的重点。
1.最高优先:面对。这比什么都重要。为了节省招聘成本,通常不会勤奋地改变同一家公司的问题。
2.子优先级:非常经典的主题。什么是经典?早些时候我写了123456。如果某个问题可以重复几次,那绝对是不朽的经典(例如atoi,LCS,LPS,单链表倒置...)。毕竟,经典问题是最常见的,必须非常熟练。
3.再说一遍:简短一点(在50行之内),一个较新的话题。 访调员通常时间有限,没有时间让您写几百行,因此最好约50行。
4.最后:一个答案很长的问题。这种主题通常不可用。如果结果出来,那通常是结局。为了进行最终检测...通常,很长的主题很容易弄乱,并且在子模块中写得很慢。
------------------------------------------------------------------------------------------------------------------------------------------

仅靠IDE不够,您必须练习纸上书写。
如果您做更多的事情,您会感到这些问题是相同的……无非就是dp,二分法,排序,递归……无非就是打开数组,调整函数,使用stl……然后主题就会意识到 算法问题只是公司招聘的一个选择,因为没有其他方法可以毕业,这是最简单,最粗鲁和最有效的方法。但是,在实际工作中,最重要的是项目能力。 要理解这个事实,应该培养这个主题以取得积极的成果。

推荐阅读

tags

最新发布