To learn

- graphs
- trees
- array two pointers
- Topological sort (BFS)
- Python
`bisect`

module - Matrix algorithms
- Sliding window algorithm

Below is a collection of (technical) tips for coding interviews. This list is based on my experience and might not be exhaustive.

- Initialize array with values
- 1-D:
`[0] * n`

- 2-D:
`[[0] * cols for _ in range(rows)]`

- 1-D:
- Arrays/lists are the same in Python, initialized via
`l = []`

- Find first zero-based index of element with
`l.index('foo')`

- Slice
`l[start:end]`

where`start`

is inclusive and`end`

is exclusive - Retrieve last item with
`l[-1]`

- A matrix of size
`M * N`

has`M + N - 1`

diagonals - Diagonals can be computed either via
`-i + j`

or`i + j`

, depending on the direction and then added to a map /`dict`

. - When counting elements in an array, it makes sense to advance the second pointer
`p2`

and then check for violation of constraints. Afterwards advance the pointer`p1`

until the violation is resolved `range(start, stop, step)`

has`start`

inclusive and`stop`

exclusive- When iterating through an array it might make sense to move the boundaries instead of changing the pointer, see this

- It’s possible to add up boolean values
`True + True + False == 2`

- Pop first item of a list
`l.pop(0)`

, otherwise`l.pop()`

pops the last item. `sortedcontainers.SortedList`

is a special (open-source) implementation of a sorted list

- A map in Python is a
`dict`

`d = collections.defaultdict(list)`

provides a dictionary with a factory method- Then use
`d['missing_key'].append(...)`

to append to a missing key

- Then use

- Sets are unordered in Python
- Initialize via
`s = set()`

- Get first/only item
`list(s)[0]`

- Intersection of two sets
`intersect = a & b`

- Union of two sets
`union = a | b`

- This also works with
`dict.keys()`

- A list can be used as a stack in Python by using
`l.append(item)`

to add a new item to the stack`l.pop()`

to return and remove an item from the stack`pop`

will return an`IndexError`

if no item is on the stack, it should be checked before calling

- Get ASCII position of characters via
`ord('a')`

- Distance between two ASCII positions
`ord('a') - ord('b')`

- When comparing the distance with wrapping, use
`ord('a') - ord('z') == -25 % 26 == 1 == ord('b') - ord('a')`

`s.isdecimal()`

returns true if`s`

is a decimal number`s.isalnum()`

returns`True`

if`s`

is alphanumeric`[0-9a-z]`

- Also known as Priority Queue
- In Python there’s the
`heapq`

library which implements a min-heap- Push to heap via
`heapq.heappush(heap, item)`

- Pop from heap via
`heapq.heappop(heap)`

- Push to heap via
- The smallest element is always at the front
`heap[0]`

- Time complexity to build:
`O(n * log n)`

- Time complexity to insert one element:
`O(log n)`

- Number of nodes in a binary tree, if all nodes are there:
`pow(2, height) - 1`

- Height of (complete) binary tree:
`h = log2(n)`

- A tree can be converted into a graph to find arbitrary nodes

- Deep copy of binary tree

Visit the current node. Recursively traverse the current node’s left subtree. Recursively traverse the current node’s right subtree. The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.

Recursively traverse the current node’s left subtree. Recursively traverse the current node’s right subtree. Visit the current node. Post-order traversal can be useful to get postfix expression of a binary expression tree.

Recursively traverse the current node’s left subtree. Visit the current node. Recursively traverse the current node’s right subtree. In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.[7]

- A graph is a tree with loops
- Time complexity
- Space complexity
- Deep copy of graph: TODO Algorithm

- Use whenever there is a question for shortest path
- Iterative is easy to use with
`queue`

, stop when`queue`

is empty - Tip for
`directions = [[1,0], [0,1], [-1,0], [0,-1], [1,1], [-1,-1], [1,-1], [-1,1]]`

- Improvement is A* algorithm
- Can also be used with a
`queue = [(node1, distance1)]`

to find nodes within a distance from origin. Important to keep track of`visited = set()`

nodes to avoid loops

- Use to find nodes with distance
`n`

from`target`

node - Use to find size of island, more efficient than BFS

Short for re**trie**val tree.

- Created via multiple hash functions (look up murmurhash)
- Stored as a bitarray.
- Does not give false negatives, but might produce false positives
- Is append only, data can only be added, not removed

Example Python implementation

`37^100`

is`37 * 37^99`

is`37^50 * 37^50`

, Thus we only have to compute the left part and need`log2(100)`

iterations. This is useful for implementing`pow(x,y)`

- Use
`random.choice(list)`

to pick a random element from a list

`threading.Semaphore(n)`

provides a semaphore with`n`

capacity that can be used via`acquire()`

and`release()`

`threading.Barrier(n)`

provides a barrier where all threads have to`wait()`

until the capacity is reached

- 200 - OK
- 400 - Bad Request
- 401 - Unauthorized
- 403 - Forbidden
- 404 - Not found
- 406 - Not acceptable (Cannot produce response according to defined accepted responses, e.g. JSON)

- Low write/high read choose SQL
- Try not to be too clever in solutions, leave room for follow up questions

- Simplified either list or card/detail endpoints
- Follow Ruby on Rails routing schema (plural,
`/companies`

,`/companies/1`

) - Use HTTP verbs (GET, PUT, POST, DELETE)
- Return the whole data that is needed in the response, unless to expensive
- Too expensive can be if stored in another database
- Almost never want to have the frontend request the data