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.

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

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.

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.

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.

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.