Interview Q&A / Data Structures & Algorithms

1. How do you find all unique triplets in an array that sum to zero?

   Sort the array, fix one number, and use two pointers on the rest to find pairs that cancel it. Skip equal values to avoid duplicate triplets. It runs in O(n squared).

   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. How do you sort an array of 0s, 1s and 2s in a single pass?

   Use the Dutch national flag method with three pointers: low for the next 0 position, high for the next 2 position, and mid scanning. Swap 0s to the front and 2s to the back; leave 1s in the middle.

   IntermediateQuick answerCoding1 min read
4. What is a stable sort and why does it matter?

   A stable sort keeps items with equal keys in their original relative order. It matters when you sort by one field after another, such as by marks first and then keep the earlier name order for ties.

   IntermediateQuick answerCoding1 min read
5. What is counting sort and when can it beat O(n log n)?

   Counting sort counts how many times each value appears in a small integer range, then rebuilds the array from those counts. It runs in O(n + k) time for values in 0..k, so it beats comparison sorts when k is small.

   IntermediateQuick answerCoding1 min read
6. 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