Landing a job at Facebook is a dream for many developers around the globe. Facebook is one of the top tech companies in the world, with a workforce of over 52,000 strong. Facebook is known for its growthbased company culture, fast promotion tracks, excellent benefits, and top salaries that few companies can match.
But competition is fierce, and with a swell of new hires, Facebook is on the lookout for the top candidates. Facebook focuses on your cultural fit, generalist knowledge, ability to build within constraints, and expert coding skills.
To help you prepare, today I will walk through everything you need to crack an Facebook interview, including coding questions and a stepbystep preparation guide.
Today we will go over:
 Overview of the Facebook coding interview
 Top 40 Facebook coding interview questions
 How to prepare for a Facebook interview
 Wrapping up and resource list
Succeed in your Facebook interview.
Strategically prepare for Facebook interviews by learning the patterns behind common questions
Grokking the Coding Interview: Patterns for Coding Questions
Overview of the Facebook coding interview
To land a software engineering job at Facebook, you need to know what lies ahead. The more prepared you are, the more confident you will be. So, let’s break it down. For a deeper dive into Facebook’s interview process, check out Coding Interviews’s free Facebook Coding Interview Guide.
 Interview Timeline: From resume submission to job offer, the process lasts 1.5 to 2 months.
 Types of Interviews: The interview process consists of 6 to 7 interviews. This includes 1 prescreen interview (20 minutes), 1 technical phone interview (50 minutes, 12 coding questions), and 45 onsite interviews (45 minutes each).
 Onsite interviews: Facebook breaks the onsite interviews into three sections. The Ninja portion consists of 2 coding interviews using a whiteboard. The Pirate portion includes 2 system design interviews. The Jedi portion includes 1 cultural/behavioral interview.
 Coding Questions: Facebook interview questions focus on generalist knowledge on algorithms, data structures, and time complexity. They also test on architecture and system design (even entry level).
 Hiring Levels: Facebook normally hires at level E3 for entry level software roles with E9 behind the height of levels. E5 is considered an entrylevel manager role.
 Hiring Teams: Central hires for Oculus, Facebook Groups, and WhatsApp.
 Programming languages: Facebook prefers most standard languages, including Java, C++, Python, Ruby, and Perl.
What’s different about Facebook interviews?
System design interview:
 At Facebook, you can expect these questions no matter what level you are interviewing for.
Structured interviewing:
 Facebook will pair you with interviewers who have either held the position you’re interviewing for or with individuals who work directly with the position you’re interviewing for.
Core values and your behavioral interview:
 Facebook interviewers will also evaluate your ability to embody their five core values: Move Fast, Be Bold, Focus on Impact, Be Open, and Build Social Value.
Top 40 Facebook coding interview questions
In this section, we’ll take a deep dive into the top 40 coding interview questions. We will discuss the answers and runtime complexities for the 15 questions you’re bound to see in an interview followed by the definitive list of 25 questions you’ll likely encounter.
Each question will be solved in Python 3. To see these solutions in C++, Ruby, Java, and JavaScript, visit here.
If you want to solve the questions yourself, please see my original posting of this article, which features an interactive code widget.
Arrays: move zeros to the left
Given an integer array, move all elements that are 0 to the left while maintaining the order of other elements in the array. The array has to be modified inplace.
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)
Runtime complexity: Linear, O(n)
Memory Complexity: Constant, O(1)
Keep two markers: read_index
and write_index
and point them to the end of the array. Let’s take a look at an overview of the algorithm.
While moving read_index
towards the start of the array:
 If
read_index
points to0
, skip.  If
read_index
points to a nonzero value, write the value atread_index
towrite_index
and decrementwrite_index
.  Assign zeros to all the values before the
write_index
and to the current position ofwrite_index
as well.
Arrays: Merge overlapping intervals
You are given an array (list) of interval pairs as input where each interval has a start and end timestamp. The input array is sorted by starting timestamps. You are required to merge overlapping intervals and return a new output array.
Consider the input array below. Intervals (1, 5), (3, 7), (4, 6), (6, 8) are overlapping so they should be merged to one big interval (1, 8). Similarly, intervals (10, 12) and (12, 15) are also overlapping and should be merged to (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 =" ")
Runtime complexity: Linear, O(n)
Memory Complexity: Linear, O(n)
This problem can be solved in a simple linear scan algorithm. We know that input is sorted by starting timestamps. Here is the approach we are following:
 List of input intervals is given, and we’ll keep merged intervals in the output list.
 For each interval in the input list:
 If the input interval is overlapping with the last interval in the output list then we’ll merge these two intervals and update the last interval of the output list with the merged interval.
 Otherwise, we’ll add an input interval to the output list.
