# Technical Interview Prep

## General Advice

- It's better to find a solution than no solution at all because you're trying only for optimal.
- Ask clarifying questions.
- Understand your inputs. Consider edge cases.

- Talk about your solution before starting to write code.
- Know the Google Tech Dev Guide
- Practice writing code on a whiteboard or paper, or editor without programming support.

## Solving Problems

- If the problem involves a linked list, it's likely that the optimal solution involves two pointers.

## Data Structures

### Hash Maps

#### Design

- Hash function is the most important component. The best hash function depends on the key range and the number of buckets.
- Distribution should be as uniform as possible.
- Trade off between # of buckets and bucket capacity.
- Collisions are inevitable so we need to handle them. Choose the right data structure for each bucket. If there are a small number of items in each bucket, a simple array will suffice. You might need a tree if there are many items in each bucket.
- Worst case, lookup time complexity can be O(n) if all values are in the same bucket and an array is used for the bucket.

#### Usage

- Use to keep track of whether you've seen something before or not.

### Trees

#### Design

- Self-balancing keeps the height across all branches roughly consistent, which is needed for O(log n) operations
- AVL trees are self-balancing binary trees with a tiny memory overhead to store the balance of each node. The value for each node is calculated by
`right tree size - left tree size`

. If the value is -1, 0, or 1, then the tree is balanced enough. If the value falls outside of that range, then some rotations are performed to rebalance the tree.

#### Usage

- Java has a built in
`TreeMap`

which is implemented using a red-black tree.

### Graphs

#### Design

- An adjacency matrix (2d array) can be used to represent a graph. Rows and columns are nodes and cell values are whether the nodes are connected or not.

#### Usage

- BFS is implemented using a queue for items to process and an array to keep track of which nodes have been seen.
- DFS is implemented using a stack for items to process and an array to keep track of which nodes have been seen.