看看最重要的Facebook代码面试问题
本文由Amanda Fawcett撰写，最初发表于Educative，Inc.。
对于全球许多开发人员而言，在Facebook上找到工作是一个梦想。 Facebook是全球顶尖的科技公司之一，拥有超过52,000名员工。 Facebook以其基于增长的公司文化，快速的晋升轨道，出色的收益以及很少有公司能比得上的高薪而闻名。
但是竞争非常激烈，并且随着新员工的涌现，Facebook正在寻找最优秀的候选人。 Facebook专注于您的文化适应性，通才知识，在限制条件下构建的能力以及专业的编码技能。
为了帮助您做好准备，今天我将逐步介绍您完成Facebook面试所需的一切，包括编码问题和分步准备指南。
今天我们将回顾：
· Facebook编码面试概述
· 前40个Facebook编码面试问题
· 如何准备面试
· 总结
Facebook代码面试概述
要在Facebook上从事软件工程工作，您需要知道未来会发生什么。 您准备得越充分，您就会越有信心。 因此，让我们对其进行分解。
· 面试时间表：从简历提交到工作机会，整个过程持续1.5到2个月。
· 面试类型：面试过程包括6到7个采访。 其中包括1次屏幕前面试（20分钟），1次技术电话面试（50分钟，1-2个编码问题）和4-5次现场面试（每次45分钟）。
· 现场面试：Facebook将现场面试分为三个部分。 忍者部分由使用白板进行的两次编码面试组成。 海盗部分包括2个系统设计面试。 绝地部分包括1次文化/行为面试。
· 编码问题：Facebook面试问题着重于算法，数据结构和时间复杂度方面的通才知识。 他们还测试了体系结构和系统设计（甚至是入门级）。
· 招聘级别：Facebook通常以E3级别聘用入门级软件角色，而E9则落后于级别。 E5被认为是入门级经理角色。
· 招聘团队：Oculus，Facebook Groups和WhatsApp的*招聘。
· 编程语言：Facebook首选大多数标准语言，包括Java，C ++，Python，Ruby和Perl。
Facebook面试有什么不同？
系统设计面试：但是，在Facebook上，无论您要面试哪个级别，都可以期待这些问题。
结构化的面试：Facebook将使您与担任您面试职位的面试官或直接与您要面试的职位一起工作的人员配对。
核心价值观和您的行为面试：Facebook面试官还将评估您体现其五个核心价值观的能力：快速行动，勇于创新，专注于影响力，开放并建立社会价值。
前40个Facebook编码面试问题
在本节中，我们将深入探讨40个编码面试问题。 我们将在面试中讨论您必然会遇到的15个问题的答案和运行时的复杂性，然后列出您可能会遇到的25个问题的权威列表。
如左图所示，Facebook主要关注数组和字符串。 这些是掌握的基本技能。 每个问题都将在Python 3中解决。要在C ++，Ruby，Java和JavaScript中查看这些解决方案，请访问此处。
数组：向左移动零
给定一个整数数组，将所有为0的元素向左移动，同时保持数组中其他元素的顺序。 数组必须就地修改。
def move_zeros_to_left(A):
if len(A) < 1:
return
lengthA = len(A)
write_index = lengthA - 1
read_index = lengthA - 1
while(read_index >= 0):
if A[read_index] != 0:
A[write_index] = A[read_index]
write_index -= 1
read_index -= 1
while(write_index >= 0):
A[write_index]=0;
write_index-=1
v = [1, 10, 20, 0, 59, 63, 0, 88, 0]
print("Original Array:", v)
move_zeros_to_left(v)
print("After Moving Zeroes to Left: ", v)
运行时复杂度：线性，O（n）O（n）
内存复杂度：常量，O（1）O（1）
保留两个标记：read_index和write_index并将它们指向数组的末尾。 让我们看一下该算法的概述。
将read_index移向数组的开头时：
· 如果read_index指向0，则跳过。
· 如果read_index指向非零值，则将read_index处的值写入write_index并递减write_index。
· 为write_index之前的所有值以及write_index的当前位置分配零。
数组：合并重叠的间隔
您会得到一个间隔对数组（列表）作为输入，其中每个间隔都有开始和结束时间戳记。 输入数组按开始时间戳排序。 您需要合并重叠的间隔并返回新的输出数组。
考虑下面的输入数组。 间隔（1、5），（3、7），（4、6），（6、8）重叠，因此应将它们合并为一个大间隔（1、8）。 同样，间隔（10，12）和（12，15）也重叠，应合并为（10，15）。
class Pair:
def __init__(self, first, second):
self.first=first
self.second=second
def merge_intervals(v):
if v==None or len(v)==0 :
return None
result=[]
result.append(Pair(v[0].first, v[0].second))
for i in range(1, len(v)):
x1=v[i].first
y1=v[i].second
x2=result[len(result) - 1].first
y2=result[len(result) - 1].second
if y2 >=x1:
result[len(result) - 1].second=max(y1, y2)
else:
result.append(Pair(x1, y1))
return result;
v=[Pair(1, 5), Pair(3, 1), Pair(4, 6),
Pair(6, 8), Pair(10, 12), Pair(11, 15)]
result=merge_intervals(v)
for i in range(len(result)):
print("[" + str(result[i].first) + ", " + str(result[i].second) + "]", end=" ")
运行时复杂度：线性，O（n）
内存复杂度：线性，O（n）
这个问题可以通过简单的线性扫描算法解决。 我们知道输入是根据开始时间戳排序的。 这是我们遵循的方法：
· 给出了输入间隔的列表，我们将合并的间隔保留在输出列表中。
· 对于输入列表中的每个间隔：
· 如果输入间隔与输出列表中的最后一个间隔重叠，则我们将合并这两个间隔，并使用合并的间隔更新输出列表中的最后一个间隔。
· 否则，我们会将输入间隔添加到输出列表中。
树：将二叉树转换为双向链表
将二叉树转换为双向链表，以便双向链表的顺序与按顺序遍历二叉树的顺序相同。
转换后，该节点的左指针应指向双向链接列表中的前一个节点，而右指针应指向双向链接列表中的下一个节点。 在查看解决方案和解释之前，请先尝试一下。
# merge(fuse) two sorted linked lists
def concatenate_lists(head1, head2):
if head1==None:
return head2
if head2==None:
return head1
# use left for previous.
# use right for next.
tail1=head1.left
tail2=head2.left
tail1.right=head2
head2.left=tail1
head1.left=tail2
tail2.right=head1
return head1
def convert_to_linked_list(root):
if root==None:
return None
list1=convert_to_linked_list(root.left)
list2=convert_to_linked_list(root.right)
root.left=root.right=root
result=concatenate_lists(list1, root)
result=concatenate_lists(result, list2)
return result
def get_list(head):
r=[]
if head==None:
return r
temp=head
while True:
r.append(temp.data)
temp=temp.right
if temp==head:
break
return r
def test(orig_data):
root=create_BST(orig_data)
all_data=bst_to_list(root)
#print(all_data);
head=convert_to_linked_list(root)
#print_list(all_data)
#print_list(v)
return head
def main():
data=[100,50,200,25,75,350]
res=test(data)
v=get_list(res)
print_list(v)
main()
运行时复杂度：线性，O（n）
内存复杂度：线性，O（h）
递归解决方案具有O（h）内存复杂性，因为它将消耗堆栈上的内存，直到二叉树h的高度。 对于平衡树，它将为O（log n），在最坏的情况下可以为O（n）。
在有序遍历中，首先遍历左侧的子树，然后访问根，最后遍历右侧的子树。
解决此问题的一种简单方法是从一个空的双向链表开始。 在对二叉树进行有序遍历时，请始终将每个元素输出插入到双向链表中。
但是，如果我们仔细地看问题，访问者希望我们将二叉树就地转换为双向链表，即我们不应该为双向链表创建新节点。
可以使用分而治之的方法递归解决此问题。 下面是指定的算法。
· 从根节点开始，递归求解左右子树
· 在每个步骤中，一旦左右子树已处理完毕：
· 将左子树的输出与根融合，以得到中间结果
· 将中间结果（在上一步中构建的结果）与右侧子树的输出融合在一起，以得出当前递归调用的最终结果。
树：二叉树的层级顺序遍历
给定二叉树的根，显示每个级别的节点值。 所有级别的节点值应在单独的行上显示。 让我们看一下下面的二叉树。
该树的级别顺序遍历应如下所示：
· 100
· 50、200
· 25、75、350
# Using two queues
def level_order_traversal_1(root):
if root==None:
return
queues=[deque(), deque()]
current_queue=queues[0]
next_queue=queues[1]
current_queue.append(root)
level_number=0
while current_queue:
temp=current_queue.popleft()
print(str(temp.data) , end=" ")
if temp.left !=None:
next_queue.append(temp.left)
if temp.right !=None:
next_queue.append(temp.right)
if not current_queue:
print()
level_number +=1
current_queue=queues[level_number % 2]
next_queue=queues[(level_number + 1) % 2]
print()
arr=[100,50,200,25,75,350]
root=create_BST(arr)
print("InOrder Traversal:", end="")
display_inorder(root)
print("
Level Order Traversal:
", end="")
level_order_traversal_1(root)
运行时复杂度：线性，O（n）
内存复杂度：线性，O（n）
在这里，您正在使用两个队列：current_queue和next_queue。 您根据当前级别编号交替推送两个队列中的节点。 您将使节点从current_queue中出队，打印该节点的数据，并将该节点的子节点排入next_queue。
一旦current_queue变为空，就已经为当前的level_number处理了所有节点。 要指示新级别，请打印一个换行符（ n），交换两个队列，并继续上述逻辑。
从current_queue打印叶子节点后，交换current_queue和next_queue。 由于current_queue将为空，因此您可以终止循环。
字符串：句子中的反词
反转给定句子中的单词顺序（字符数组）。 以" Hello World"字符串为例：
def str_rev(str, start, end):
if str==None or len(str) < 2:
return
while start < end:
temp=str[start]
str[start]=str[end]
str[end]=temp
start +=1
end -=1
def reverse_words(sentence):
# Here sentence is a null-terminated string ending with char '\0'.
if sentence==None or len(sentence)==0:
return
# To reverse all words in the string, we will first reverse
# the string. Now all the words are in the desired location, but
# in reverse order: "Hello World" -> "dlroW olleH".
str_len=len(sentence)
str_rev(sentence, 0, str_len - 2)
# Now, let's iterate the sentence and reverse each word in place.
# "dlroW olleH" -> "World Hello"
start=0
end=0
while True:
# find the start index of a word while skipping spaces.
while start < len(sentence) and sentence[start]==' ':
start +=1
if start==str_len:
break
# find the end index of the word.
end=start + 1
while end < str_len and sentence[end] !=' ':
end +=1
# let's reverse the word in-place.
str_rev(sentence, start, end - 1)
start=end
def get_array(t):
s=array('u', t)
return s
def print_array(s):
i=0
while i !=len(s):
stdout.write(s[i])
i +=1
print ()
s=get_array('Hello World!')
print_array(s)
reverse_words(s)
print_array(s)
解决方案的工作原理如下：
· 反转字符串。
· 遍历字符串并将每个单词反向。
字符串：字符串分段
您会得到一个单词词典和一个大输入字符串。 您必须找出输入字符串是否可以完全分割成给定字典的单词。 以下示例进一步阐述了该问题。
def can_segment_string(s, dictionary):
for i in range(1, len(s) + 1):
first=s[0:i]
if first in dictionary:
second=s[i:]
if not second or second in dictionary or can_segment_string(second, dictionary):
return True
return False
s="hellonow";
dictionary=set(["hello","hell","on","now"])
if can_segment_string(s, dictionary):
print("String Can be Segmented")
else:
print("String Can NOT be Segmented")
运行时复杂度：如果仅使用递归，则指数为O（2 ^ n）。 借助备忘录，可以将该解决方案的运行时复杂度提高为多项式O（n2）。
内存复杂度：多项式，O（n2）
您可以通过在每个可能的位置处分割大字符串来查看字符串是否可以完全分割为字典中的单词，从而解决此问题。 如果分步编写算法，则将如下所示：
n=length of input string
for i=0 to n - 1
first_word=substring (input string from index [0, i] )
second_word=substring (input string from index [i + 1, n - 1] )
if dictionary has first_word
if second_word is in dictionary OR second_word is of zero length, then return true
recursively call this method with second_word as input and return true if it can be segmented
该算法将在循环的每次迭代中从头计算两个字符串。 最坏的情况是每次都会递归调用second_word。 这将时间复杂度提高到2 ^ n。
您会发现您可能多次计算相同的子字符串，即使字典中不存在该子字符串也是如此。 可以通过备注来修复此冗余，您可以在其中记住已经解决了哪些子字符串。
为了实现记忆，您可以每次将第二个字符串存储在一个新集中。 这将减少时间和内存复杂度。
动态编程：查找最大单笔卖出利润
给定每日股票价格列表（为简单起见，以整数表示），请返回买入和卖出价格以获取最大利润。
我们需要最大化单次买卖利润。 如果我们无法获得任何利润，我们将尽量减少损失。 在下面的示例中，突出显示了（最大）获利的买入（橙色）和卖出（绿色）价格。
current_buy=array[0]
global_sell=array[1]
global_profit=global_sell - current_buy
current_profit=-sys.maxsize - 1
for i in range(1, len(array)):
current_profit=array[i] - current_buy
if current_profit > global_profit:
global_profit=current_profit
global_sell=array[i]
if current_buy > array[i]:
current_buy=array[i];
result=global_sell - global_profit, global_sell
return result
array=[1, 2, 3, 4, 3, 2, 1, 2, 5]
result=find_buy_sell_stock_prices(array)
print("Buy Price: " + str(result[0]) + ", Sell Price: " + str(result[1]))
运行时复杂度：线性，O（n）
内存复杂度：常数，O（1）
数组中的值代表每天的库存成本。 由于我们只能买卖一次股票，因此我们需要找到在给定的时间段内利润最大化（或亏损最小化）的最佳买卖价格。
一个运行时间复杂度为O（n2）的简单的解决方案是在每个元素及其后续元素之间找到最大增益。
有一个棘手的线性解决方案，需要迭代遍历整个股票价格时，保持current_buy_price（这是迄今为止看到的最小数量），current_profit和global_profit。
在每次迭代中，我们都将current_profit与global_profit进行比较，并相应地更新global_profit。
基本算法如下：
current buy=stock_prices[0]
global sell=stock_prices[1]
global profit=global sell - current buy
for i=1 to stock_prices.length:
current profit=stock_prices[i] - current buy
if current profit is greater than global profit
then update global profit to current profit and update global sell to stock_prices[i]
if stock_prices[i] is less than current buy
then update current buy to stock_prices[i]
return global profit and global sell数学和统计：计算数字的幂
给定一个双精度数x和一个整数n，编写一个函数计算x的幂次。 例如：
功率（2，5）=32
功率（3，4）=81
功效（1.5，3）=3.375
功效（2，-2）=0.25
def power_rec(x, n):
if n==0:
return 1
if n==1:
return x
temp=power_rec(x, n//2)
if n % 2==0:
return temp * temp
else:
return x * temp * temp
def power(x, n):
is_negative=False
if n < 0:
is_negative=True
n *=-1
result=power_rec(x, n)
if is_negative:
return 1 / result
return result
def main():
pass_count=0
fail_count=0
for x in range(-10, 5, 1):
for n in range(-4, 6):
if x==0 and n < 0:
continue
r1=power(x * 1.0, n)
r2=pow(x, n)
diff=r1 - r2
if diff < 0:
diff *=-1
if diff > 0.0000000001:
msg="r1=%f, r2=%f, difference=%f" % (r1, r2, diff)
print("Failed for (%d, %d) - %s" % (x, n, msg))
fail_count +=1
else:
pass_count +=1
assert diff <=0.0000000001
main()
print(pow(2, 5))
运行时复杂度：对数，O（log n）
内存复杂度：对数，O（log n）
解决此问题的简单算法是将x乘以n倍。 该算法的时间复杂度为O（n）。 我们可以使用分而治之的方法来更有效地解决此问题。
在除法步骤中，我们将n递归除以2直到达到基本情况，即n==1
在合并步骤中，我们获得子问题的结果r，并使用以下两个规则计算当前问题的结果：如果n为偶数，则结果为r * r * r（其中r为结果 如果n为奇数，则结果为x * r * r（其中r是子问题的结果）。
回溯：查找所有可能的子集
我们得到了一组整数，我们必须找到该整数组的所有可能子集。
def get_bit(num, bit):
temp=(1 << bit)
temp=temp & num
if temp==0:
return 0
return 1
def get_all_subsets(v, sets):
subsets_count=2 ** len(v)
for i in range(0, subsets_count):
st=set([])
for j in range(0, len(v)):
if get_bit(i, j)==1:
st.add(v[j])
sets.append(st)
def main():
v=[8,13,3,22,17,39,87,45,36]
subsets=[]
get_all_subsets(v, subsets);
print("****Total*****" + str(len(subsets)))
for i in range(0, len(subsets)):
print("{", end="")
print(subsets[i], end="")
print("}")
print("****Total*****" + str(len(subsets)))
main()
运行时复杂度：指数，O（2 ^ n * n），其中n是给定集合中整数的数量
内存复杂度：常数，O（2 ^ {n} * n）
有几种方法可以解决此问题。 我们将讨论一种简洁易懂的方法。 我们知道对于一组n个元素有2 ^ n个子集。 例如，具有3个元素的集合将具有8个子集。 这是我们将使用的算法：
n=size of given integer set
subsets_count=2^n
for i=0 to subsets_count
form a subset using the value of 'i' as following:
bits in number 'i' represent index of elements to choose from original set,
if a specific bit is 1 choose that number from original set and add it to current subset,
e.g. if i=6 i.e 110 in binary means that 1st and 2nd elements in original array need to be picked.
add current subset to list of all subsets
注意，从集合中选取整数的位的顺序无关紧要； 从左到右选取整数将产生与从右到左选取整数相同的输出。
图形：克隆有向图
给定有向图的根节点，通过创建其深拷贝来克隆该图，以使克隆的图具有与原始图相同的顶点和边。
让我们以下面的图表为例。 如果输入图是G=（V，E），其中V是一组顶点，而E是一组边，则输出图（克隆图）G'=（V'，E'），使得V=V'和 E=E'。
注意：我们假设所有顶点都可以从根顶点到达。 即我们有一个连通图。
class Node:
def __init__(self, d):
self.data=d
self.neighbors=[]
def clone_rec(root, nodes_completed):
if root==None:
return None
pNew=Node(root.data)
nodes_completed[root]=pNew
for p in root.neighbors:
x=nodes_completed.get(p)
if x==None:
pNew.neighbors +=[clone_rec(p, nodes_completed)]
else:
pNew.neighbors +=[x]
return pNew
def clone(root):
nodes_completed={}
return clone_rec(root, nodes_completed)
# this is un-directed graph i.e.
# if there is an edge from x to y
# that means there must be an edge from y to x
# and there is no edge from a node to itself
# hence there can maximim of (nodes * nodes - nodes) / 2 edgesin this graph
def create_test_graph_undirected(nodes_count, edges_count):
vertices=[]
for i in range(0, nodes_count):
vertices +=[Node(i)]
all_edges=[]
for i in range(0, nodes_count):
for j in range(i + 1, nodes_count):
all_edges.append([i, j])
shuffle(all_edges)
for i in range(0, min(edges_count, len(all_edges))):
edge=all_edges[i]
vertices[edge[0]].neighbors +=[vertices[edge[1]]]
vertices[edge[1]].neighbors +=[vertices[edge[0]]]
return vertices
def print_graph(vertices):
for n in vertices:
print(str(n.data), end=": {")
for t in n.neighbors:
print(str(t.data), end=" ")
print()
def print_graph_rec(root, visited_nodes):
if root==None or root in visited_nodes:
return
visited_nodes.add(root)
print(str(root.data), end=": {")
for n in root.neighbors:
print(str(n.data), end=" ")
print("}")
for n in root.neighbors:
print_graph_rec(n, visited_nodes)
def print_graph(root):
visited_nodes=set()
print_graph_rec(root, visited_nodes)
def main():
vertices=create_test_graph_undirected(7, 18)
print_graph(vertices[0])
cp=clone(vertices[0])
print()
print("After copy.")
print_graph(cp)
main()
运行时复杂度：线性O（n）
内存复杂度：对数，O（logn）
我们使用深度优先遍历，并在遍历图形时创建每个节点的副本。 为了避免陷入周期，我们将使用哈希表存储每个完成的节点，并且不会重新访问哈希表中存在的节点。
哈希表键将是原始图中的一个节点，其值将是克隆图中的相应节点。
设计：序列化/反序列化二叉树
将二叉树序列化为文件，然后将其反序列化为树，以使原始树和反序列化的树相同。
· 序列化：将树写入文件中。
· 反序列化：从文件读取并在内存中重建树。
序列化流的格式没有限制，因此可以以任何有效的格式对其进行序列化。 但是，从流中反序列化树之后，它应该与原始树完全相同。 将下面的树视为输入树。
MARKER=sys.maxsize
def serialize(node, stream):
if node==None:
stream.dump(MARKER);
return
stream.dump(node.data);
serialize(node.left, stream)
serialize(node.right, stream)
def deserialize(stream):
try:
data=pickle.load(stream)
if data==MARKER:
return None
node=BinaryTreeNode(data);
node.left=deserialize(stream)
node.right=deserialize(stream)
return node
except pickle.UnpicklingError:
return None
root=create_random_BST(15)
display_level_order(root)
output=open('data.class', 'wb')
p=pickle.Pickler(output)
serialize(root, p)
output.close()
input2=open('data.class','rb')
root_deserialized=deserialize(input2)
display_level_order(root_deserialized)
assert is_identical_tree(root, root_deserialized), "Trees should be identical"
运行时复杂度：线性O（n）
内存复杂度：对数，O（logn）O
可以有多种方法来序列化和反序列化树。 一种方法是执行深度优先遍历并将单个节点序列化到流。 我们将在此处使用预订遍历。 我们还将序列化一些标记以表示空指针，以帮助反序列化树。
以下面的二叉树为例。 标记（M *）已添加到该树中以表示空节点。 每个标记的数字，即M1中的1，M2中的2，仅代表标记在流中的相对位置。
上面示例中的序列化树（预遍历）看起来像下面的列表。
反序列化树时，我们将再次使用预遍历，并为每个非标记节点创建一个新节点。 遇到标记表明它是一个空节点。
排序和搜索：查找高低索引
给定一个整数排序数组，返回给定键的低和高索引。 如果找不到索引，则必须返回-1。
数组长度可以是数百万，其中有很多重复项。
在以下示例中，根据键，低索引和高索引将为：
· 键：1，低=0，高=0
· 键：2，低=1，高=1
· 键：5，低=2，高=9
· 键：20，低=10，高=10
为了测试您的代码，输入数组将为：
1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6
现在使用Python 3解决方案。
def find_low_index(arr, key):
low = 0
high = len(arr) - 1
mid = int(high / 2)
while low <= high:
mid_elem = arr[mid]
if mid_elem < key:
low = mid + 1
else:
high = mid - 1
mid = low + int((high - low) / 2)
if low < len(arr) and arr[low] == key:
return low
return -1
def find_high_index(arr, key):
low = 0
high = len(arr) - 1
mid = int(high / 2)
while low <= high:
mid_elem = arr[mid]
if mid_elem <= key:
low = mid + 1
else:
high = mid - 1
mid = low + int((high - low) / 2);
if high == -1:
return high
if high < len(arr) and arr[high] == key:
return high
return -1
array = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6]
key = 5
low = find_low_index(array, key)
high = find_high_index(array, key)
print("Low Index of " + str(key) + ": " + str(low))
print("High Index of " + str(key) + ": " + str(high))
key=-2
low=find_low_index(array, key)
high=find_high_index(array, key)
print("Low Index of " + str(key) + ": " + str(low))
print("High Index of " + str(key) + ": " + str(high))
运行时复杂度：对数O（logn）
内存复杂度：常数，O（1）
线性扫描排序后的数组以获取低索引和高索引是非常低效的，因为我们的数组大小可能达到数百万。 取而代之的是，我们将使用经过稍微修改的二进制搜索来查找给定键的低和高索引。 我们需要进行两次二进制搜索：
· 一次用于查找低索引。
· 一次用于查找高索引。
低指数
让我们看一下查找低索引的算法：
· 在每个步骤中，请考虑低索引和高索引之间的数组，并计算中索引。
· 如果中间索引处的元素小于关键点，则低点变为中间+ 1（朝范围的起点移动）。
· 如果位于中间的元素大于或等于键，则高变为-1。位于低的索引保持不变。
· 当低大于高时，低将指向该键的首次出现。
· 如果低位元素与键不匹配，则返回-1。
高指数
同样，我们可以通过稍微修改上述条件来找到较高的索引：
· 当位于中间索引处的元素小于或等于键时，将低索引移至中间+1。
· 当位于中间的元素大于关键点时，将高索引切换到中间-1。
排序和搜索：搜索旋转数组
在具有唯一元素的已排序数组中搜索已旋转任意数字的给定数字。 如果该数字不存在，则返回-1。
假定数组不包含重复项
任务是在此数组中找到给定的数字。
def binary_search(arr, start, end, key):
# assuming all the keys are unique.
if (start > end):
return -1;
mid=int(start + (end - start) / 2)
if arr[mid]==key:
return mid
if arr[start] <=arr[mid] and key <=arr[mid] and key >=arr[start]:
return binary_search(arr, start, mid - 1, key)
elif arr[mid] <=arr[end] and key >=arr[mid] and key <=arr[end]:
return binary_search(arr, mid + 1, end, key)
elif arr[end] <=arr[mid]:
return binary_search(arr, mid + 1, end, key)
elif arr[start] >=arr[mid]:
return binary_search(arr, start, mid - 1, key)
return -1;
def binary_search_rotated(arr, key):
return binary_search(arr, 0, len(arr)-1, key)
v1=[6, 7, 1, 2, 3, 4, 5];
print("Key(3) found at: " + str(binary_search_rotated(v1, 3)))
print("Key(6) found at: " + str(binary_search_rotated(v1, 6)))
v2=[4, 5, 6, 1, 2, 3];
print("Key(3) found at: " + str(binary_search_rotated(v2, 3)))
print("Key(6) found at: " + str(binary_search_rotated(v2, 6)))
运行时复杂度：对数O（logn）
内存复杂度：对数，O（logn）
该解决方案本质上是二进制搜索，但有一些修改。 如果我们仔细查看示例中的数组，则会注意到该数组的至少一半始终被排序。 我们可以利用此属性来获得优势。
如果数字n位于数组的排序一半内，那么我们的问题是基本的二进制搜索。 否则，丢弃分类的一半并继续检查未分类的一半。 由于我们在每一步都将数组分成两半，因此给我们带来了O（logn）运行时复杂性。
25个更常见的Facebook编码面试问题
· 整数数组（动态编程数组）中最长的递增子序列
· 网格中的唯一路径（动态编程矩阵）
· 将两个数字相加成一个列表（列表）
· 设计缓存（系统设计）
· 设计高度一致的数据库（系统设计）
· 旋转矩阵（数组）
· 设计URL缩短器（系统设计）
· 设计推荐系统（ML，系统设计）
· 求第n个斐波那契数（数论）
· 使用二进制搜索找到整数的平方根（数学搜索答案）
· 实现StrStr（字符串搜索）
· 回文的最少附加内容（字符串）
· 在直方图中找到最大的矩形（堆栈）
· 子字符串串联（增量哈希）
· 查找最不常见的祖先（树搜索）
· 查找树中节点之间的最大距离（DFS）
· 在一个数组中查找所有唯一的三元组，给出零和（数组）
· 在非空二叉树（二叉树）中找到最大路径总和
· 查找最接近原点的K个点，以获取平面上的点列表（搜索/排序）
· 编写函数以计算数组的交集（排序/搜索）
· 设计提前输入功能（系统设计）
· 设计Facebook Messenger（系统设计）
· 将字串以字符串数组（数组/字符串）分组
· 将BST转换为排序的圆形双向链表（树）
· 确定字典中字母的顺序（图形/树）
如何准备面试
现在，您已经对采访期望了些什么，并知道了什么样的问题，让我们基于Facebook独特的采访过程来学习一些准备策略。
准备你的简历。
您应该做的第一件事是将简历更新为指标/可交付成果驱动的。 展示您所做的工作如何转化为五个核心价值也是一个好主意：快速行动，勇于创新，专注于影响力，开放并建立社会价值。
练习通才编码问题
我建议至少三个月的自学才能成功。 这包括选择编程语言，复习基础知识以及研究算法，数据结构，系统设计，面向对象的编程等等。
这里的窍门不仅仅是学习死记硬背。 最好的练习方法是学习编码问题的常用模式。 专家们确定了16种常见的编码问题模式。
使用不同的工具练习编码也很重要：
· 简单文本编辑器（如CoderPad）
· 手动（在白板或纸上）
· 您首选的编码风格
准备系统设计面试
设计面试通常不需要任何编码，因此您需要学习如何回答这些问题。 这将在面试期间在白板上完成，因此请手动练习设计。 研究系统设计和产品设计。
掌握系统设计问题的最好方法不是记住答案，而是学习系统设计问题的结构。 您需要训练自己从头开始思考，同时还要考虑规模和要求。
专业提示：如果您想在系统设计访谈中脱颖而出，则需要讨论如何在设计中实施机器学习。
Facebook需要下一代工程师，他们将重点放在人工智能上。 考虑重新学习ML概念和ML系统设计原理。
掌握最佳做法
一旦掌握了基础知识并通过了面试准备路线图，就可以掌握最佳实践。
练习时，学习如何清晰地表达自己的过程。 Facebook非常在乎您的想法。 编写代码时，请像其他人在会议室一样解释您的思考过程。
您还希望开始计时，以学习如何有效地管理时间。 花时间计划您的答案总是比仅仅用蛮力跳出来更好。
准备行为面试
Facebook关心您是否适合他们的公司，因此您需要准备谈论自己。 对于Facebook的每个价值观，集思广益，了解自己的适应方式以及这些价值观对您的重要性。
您还应该考虑作为工程师的2至4年的职业抱负，兴趣和优势，因为它们可能会在面试中出现。
为面试官准备问题
Facebook重视自我进取，因此请务必准备好面试官的问题。 在每次面试期间，您将有时间问自己的问题。 这也是确定Facebook是否适合您的生活方式和需求的机会。
总结
恭喜！ 您现在距离在Facebook上找到该职位更近了一步。 破解Facebook编码面试取决于您准备花费的时间，例如练习编码问题，研究行为面试以及了解Facebook的公司文化。
没有金牌，但是更多的准备肯定会让您成为一个更自信和更理想的候选人。 有策略地练习。 经常练习。
继续学习！
升级编码
感谢您加入我们的社区！ 订阅我们的YouTube频道或参加Skilled.dev编码面试课程。
编码面试题 Skilled.dev掌握编码面试的课程