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.
My Facebook Interview Experience (software engineer interview)
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.
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.
In the following example, according to the the key, the low and high indices would be:
key: 1, low = 0 and high = 0key: 2, low = 1 and high = 1key: 5, low = 2 and high = 9key: 20, low = 10 and high = 10For the testing of your code, the input array will be:
Runtime complexity: Logarithmic O(logn)O(log n)O(logn)
Memory Complexity: Constant, O(1)O(1)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:
low index.high index.Let’s look at the algorithm for finding the low index:
low and high indices and calculate the mid index.mid index is less than the key, low becomes mid + 1 (to move towards the start of range).key, the high becomes mid - 1. Index at low remains the same.low is greater than high, low would be pointing to the first occurrence of the key.low does not match the key, return -1.Similarly, we can find the high index by slightly modifying the above condition:
low index to mid + 1 when the element at mid index is less than or equal to the key.high index to mid - 1 when the element at mid is greater than the key.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.
Runtime complexity: Exponential, O(2n)O(2^{n})O(2n), if we only use recursion. With memoization, the runtime complexity of this solution can be improved to be polynomial, O(n2)O(n^{2})O(n2).
Memory Complexity: Polynomial, O(n2)O(n^{2})O(n2)
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:
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 2n2^{n}2n.
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.
FAQ
What questions does Facebook ask in an interview?
- How highly do you rate teamwork on a scale of 1 to 10, with 1 being the highest and 10 being the lowest?
- Do you prefer to work independently?
- Have you ever been in a challenging team situation? …
- How did you motivate your team?
How do I pass a Facebook interview?
- 3.1 Deep dive into the product / organization. …
- 3.2 Brush up on product fundamentals. …
- 3.3 Learn a consistent method for answering PM interview questions. …
- 3.4 Practice by yourself or with peers.
Are Facebook interview questions hard?
How many interview rounds does Facebook have?
