# Technical Interview Prep

• It's better to find a solution than no solution at all because you're trying only for optimal.
• Understand your inputs. Consider edge cases.
• 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.