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 programmaker
 I want to be able to do the following:
 Copy the inner text.
 Pipe the inner text into any filter.


BigO
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 bigo
 Log the way the data changes
Some algorithms
$MYGIT/TheAlgorithms/Python
Video
$DUMP$NOTES/ws/facebook/technicalinterview/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/92.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 – doubleended queue


[5, 2, 1, 3]
Datastructures
Heap
Heap is a specialized treebased 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 
BTree  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.