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.
1
2

1,3,4,5,7,9
0,4,5,6,8,9

Big-O Complexity Chart

O
1
log n
n
n log n
n^2
2^n
n!

Python syntax

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

True
and
or
[1, 2, 3, 4]                                     # list
b = a                                            # assignment
b == a                                           # objects are equal
b is a                                           # the same object
"This is a string."                              # string
'This is also a string.'
"This is a string"[0]                            # string is list
"{} can be {}".format("Strings", "interpolated") # interpolation
name = "Reiko"
f"She said her name is {name}."                  # f-string
None is not None                                 # False
None is None                                     # True
not None                                         # True
print("Hello, World")                            # chomp
"yahoo!" if 3 > 2 else 2                         # ?:
li.append(3)                                     # li is now [1, 2, 4, 3]
li.pop()                                         # => 3 and li is now [1, 2, 4]
li[-1]                                           # => 3
a = a + [5]                                      # append to list
li.insert(1, 2)                                  # li is now [1, 2, 3] again. Insert an element at a specific index
if not root: return 0                            # One-liner if
d["shane"] = "megan"
# {'shane': 'megan'}

default dictionary

1

egr python default dictionary
1
2
3
4
5
6
7

from collections import defaultdict
ice_cream = defaultdict(lambda: 'Vanilla')
ice_cream = defaultdict(lambda: 'Vanilla')
ice_cream['Sarah'] = 'Chunky Monkey'
ice_cream['Abdul'] = 'Butter Pecan'
print(ice_cream['Sarah'])
print(ice_cream['Joe'])
Chunky Monkey
Vanilla

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Node:
    def __init__(self, v):
        self.val = v
        self.left = None
        self.right = None

def _collect(node, data, depth = 0):
    """ DFS traverse the Node tree, whilst remembering the current depth.
    add the nodes to a list of node lists"""
    if not node:
        return None

    if depth not in data:
        data[depth] = []

    data[depth].append(node.val)

    _collect(node.left, data, depth + 1)
    _collect(node.right, data, depth + 1)

def avg_by_depth(node):
    data = {}
    _collect(node, data)

    result = []

    i = 0
    for i in data:
        nums = data[i]
        avg = sum(nums) / len(nums)
        result.append(avg)
        i += 1

    return result

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

1

['a', 'b', 'c', 'd', 'e', 'f', 'g']

z=3

1

['e', 'f', 'g', 'a', 'b', 'c', 'd']

Advanced python syntax

unpacking

1
2
3

# multiple assignment from an array
array = [5, 10, 15, 20]
five, ten, fift, twent = array
1
2
3

# unpack a sublist into a single variable while doing multiple assigment
a, *b, c = [1, 2, 3, 4, 5]
print(b)
[2, 3, 4]

more unpacking

1
2

# unpack a dictionary into a dictionary
print({'a': 1, **{'b': 2}})
{'a': 1, 'b': 2}

Named slices

1
2
3
4

a = [0, 1, 2, 3, 4, 5]
LASTTHREE = slice(-3, None)
slice(-3, None, None)
print(a[LASTTHREE])
[3, 4, 5]

Deque – double-ended queue

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import collections
Q = collections.deque()
Q.append(1)
Q.appendleft(2)
Q.extend([3, 4])
Q.extendleft([5, 6])
Q.pop()
Q.popleft()
Q.rotate(3)
Q.rotate(-3)
print(list(Q))
[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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Skip list
    - sorted

    https://www.youtube.com/watch?v=ypod5jeYzAU

    The idea is simple, we create multiple
    layers in a sorted list so that we can
    skip some nodes.

    A data structure that allows search
    complexity as well as insertion complexity
    within an ordered sequence of elements.

    Thus it can get the best features of an
    array while maintaining a linked list-like
    structure

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:
  1. Correct position in final, sorted array
    1. Items to the left are smaller
    2. Items to the right are larger
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def quickSort(arr):
    less = []
    pivotList = []
    more = []
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)
        less = quickSort(less)
        more = quickSort(more)
        return less + pivotList + more

a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quickSort(a)
print(a)
[-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.

1
2
3
4
5
6

quicksort1 :: (Ord a) => [a] -> [a]
quicksort1 [] = []
quicksort1 (x:xs) =
  let smallerSorted = quicksort1 [a | a <- xs, a <= x]
      biggerSorted = quicksort1 [a | a <- xs, a > x]
  in  smallerSorted ++ [x] ++ biggerSorted
1
2
3
4
5
6

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import Dict, Tuple, Sequence, List

class Solution:
    def two_sum(self, nums: List[int], target: int) -> List[int]:
        for i, n1 in enumerate(nums):
            for j, n2 in enumerate(nums):
                if i >= j: continue
                if n1 + n2 == target:
                    return [i, j]

def main():
    s = Solution()
    print(s.two_sum([5,6,10,13], 16))

if __name__ == "__main__":
    main()
  • Improvements:

    • Method 2: Sort and two pointers

      • Space: O(N)
      • Time: O(N log N)

    • Method 3: Hash the difference

      • key: num
      • value: index of num
      • Space: O(N)
      • Time: O(N)

Method 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from typing import Dict, Tuple, Sequence, List

class Solution:
    def two_sum(self, nums: List[int], target: int) -> List[int]:
        num_to_id = {}
        for i, num in enumerate(nums):
            if target - num in num_to_id:
                return [i, num_to_id[target - num]]
            else:
                num_to_id[num] = i

def main():
    s = Solution()
    print(s.two_sum([5,6,10,13], 16))
    print(s.two_sum([5,6,10,13], 16))

if __name__ == "__main__":
    main()

26

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from typing import Dict, Tuple, Sequence, List

class Solution:
    def remove_duplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        i = 1
        while i < len(nums):
            if nums[i] == nums[i-1]:
                del nums[i]
            else:
                i += 1

        return i


def main():
    s = Solution()
    print(s.remove_duplicates([1, 1, 2]))
    print(s.remove_duplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]))


if __name__ == '__main__':
    main()

Set objects

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# number of elements in set s (cardinality)
len(s)

# test x for membership in s
x in s

# test x for non-membership in s
x not in s

# test whether every element in s is in t
s.issubset(t)
s <= t

# test whether every element in t is in s
s.issuperset(t)
s >= t

# new set with elements from both s and t
s.union(t)
s | t

# new set with elements common to s and t
s.intersection(t)
s & t

# new set with elements in s but not in t
s.difference(t)
s - t

# new set with elements in either s or t but not both
s.symmetric_difference(t)
s ^ t

# new set with a shallow copy of s
s.copy()