Facebook initial interview prep
Interviews
Coding
Design
Systems design
Product design
Behavioural
Focus
- 5 core values
-
Be bold. Building great things means taking risks. We have a saying: “The riskiest thing is to take no risks.” In a world that’s changing so quickly, you’re guaranteed to fail if you don’t take any risks. We encourage everyone to make bold decisions, even if that means being wrong some of the time.
-
Focus on impact. To have the biggest impact, we need to focus on solving the most important problems. It sounds simple, but most companies do this poorly and waste a lot of time. We expect everyone at Facebook to be good at finding the biggest problems to woKrk on.
-
Move fast. Moving fast enables us to build more things and learn faster. We’re less afraid of making mistakes than we are of losing opportunities by moving too slowly. We are a culture of builders, the power is in your hands.
-
Be open. We believe that a more open world is a better world. The same goes for our company. Informed people make better decisions and have a greater impact, which is why we work hard to make sure everyone at Facebook has access to as much information about the company as possible.
-
Build Social Value. Facebook was created to make the world more open and connected, not just to build a company. We expect everyone at Facebook to focus every day on how to build real value for the world in everything they do.
-
TODO create a process of starting with some text block and then sending it into a program-maker
- I want to be able to do the following:
- Copy the inner text.
- Pipe the inner text into any filter.
|
|
Big-O
Complexity Chart
O |
---|
1 |
log n |
n |
n log n |
n^2 |
2^n |
n! |
Python syntax
|
|
default dictionary
|
|
|
|
Chunky Monkey
Vanilla
Example
|
|
Complexity
Since every node is stepped over, the Time complexity is linear (n). For space complexity, each node value is placed into the list. Therefore, space complexity would be linear (n) also.
When stepping through the algorithm
- Go over the portion of the code that will be measured for big-o
- Log the way the data changes
Some algorithms
$MYGIT/TheAlgorithms/Python
Video
$DUMP$NOTES/ws/facebook/technical-interview/1460597782.mp4
Data structures
- Hash maps,
- linked lists,
- stacks,
- queues,
- trees,
- heaps,
- tries, and
- graphs
leetcode
- Make all examples runnable. Fill out the code
- Step through the leetcode solutions. Make comments on the algorithm No need to memorise code. <v +/"# Get the number of digits" “$MYGIT/seungjaeryanlee/leetcode/solutions/9-2.py”>
Facebook questions
Given an array and an integer z, rotate the array starting from index z to the front
|
|
z=3
|
|
Advanced python syntax
unpacking
|
|
|
|
[2, 3, 4]
more unpacking
|
|
{'a': 1, 'b': 2}
Named slices
|
|
[3, 4, 5]
Deque – double-ended queue
|
|
[5, 2, 1, 3]
Data-structures
Heap
Heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property:
-
In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
-
In a min heap, the key of P is less than or equal to the key of C.
The node at the “top” of the heap (with no parents) is called the root node.
graph TB;
A((100))-->B((19))
A-->C((36))
B-->D((17))
B-->E((3))
C-->F((25))
C-->G((1))
D-->H((2))
D-->I((7))

Glossary
|
|
Complexity
Data structures
- Indexing
- Selecting by index
- Search
- Find value inside data structure
- Insertion
- Insert value into data structure
- Deletion
- Remove value from data structure
Typically, data structures don’t store more than the set of values; it’s the structure of that storage that changes. Therefore, n space complexity.
Data Structure | Time Complexity | - | - | - | - | - | - | - | Space complexity |
---|---|---|---|---|---|---|---|---|---|
Average | Worst | Worst | |||||||
Indexing | Search | Insertion | Deletion | Indexing | Search | Insertion | Deletion | ||
Array | 1 | n | 1 | n | n | ||||
Dynamic Array | 1 | n | n | n | 1 | n | n | n | n |
SLL | n | n | 1 | 1 | n | n | 1 | 1 | n |
DLL | n | n | 1 | 1 | n | n | 1 | 1 | n |
Skip List | log n | log n | log n | log n | n | n | n | n | n log n |
Hash table | 1 | 1 | 1 | n | n | n | n | ||
BST | log n | log n | log n | log n | n | n | n | n | n |
RBT | log n | log n | log n | log n | log n | log n | log n | log n | n |
B-Tree | log n | log n | log n | log n | log n | log n | log n | log n | n |
Searching
Algorithm | Data structure | Time complexity | - | Space complexity |
---|---|---|---|---|
Average | Worst | Worst | ||
Binary search | Sorted array of elements | log n | log n | 1 |
Sorting
- Auxiliary space
- Temporary or extra space used by an algorithm. This temporary space allocated in order to solve the problem. Space complexity is total space taken by the algorithm with respect to the input size.
Algorithm | Data structure | Time complexity | - | - | Auxiliary space complexity |
---|---|---|---|---|---|
Average | Average | Worst | Worst | ||
Quicksort | Sorted array of elements | log n | log n | 1 |
- Pivot
- After sorting, a pivot meets the following 3 conditions:
- Correct position in final, sorted array
- Items to the left are smaller
- Items to the right are larger
- Items to the left are smaller
- Correct position in final, sorted array
|
|
[-31, 0, 1, 2, 4, 65, 83, 99, 782]
Slow quicksort in haskell
- Excerpt from
- Quicksort with Haskell! - Monday Morning Haskell
Learn You a Haskell For Great Good presents a short take on the quicksort algorithm. It demonstrates the elegance with which we can express recursive solutions.
|
|
|
|
This looks very nice!
It captures the general idea of quicksort.
We take the first element as our pivot.
We divide the remaining list into the elements greater than the pivot and less than the pivot.
Then we recursively sort each of these sub- lists, and combine them with the pivot in the middle.
However, each new list we make takes extra memory.
So we are copying part of the list at each recursive step.
This means we will definitely use at least O(n) memory for this algorithm.
We can also note the way this algorithm chooses its pivot.
It always selects the first element.
This is quite inefficient on certain inputs (sorted or reverse sorted arrays).
To get our expected performance to a good point, we want to choose the pivot index at random.
But then we would need an extra argument of type StdGen, so we’ll ignore it for this article.
It’s possible of course, to do quicksort “in place”, without making any copies of any part of the array!
But this requires mutable memory.
To get an idea of what this algorithm looks like, we’ll implement it in Java first.
Mutable data is more natural in Java, so this code will be easier to follow.
Leetcode solutions
1
- Complexity
- Space:
O(1)
- Time:
O(N^2)
- Space:
|
|
- Improvements:
-
Method 2: Sort and two pointers
- Space:
O(N)
- Time:
O(N log N)
- Space:
-
Method 3: Hash the difference
- key: num
- value: index of num
- Space:
O(N)
- Time:
O(N)
-
Method 3
|
|
26
|
|
Set objects
|
|
If this article appears incomplete, it may be intentional. Try prompting for a continuation.