Cracking the top 40 Facebook coding interview questions

This article was written by Amanda Fawcett and was originally published at Educative, Inc.

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 growth-based 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 step-by-step 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

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.

• 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 pre-screen interview (20 minutes), 1 technical phone interview (50 minutes, 1–2 coding questions), and 4–5 on-site interviews (45 minutes each).
• On-site interviews: Facebook breaks the on-site 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 entry-level 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 though, 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.

As you can see to the left, Facebook focuses mostly on arrays and strings. These are essential skills to master. Each question will be solved in Python 3. To see these solutions in C++, Ruby, Java, and JavaScript, visit here.

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 in-place.

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)O(n)

Memory Complexity: Constant, O(1)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 to 0, skip.
• If read_index points to a non-zero value, write the value at read_index to write_index and decrement write_index.
• Assign zeros to all the values before the write_index and to the current position of write_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 in-order 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)

Recursive solution has O(h) memory complexity as it will consume memory on the stack up to the height of binary tree h. It will be O(log n) for balanced trees and in the worst case can be O(n).

In an in-order traversal, first the left sub-tree is traversed, then the root is visited, and finally the right sub-tree is traversed.

One simple way of solving this problem is to start with an empty doubly linked list. While doing the in-order 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 in-place 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

Write a new post

PersonalEducative

EditPreview

# 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 above-mentioned 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 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)

Here is how the solution works:

• Reverse the string.
• Traverse the string and reverse each word in place.

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. With memoization, the runtime complexity of this solution can be improved to be polynomial, O(n²).

Memory Complexity: Polynomial, O(n²)

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²), 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 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 sub-problem and compute the result of the current problem using the two rules below: If n is even, the result is r *r*r (where r is the result of sub-problem) If n is odd, the result is x*r*r (where r is the result of sub-problem).

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 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()

Runtime complexity: Linear O(n)

Memory Complexity: Logarithmic, O(logn)

We use depth-first 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(logn)O

There can be multiple approaches to serialize and deserialize the tree. One approach is to perform a depth-first traversal and serialize individual nodes to the stream. We’ll use a pre-order 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.

The serialized tree (pre-order traversal) from the above example would look like the below list.

When deserializing the tree we’ll again use the pre-order traversal and create a new node for every non-marker 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 and high = 0
• key: 2, low = 1 and high = 1
• key: 5, low = 2 and high = 9
• key: 20, low = 10 and high = 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 in 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))

Runtime complexity: Logarithmic O(logn)

Memory Complexity: Constant, O(1)

Linearly scanning the sorted array for low and high 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 and high 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 and high indices and calculate the mid index.
• If the element at mid index is less than the key, low becomes mid + 1 (to move towards the start of range).
• If the element at mid is greater or equal to the key, the high becomes mid - 1. Index at low remains the same.
• When low is greater than high, low would be pointing to the first occurrence of the key.
• If the element at low does not match the key, return -1.

High index

Similarly, we can find the high index by slightly modifying the above condition:

• Switch the low index to mid + 1 when the element at mid index is less than or equal to the key.
• Switch the high index to mid - 1 when the element at mid is greater than the key.

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(logn)

Memory Complexity: Logarithmic, O(logn)

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(logn) runtime complexity.

25 more common Facebook coding interview questions

1. Longest increasing subsequence from array of integers (dynamic programming arrays)
2. Unique paths in a grid (dynamic programming matrices)
3. Add two numbers as a list (lists)
4. Design cache (system design)
5. Design a highly consistent database (system design)
6. Rotate a matrix (arrays)
7. Design a URL shortener (system design)
8. Design a recommendation system (ML, system design)
9. Find nth Fibonacci number (number theory)
10. Find the square root of an integer using binary search (math search answer)
11. Implement StrStr (string search)
12. Minimum appends for Palindrome (strings)
13. Find the largest rectangle in a histogram (stacks)
14. Substring concatenation (incremental hash)
15. Find the least common ancestor (tree search)
16. Find largest distance between nodes in a tree (DFS)
17. Find all unique triplets in an array, giving sum of zero (array)
18. Find maximum path sum in non-empty binary tree (binary tree)
19. Find K closest points to origin for a list of points on a plane (search/sort)
20. Write a function to compute intersection of arrays (sort/search)
21. Design a typehead feature (system design)
22. Design Facebook Messenger (system design)
23. Group anagrams together in an array of strings (arrays/strings)
24. Convert a BST to sorted circular doubly linked list (trees)
25. 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 self-study to be successful. This includes choosing a programming language, reviewing the basics, and studying algorithms, data structures, system design, object-oriented programming, and more.

The trick here is not just to learn rote memorization. The best way to practice is by learning the common patterns for coding questions. Experts have identified 16 common coding question patterns.

It’s also important to practice coding using different tools:

• Simple Text Editor (like CoderPad)
• By hand (on a whiteboard or paper)
• Your preferred style of coding

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 next-gen 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.

Prepare questions for your interviewers

Facebook values self-starters, 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.

Wrapping up

Congrats! You’re now one step closer to landing that job at Facebook. 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. Practice strategically. Practice often.

Keep learning and studying!