Trees: Convert binary tree to doubly linked list
Convert a binary tree to a doubly linked list so that the order of the doubly linked list is the same as an inorder traversal of the binary tree.
After conversion, the left pointer of the node should be pointing to the previous node in the doubly linked list, and the right pointer should be pointing to the next node in the doubly linked list. Try it yourself before reviewing the solution and explanation.
# 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()
Runtime complexity: Linear, O(n)
Memory Complexity: Linear, O(h).
In an inorder traversal, first the left subtree is traversed, then the root is visited, and finally the right subtree is traversed.
One simple way of solving this problem is to start with an empty doubly linked list. While doing the inorder traversal of the binary tree, keep inserting each element output into the doubly linked list.
But, if we look at the question carefully, the interviewer wants us to convert the binary tree to a doubly linked list inplace i.e. we should not create new nodes for the doubly linked list.
This problem can be solved recursively using a divide and conquer approach. Below is the algorithm specified.
 Start with the root node and solve left and right subtrees recursively
 At each step, once left and right subtrees have been processed:
 Fuse output of left subtree with root to make the intermediate result
 Fuse intermediate result (built in the previous step) with output from the right subtree to make the final result of the current recursive call.
Trees: Level order traversal of binary tree
Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree.
Level order traversal for this tree should look like:
 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("\nLevel Order Traversal:\n", end = "")
level_order_traversal_1(root)
Runtime complexity: Linear, O(n)
Memory Complexity: Linear, O(n)
Here, you are using two queues:current_queue
and next_queue
. You push the nodes in both queues alternately based on the current level number.
You’ll dequeue nodes from the current_queue
, print the node’s data, and enqueue the node’s children to the next_queue
.
Once the current_queue
becomes empty, you have processed all nodes for the current level_number
. To indicate the new level, print a line break (\n
), swap the two queues, and continue with the abovementioned logic.
After printing the leaf nodes from the current_queue
, swap current_queue
and next_queue
. Since the current_queue
would be empty, you can terminate the loop.
Strings: Reverse words in a sentence
Reverse the order of words in a given sentence (an array of characters). Take the “Hello World” string for example:
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 nullterminated 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 inplace.
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)
Here is how the solution works:
 Reverse the string.
 Traverse the string and reverse each word in place.
For more on string reversal, read my article Best practices for reversing a string in JavaScript, C++, and Python.
Strings: String segmentation
You are given a dictionary of words and a large input string. You have to find out whether the input string can be completely segmented into the words of a given dictionary. The following example elaborates on the problem further.
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")
Runtime complexity: Exponential, O(2^n), if we only use recursion.
Memory Complexity: Polynomial, O(n^2)
You can solve this problem by segmenting the large string at each possible position to see if the string can be completely segmented to words in the dictionary. If you write the algorithm in steps it will be as follows:
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
The algorithm will compute two strings from scratch in each iteration of the loop. Worst case scenario, there would be a recursive call of the second_word
each time. This shoots the time complexity up to $2^{n}$.
You can see that you may be computing the same substring multiple times, even if it doesn’t exist in the dictionary. This redundancy can be fixed by memoization, where you remember which substrings have already been solved.
To achieve memoization, you can store the second
string in a new set each time. This will reduce both time and memory complexities.
Dynamic Programming: Find maximum single sell profit
Given a list of daily stock prices (integers for simplicity), return the buy and sell prices for making the maximum profit.
We need to maximize the single buy/sell profit. If we can’t make any profit, we’ll try to minimize the loss. For the below examples, buy (orange) and sell (green) prices for making a maximum profit are highlighted.
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]))
Runtime complexity: Linear, O(n)
Memory Complexity: Constant, O(1)
The values in the array represent the cost of a stock each day. As we can buy
and sell
the stock only once, we need to find the best buy
and sell
prices for which our profit is maximized (or loss is minimized) over a given span of time.
A naive solution, with runtime complexity of $O(n^{2})$, is to find the maximum gain between each element and its succeeding elements.
There is a tricky linear solution to this problem that requires maintaining current_buy_price
(which is the smallest number seen so far), current_profit
, and global_profit
as we iterate through the entire array of stock prices.
At each iteration, we will compare the current_profit
with the global_profit
and update the global_profit
accordingly.
The basic algorithm is as follows:
current profit = INT_MIN
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
Math and Stats: Calculate the power of a number
Given a double, x
, and an integer, n
, write a function to calculate x
raised to the power n
. For example:
power (2, 5) = 32
power (3, 4) = 81
power (1.5, 3) = 3.375
power (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))
Runtime complexity: Logarithmic, O(log n)
Memory Complexity: Logarithmic, O(log n)
A simple algorithm for this problem is to multiply x
by n
times. The time complexity of this algorithm would be O(n). We can use the divide and conquer approach to solve this problem more efficiently.
In the dividing step, we keep dividing n
by 2
recursively until we reach the base case i.e. n == 1
In the combining step, we get the result, r
, of the subproblem and compute the result of the current problem using the two rules below:
 If n is even, the result is r * r (where r is the result of subproblem)
 If n is odd, the result is x * r * r (where r is the result of subproblem).
