AI Hints
Home›DSA in Python Tutorial›Interview Questions
DSA in Python · Lesson 128 of 132

Interview Questions: Part 2

Trees, sorting and more.

⏱ 2 min read▶ Video at 2:32:32🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Interview Questions: Part 2
From the video: Interview Questions: Part 2
  • 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.

keyvalue
Hash tableO(1) lookup, no order
Balanced BSTO(log n), sorted
BST canrange queries, min, max
Choose bythe 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.

keyvalue
Merge sortalways n log n, stable
Quick sortfast, in place
Quick sort riskO(n²) worst case
PythonTimsort

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.

keyvalue
BFSlevel by level, a queue
BFS findsshortest steps
DFSdeep first, a stack
DFS forcycles, 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
Next up: Big O Cheat Sheet — every cost in one place