看看最重要的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的元素向左移動，同時保持數組中其他元素的順序。 數組必須就地修改。
<code>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)/<code>運行時複雜度：線性，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）。
<code>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 =" ")/<code>運行時複雜度：線性，O（n）
內存複雜度：線性，O（n）
這個問題可以通過簡單的線性掃描算法解決。 我們知道輸入是根據開始時間戳排序的。 這是我們遵循的方法：
· 給出了輸入間隔的列表，我們將合併的間隔保留在輸出列表中。
· 對於輸入列表中的每個間隔：
· 如果輸入間隔與輸出列表中的最後一個間隔重疊，則我們將合併這兩個間隔，並使用合併的間隔更新輸出列表中的最後一個間隔。
· 否則，我們會將輸入間隔添加到輸出列表中。
樹：將二叉樹轉換為雙向鏈表
將二叉樹轉換為雙向鏈表，以便雙向鏈表的順序與按順序遍歷二叉樹的順序相同。
轉換後，該節點的左指針應指向雙向鏈接列表中的前一個節點，而右指針應指向雙向鏈接列表中的下一個節點。 在查看解決方案和解釋之前，請先嚐試一下。
<code># 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()/<code>運行時複雜度：線性，O（n）
內存複雜度：線性，O（h）
遞歸解決方案具有O（h）內存複雜性，因為它將消耗堆棧上的內存，直到二叉樹h的高度。 對於平衡樹，它將為O（log n），在最壞的情況下可以為O（n）。
在有序遍歷中，首先遍歷左側的子樹，然後訪問根，最後遍歷右側的子樹。
解決此問題的一種簡單方法是從一個空的雙向鏈表開始。 在對二叉樹進行有序遍歷時，請始終將每個元素輸出插入到雙向鏈表中。
但是，如果我們仔細地看問題，訪問者希望我們將二叉樹就地轉換為雙向鏈表，即我們不應該為雙向鏈表創建新節點。
可以使用分而治之的方法遞歸解決此問題。 下面是指定的算法。
· 從根節點開始，遞歸求解左右子樹
· 在每個步驟中，一旦左右子樹已處理完畢：
· 將左子樹的輸出與根融合，以得到中間結果
· 將中間結果（在上一步中構建的結果）與右側子樹的輸出融合在一起，以得出當前遞歸調用的最終結果。
樹：二叉樹的層級順序遍歷
給定二叉樹的根，顯示每個級別的節點值。 所有級別的節點值應在單獨的行上顯示。 讓我們看一下下面的二叉樹。
該樹的級別順序遍歷應如下所示：
· 100
· 50、200
· 25、75、350
<code># 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("\nLevel Order Traversal:\n", end = "")
level_order_traversal_1(root)/<code>運行時複雜度：線性，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"字符串為例：
<code>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)/<code>解決方案的工作原理如下：
· 反轉字符串。
· 遍歷字符串並將每個單詞反向。
字符串：字符串分段
您會得到一個單詞詞典和一個大輸入字符串。 您必須找出輸入字符串是否可以完全分割成給定字典的單詞。 以下示例進一步闡述了該問題。
<code>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")/<code>運行時複雜度：如果僅使用遞歸，則指數為O（2 ^ n）。 藉助備忘錄，可以將該解決方案的運行時複雜度提高為多項式O（n²）。
內存複雜度：多項式，O（n²）
您可以通過在每個可能的位置處分割大字符串來查看字符串是否可以完全分割為字典中的單詞，從而解決此問題。 如果分步編寫算法，則將如下所示：
<code>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/<code>該算法將在循環的每次迭代中從頭計算兩個字符串。 最壞的情況是每次都會遞歸調用second_word。 這將時間複雜度提高到2 ^ n。
您會發現您可能多次計算相同的子字符串，即使字典中不存在該子字符串也是如此。 可以通過備註來修復此冗餘，您可以在其中記住已經解決了哪些子字符串。
為了實現記憶，您可以每次將第二個字符串存儲在一個新集中。 這將減少時間和內存複雜度。
動態編程：查找最大單筆賣出利潤
給定每日股票價格列表（為簡單起見，以整數表示），請返回買入和賣出價格以獲取最大利潤。
我們需要最大化單次買賣利潤。 如果我們無法獲得任何利潤，我們將盡量減少損失。 在下面的示例中，突出顯示了（最大）獲利的買入（橙色）和賣出（綠色）價格。
<code>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]))/<code>運行時複雜度：線性，O（n）
內存複雜度：常數，O（1）
數組中的值代表每天的庫存成本。 由於我們只能買賣一次股票，因此我們需要找到在給定的時間段內利潤最大化（或虧損最小化）的最佳買賣價格。
一個運行時間複雜度為O（n²）的簡單的解決方案是在每個元素及其後續元素之間找到最大增益。
有一個棘手的線性解決方案，需要迭代遍歷整個股票價格時，保持current_buy_price（這是迄今為止看到的最小數量），current_profit和global_profit。
在每次迭代中，我們都將current_profit與global_profit進行比較，並相應地更新global_profit。
基本算法如下：
<code>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/<code>數學和統計：計算數字的冪
給定一個雙精度數x和一個整數n，編寫一個函數計算x的冪次。 例如：
功率（2，5）= 32
功率（3，4）= 81
功效（1.5，3）= 3.375
功效（2，-2）= 0.25
<code>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))/<code>運行時複雜度：對數，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是子問題的結果）。
回溯：查找所有可能的子集
我們得到了一組整數，我們必須找到該整數組的所有可能子集。
<code>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()/<code>運行時複雜度：指數，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'。
注意：我們假設所有頂點都可以從根頂點到達。 即我們有一個連通圖。
<code>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()/<code>運行時複雜度：線性O（n）
內存複雜度：對數，O（logn）
我們使用深度優先遍歷，並在遍歷圖形時創建每個節點的副本。 為了避免陷入週期，我們將使用哈希表存儲每個完成的節點，並且不會重新訪問哈希表中存在的節點。
哈希表鍵將是原始圖中的一個節點，其值將是克隆圖中的相應節點。
設計：序列化/反序列化二叉樹
將二叉樹序列化為文件，然後將其反序列化為樹，以使原始樹和反序列化的樹相同。
· 序列化：將樹寫入文件中。
· 反序列化：從文件讀取並在內存中重建樹。
序列化流的格式沒有限制，因此可以以任何有效的格式對其進行序列化。 但是，從流中反序列化樹之後，它應該與原始樹完全相同。 將下面的樹視為輸入樹。
<code>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"/<code>運行時複雜度：線性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解決方案。
<code>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))/<code>運行時複雜度：對數O（logn）
內存複雜度：常數，O（1）
線性掃描排序後的數組以獲取低索引和高索引是非常低效的，因為我們的數組大小可能達到數百萬。 取而代之的是，我們將使用經過稍微修改的二進制搜索來查找給定鍵的低和高索引。 我們需要進行兩次二進制搜索：
· 一次用於查找低索引。
· 一次用於查找高索引。
低指數
讓我們看一下查找低索引的算法：
· 在每個步驟中，請考慮低索引和高索引之間的數組，並計算中索引。
· 如果中間索引處的元素小於關鍵點，則低點變為中間+ 1（朝範圍的起點移動）。
· 如果位於中間的元素大於或等於鍵，則高變為-1。位於低的索引保持不變。
· 當低大於高時，低將指向該鍵的首次出現。
· 如果低位元素與鍵不匹配，則返回-1。
高指數
同樣，我們可以通過稍微修改上述條件來找到較高的索引：
· 當位於中間索引處的元素小於或等於鍵時，將低索引移至中間+1。
· 當位於中間的元素大於關鍵點時，將高索引切換到中間-1。
排序和搜索：搜索旋轉數組
在具有唯一元素的已排序數組中搜索已旋轉任意數字的給定數字。 如果該數字不存在，則返回-1。
假定數組不包含重複項
任務是在此數組中找到給定的數字。
<code>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)))/<code>運行時複雜度：對數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
掌握編碼面試的課程
(本文翻譯自The Educative Team的文章《Cracking the top 40 Facebook coding interview questions》，參考：https://levelup.gitconnected.com/cracking-the-top-40-facebook-coding-interview-questions-185bab32489f)
