### 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

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

### 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']

#### 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]


Excerpt from

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