Interview Questions: Part 2
Trees, sorting and more.
Here are more questions you're likely to hear, about trees, sorting, and graphs. Again, aim for an answer you could say in thirty seconds.

- Trees, sorting, graphs
- Thirty second answers
- Say the trade off
BST or hash table?
Why use a binary search tree instead of a hash table? A hash table is faster for simple lookups. But a balanced binary search tree keeps keys in sorted order. So it can find the smallest, the largest, or everything in a range, which a hash table can't do quickly. Both are useful, for different questions.
| key | value |
|---|---|
| Hash table | O(1) lookup, no order |
| Balanced BST | O(log n), sorted |
| BST can | range queries, min, max |
| Choose by | the question you'll ask |
Quick sort or merge sort?
Quick sort or merge sort? Merge sort is always O of N log N, and it's stable, but it needs extra memory. Quick sort is usually faster in practice, and sorts in place, but it can hit O of N squared with bad pivots. Python's own sort, Timsort, is a clever mix of merge sort and insertion sort.
| key | value |
|---|---|
| Merge sort | always n log n, stable |
| Quick sort | fast, in place |
| Quick sort risk | O(n²) worst case |
| Python | Timsort |
BFS or DFS?
When would you use breadth first search instead of depth first? Breadth first explores level by level, so it finds the shortest path in an unweighted graph. Depth first goes deep first, and is natural for exploring everything, detecting cycles, and backtracking. Both are O of vertices plus edges.
| key | value |
|---|---|
| BFS | level by level, a queue |
| BFS finds | shortest steps |
| DFS | deep first, a stack |
| DFS for | cycles, all paths |
Summary
Hash tables are fast but unordered, merge sort is safe and stable, and breadth first search finds the shortest steps. Next, a cheat sheet of every Big O you've learned.
Key takeaways- BST keeps order
- Merge vs quick
- BFS vs DFS