FaceBook的三道Python面试真题！肝了半天真的没做出来！-技术圈

大家好，我是菜鸟哥！学Python走起！

Facebook作为全球顶尖的科技公司之一，拥有超过52000名员工。很少能有公司在晋升空间和福利上与Facebook匹敌。能够进入到Facebook公司，成为Facebook的一名码农，是很多人梦寐以求的事情。

秋招季马上就要到了，我们先拿三道Facebook的python面试真题来练练手，体会一下Facebook的题。反正我是做了半天，没有全都做出来。

1.将零移动到左侧

题目描述：将给出整数列表array中的“0”全部移动到最左侧，同时保证其他列表元素的顺序不变。

时间复杂度：O(n)空间复杂度：O(1)

解题思路：

首先，题目指出空间的复杂度为O(1)，表明需要在原列表中进行修改，因此我们可以利用双指针的思路来解题。

1).设置read_index和write_index的两个索引，都指向最后一个元素。

2).read_index向前走，如果指向了“0”值，就继续向前，否则,array[write_index]=array[read_index],同时write_index向前走一步。

3).当read_index走到array的头部时，则将write_index之前(包括write_index)的数值全部赋值为0。

程序展示:

程序中，根据解题思路的每一个步骤，都有对应的程序答案，从结果中也可以看出，输出结果正确。问题思考：

如果没有空间复杂度和时间复杂度的限制，这道题是非常容易的，但是通过添加限制，更能体现出一个笔试者的水平。

2.合并重叠区间

题目描述：题目给出一个区间间隔组成的列表array，每一个间隔代表一个小的区间，列表中的间隔都是按照第一个数字进行排序的。合并这些区间，找出这些区间的并集。

时间复杂度：O(n)。空间复杂度：O(n)。

解题思路：这道题目可以利用线性的扫描算法来进行解决。

1.对于每一个区间间隔，进行逐个的空间叠加，设置列表中的第一个间隔为输出间隔。

2.如果下一个间隔的区间和输出间隔有交集，那么就更新输出间隔的最大值。

3.如果下一个间隔的区间和输出间隔没有交集，那么将下一个间隔区间来添加到最终的结果中。程序展示

程序实现的功能如下图所示:

程序中首先判断输入的array长度是否是大于等于2，然后按照我们的解题思路，给出了程序解答。问题思考：

这道题的一个重要点在于按照第一个数值对区间进行排序，当然题目给出的列表是已经排好序的。根据区间的数值判断，就可以很快的得到解题思路。

3.单词拆分

题目描述：给定一个输入的单词string和一个单词列表array，判断string能否拆分为array中的单词组合。

时间复杂度：O(2的n次方)

空间复杂度：O(n的平方)

上图的单词展示中，applepie可以被拆分为apple 和pie的单词组合，applepear则可以被拆分为apple和pear的组合方式。

解题思路：

这道题可以利用动态规划的算法思想来进行解决。

我们以“applepie”这个单词为例,单词列表array=["apple", "apple", "pie", "pear"]：1).设置dp = [True, False, False, False, False, False, False, False, False]，dp长度为len("applepie") + 1。

2).由于"apple" in array，所以dp =[True, False, False, False, False, True, False, False, False]。也就是dp[5] = True。

3).从dp[5]开始搜寻，由于pie in array，所以有dp =[True, False, False, False, False, True, False, False, True],也即dp[8] = True。

4).返回最终的dp[-1]的结果，表示的单词string能否被拆分。

程序展示：

程序中，创造动态规划的数组，然后通过判断数组中每一个位置是否为True，进行下一步的计算，最终输出dp[-1]的接过来判断string能否被拆分。

问题思考：这道题的动态规划思路，可以当作一个跳一跳的小游戏，从string的初始位置，能否按照array中单词的顺序跳到下一个位置，如果有，说明能够被拆分，如果没有，则证明无法被拆分。

总结

通过以上三道Facebook的面试真题分享，可以发现，考察的点都是我们平时刷题学习遇到的知识点，这更提示了我们，需要打好自己的基础，从容应对笔试。希望找工作的小伙伴，都能够找到自己心仪的工作！




推荐阅读:
入门: 最全的零基础学Python的问题  | 零基础学了8个月的Python  | 实战项目 |学Python就是这条捷径

干货:爬取豆瓣短评，电影《后来的我们》 | 38年NBA最佳球员分析 |   从万众期待到口碑扑街！唐探3令人失望  | 笑看新倚天屠龙记 | 灯谜答题王 ｜用Python做个海量小姐姐素描图 ｜碟中谍这么火，我用机器学习做个迷你推荐系统电影

趣味:弹球游戏  | 九宫格  | 漂亮的花 | 两百行Python《天天酷跑》游戏!

AI: 会做诗的机器人 | 给图片上色 | 预测收入 | 碟中谍这么火，我用机器学习做个迷你推荐系统电影

小工具: Pdf转Word，轻松搞定表格和水印！ | 一键把html网页保存为pdf！|  再见PDF提取收费！ | 用90行代码打造最强PDF转换器，word、PPT、excel、markdown、html一键转换 | 制作一款钉钉低价机票提示器！ ｜60行代码做了一个语音壁纸切换器天天看小姐姐！｜

年度爆款文案
1).卧槽！Pdf转Word用Python轻松搞定！
2).学Python真香！我用100行代码做了个网站，帮人PS旅行图片，赚个鸡腿吃
3).首播过亿，火爆全网，我分析了《乘风破浪的姐姐》，发现了这些秘密 
4).80行代码！用Python做一个哆来A梦分身 
5).你必须掌握的20个python代码，短小精悍，用处无穷 
6).30个Python奇淫技巧集 
7).我总结的80页《菜鸟学Python精选干货.pdf》,都是干货 
8).再见Python！我要学Go了！2500字深度分析！
9).发现一个舔狗福利！这个Python爬虫神器太爽了，自动下载妹子图片

点阅读原文,领AI全套资料！