Backtracking: Find all possible subsets
We are given a set of integers and we have to find all the possible subsets of this set of integers.
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()
Runtime complexity: Exponential, O(2^n * n), where $n$ is the number of integers in the given set
Memory Complexity: Constant, O(2^n * n)
There are several ways to solve this problem. We will discuss the one that is neat and easier to understand. We know that for a set of ‘n’ elements there are 2^n subsets. For example, a set with 3 elements will have 8 subsets. Here is the algorithm we will use:
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
Note that the ordering of bits for picking integers from the set does not matter; picking integers from left to right would produce the same output as picking integers from right to left.
Graphs: Clone a directed graph
Given the root node of a directed graph, clone this graph by creating its deep copy so that the cloned graph has the same vertices and edges as the original graph.
Let’s look at the below graphs as an example. If the input graph is G = (V, E) where V is set of vertices and E is set of edges, then the output graph (cloned graph) G’ = (V’, E’) such that V = V’ and E = E’.
Note: We are assuming that all vertices are reachable from the root vertex. i.e. we have a connected graph.
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 undirected 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()
Runtime complexity: Linear O(n)
Memory Complexity: Logarithmic, O(log n)
We use depthfirst traversal and create a copy of each node while traversing the graph. To avoid getting stuck in cycles, we’ll use a hashtable to store each completed node and will not revisit nodes that exist in the hashtable.
The hashtable key will be a node in the original graph, and its value will be the corresponding node in the cloned graph.
Design: Serialize / deserialize binary tree
Serialize a binary tree to a file and then deserialize it back to a tree so that the original and the deserialized trees are identical.
 Serialize: write the tree in a file.
 Deserialize: read from a file and reconstruct the tree in memory.
There is no restriction regarding the format of a serialized stream, therefore you can serialize it in any efficient format. However, after deserializing the tree from the stream, it should be exactly like the original tree. Consider the below tree as the input tree.
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"
Runtime complexity: Linear O(n)
Memory Complexity: Logarithmic, O(log n)
There can be multiple approaches to serialize and deserialize the tree. One approach is to perform a depthfirst traversal and serialize individual nodes to the stream. We’ll use a preorder traversal here. We’ll also serialize some markers to represent a null pointer to help deserialize the tree.
Consider the below binary tree as an example. Markers (M*) have been added in this tree to represent null nodes. The number with each marker i.e. 1 in M1, 2 in M2, merely represents the relative position of a marker in the stream.
When deserializing the tree we’ll again use the preorder traversal and create a new node for every nonmarker node. Encountering a marker indicates that it was a null node.
Sorting and Searching: Find the high and low index
Given a sorted array of integers, return the low and high index of the given key. You must return 1 if the indexes are not found.
The array length can be in the millions with many duplicates.
In the following example, according to the the key
, the low
and high
indices would be:

key
: 1,low
= 0 andhigh
= 0 
key
: 2,low
= 1 andhigh
= 1 
key
: 5,low
= 2 andhigh
= 9 
key
: 20,low
= 10 andhigh
= 10
For the testing of your code, the input array will be:
1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6
Now for the solution.
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))
Runtime complexity: Logarithmic O(log n)
Memory Complexity: Constant, O(1)
Linearly scanning the sorted array for low
andhigh
indices are highly inefficient since our array size can be in millions. Instead, we will use a slightly modified binary search to find the low
andhigh
indices of a given key.
We need to do binary search twice:
 Once for finding the
low
index.  Once for finding the
high
index.
Low index
Let’s look at the algorithm for finding the low
index:
 At every step, consider the array between
low
andhigh
indices and calculate themid
index.  If the element at
mid
index is less than thekey
,low
becomesmid + 1
(to move towards the start of range).  If the element at mid is greater or equal to the
key
, thehigh
becomesmid  1
. Index atlow
remains the same.  When
low
is greater thanhigh
,low
would be pointing to the first occurrence of thekey
.  If the element at
low
does not match thekey
, return1
.
High index
Similarly, we can find the high
index by slightly modifying the above condition:
 Switch the
