Interview Q&A / Data Structures & Algorithms

1. How do you compute x to the power n efficiently with recursion?

   Use divide and conquer: x^n equals (x^(n/2)) squared, times x if n is odd. That halves n each time, so it needs only O(log n) multiplications instead of O(n).

   IntermediateQuick answerCoding1 min read
2. How do you implement quick sort, and when does it become slow?

   Pick a pivot, partition so smaller elements go left and larger go right, then recursively sort both sides. It averages O(n log n) but becomes O(n squared) when the pivot is always the smallest or largest element.

   IntermediateQuick answerCoding1 min read
3. What is the difference between merge sort and quick sort?

   Merge sort splits the array in half, sorts each half and merges them; it is always O(n log n) and stable but needs O(n) extra space. Quick sort partitions around a pivot in place; it averages O(n log n) but can degrade to O(n squared) with bad pivots.

   IntermediateQuick answer1 min read