low
index tomid + 1
when the element atmid
index is less than or equal to thekey
.  Switch the
high
index tomid  1
when the element atmid
is greater than thekey
.
Sorting and Searching: Search rotated array
Search for a given number in a sorted array, with unique elements, that has been rotated by some arbitrary number. Return 1
if the number does not exist.
Assume that the array does not contain duplicates
The task is to find a given number in this array.
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)))
Runtime complexity: Logarithmic, O(log n)
Memory Complexity: Logarithmic, O(log n)
The solution is essentially a binary search but with some modifications. If we look at the array in the example closely, we notice that at least one half of the array is always sorted. We can use this property to our advantage.
If the number n
lies within the sorted half of the array, then our problem is a basic binary search. Otherwise, discard the sorted half and keep examining the unsorted half. Since we are partitioning the array in half at each step, this gives us O(log n) runtime complexity.
25 more common Facebook coding interview questions
 Longest increasing subsequence from array of integers (dynamic programming arrays)
 Unique paths in a grid (dynamic programming matrices)
 Add two numbers as a list (lists)
 Design cache (system design)
 Design a highly consistent database (system design)
 Rotate a matrix (arrays)
 Design a URL shortener (system design)
 Design a recommendation system (ML, system design)
 Find nth Fibonacci number (number theory)
 Find the square root of an integer using binary search (math search answer)
 Implement
StrStr
(string search)  Minimum appends for Palindrome (strings)
 Find the largest rectangle in a histogram (stacks)
 Substring concatenation (incremental hash)
 Find the least common ancestor (tree search)
 Find largest distance between nodes in a tree (DFS)
 Find all unique triplets in an array, giving sum of zero (array)
 Find maximum path sum in nonempty binary tree (binary tree)
 Find K closest points to origin for a list of points on a plane (search/sort)
 Write a function to compute intersection of arrays (sort/search)
 Design a typehead feature (system design)
 Design Facebook Messenger (system design)
 Group anagrams together in an array of strings (arrays/strings)
 Convert a BST to sorted circular doubly linked list (trees)
 Determine the order of letters in a dictionary (graphs/trees)
How to prepare for a Facebook interview
Now that you have a sense of what to expect from an interview and know what kinds of questions to expect, let’s learn some preparation strategies based on Facebook’s unique interview process.
Prepare your resume.
The first thing you should do is update your resume to be metrics/deliverables driven. It’s also a good idea to show how the work you’ve done can translate into their five core values: Move fast, Be bold, Focus on impact, Be open, and Build social value.
Practice generalist coding questions
I recommend at least three months of selfstudy to be successful. This includes choosing a programming language, reviewing the basics, and studying algorithms, data structures, system design, objectoriented programming, and more.
It’s important to practice coding using different tools:
 Simple Text Editor (like CoderPad)
 By hand (on a whiteboard or paper)
 Your preferred style of coding
For a robust, 12week interview guide, check out our article, the 3 Month Coding Interview Preparation Bootcamp
Prepare for the system design interview
The design interview usually doesn’t involve any coding, so you’ll need to learn how to answer these questions. This will be done on a whiteboard during the interview, so practice your designs by hand. Study up on system design and product design.
The best way to master system design questions is not by memorizing answers but by learning the anatomy of a system design question. You need to train yourself to think from the ground up while also considering scaling and requirements.
Pro tip: If you want to stand out in the system design interview, you’ll need to discuss how Machine Learning can be implemented in your design.
Facebook wants nextgen engineers, and they focus heavily on artificial intelligence. Consider brushing up on ML concepts and ML system design principles.
Master the best practices
Once you get the basics down and progress through the interview prep roadmap, master the best practices.
When you practice, learn how to articulate your process out loud. Facebook cares a lot about how you think. When you code, explain your thought process as if another person were in the room.
You also want to start timing yourself to learn how to manage your time effectively. It’s always better to take time planning your answer than to just jump it with brute force.
Prepare for behavioral interviews
Facebook cares that you fit with their company, so you need to be prepared to talk about yourself. For each of Facebook’s values, brainstorm how you fit and why these values matter to you.
You should also think about your 2 to 4 year career aspirations, interests, and strengths as an engineer, as they will likely come up in the interview.
To learn how to prepare, check out my article Behavioral Interviews: how to prepare and ace interview questions
Prepare questions for your interviewers
Facebook values selfstarters, so it’s important that you come prepared with questions for your interviewers. You’ll have time during every interview to ask your own questions. This is also an opportunity to determine if Facebook is a good fit for your lifestyle and needs.
Wrap up and resource list
Cracking the Facebook coding interview comes down to the time you spend preparing, such as practicing coding questions, studying behavioral interviews, and understanding Facebook’s company culture.
There is no golden ticket, but more preparation will surely make you a more confident and desirable candidate. The essential resources below will help you prepare and build confidence for Facebook interviews.
Keep learning and studying!
Essential courses for interview prep
 Grokking the Behavioral Interview
 Grokking the Coding Interview: Patterns for Coding Questions
 Grokking the System Design Interview
 Grokking the Machine Learning System Design Interview
 Mastering Data Structures: An interview refresher
Top comments (2)
Gee 3 months preparation. I have better things to do...
Wow !! Excellent one ;) Thanks for Sharing.