| Bubble Sort | O(n) best, O(n²) avg/worst, O(1) space — stable |
| Selection Sort | O(n²) all cases, O(1) space — not stable (typical impl) |
| Insertion Sort | O(n) best, O(n²) avg/worst, O(1) space — stable |
| Merge Sort | O(n log n) all cases, O(n) space — stable |
| Quicksort | O(n log n) avg, O(n²) worst, O(log n) space — not stable |
| Heap Sort | O(n log n) all cases, O(1) space — not stable |
| Counting Sort | O(n + k) time, O(k) space — stable, needs bounded integer keys |
| Radix Sort | O(d × (n + k)) time, O(n + k) space — stable, digit-by-digit |
Sorting Algorithms Interview Questions & Answers
Q1. What is bubble sort and how does it work?
A: Bubble sort repeatedly scans the array, comparing each pair of adjacent elements and swapping them if they are out of order. After each full pass, the largest unsorted element "bubbles up" to its correct position at the end, so the next pass can shrink its range by one. It takes n-1 passes in the worst case to fully sort n elements.
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}Q2. What is the time and space complexity of bubble sort?
A: Bubble sort is O(n²) in the average and worst case because it performs nested comparisons across all pairs across n passes. Its best case is O(n) when the optimized version detects a fully sorted array in one pass and exits early. Space complexity is O(1) since it sorts in place using only a temporary swap variable.
Q3. How can bubble sort be optimized with an early-exit flag?
A: Track a boolean flag that starts false at the beginning of each pass and is set true whenever a swap occurs. If a full pass completes with no swaps, the array is already sorted and the algorithm can break out immediately instead of running all n-1 passes unconditionally. This turns the best case (already-sorted input) into O(n) instead of O(n²).
void bubbleSortOptimized(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t;
swapped = true;
}
}
if (!swapped) break; // already sorted
}
}Q4. Is bubble sort stable? Why does that matter?
A: Yes — bubble sort is stable because it only swaps two adjacent elements when the earlier one is strictly greater than the later one, so equal elements are never swapped past each other and keep their original relative order. Stability matters when sorting records by one field while wanting to preserve the pre-existing order of records with equal keys (for example, a secondary sort key).
Q5. When, if ever, would you actually choose bubble sort in production code?
A: Almost never for real workloads — insertion sort dominates it in every practical metric (fewer comparisons and writes on nearly-sorted data). Bubble sort is mainly taught as a simple introduction to swap-based sorting and the concept of algorithmic complexity. Its one arguable niche use is detecting whether a tiny, already-nearly-sorted array needs any work at all, via the early-exit optimization.
Q6. How does selection sort work?
A: Selection sort divides the array into a sorted prefix and an unsorted suffix. On each pass, it scans the entire unsorted suffix to find the minimum element, then swaps it into the front of the unsorted region, growing the sorted prefix by one. It always performs exactly n-1 swaps, regardless of the input's initial order.
void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}Q7. What is the time complexity of selection sort, and why doesn't it improve for a nearly-sorted input?
A: Selection sort is O(n²) in every case — best, average, and worst — because it always scans the entire remaining unsorted suffix to find the minimum, regardless of whether the array is already sorted. Unlike insertion sort or bubble sort, there's no early-exit opportunity: the comparison count is fixed at roughly n²/2 no matter the input arrangement.
Q8. Is selection sort stable by default? How would you make it stable?
A: The standard implementation is not stable, because swapping the found minimum into position i can jump it past equal elements that appeared earlier, changing their relative order. It can be made stable by shifting elements (like insertion sort does) rather than swapping directly, at the cost of extra writes — but at that point it loses its main appeal of a fixed, minimal number of swaps.
Q9. How does selection sort compare to bubble sort in terms of number of swaps?
A: Selection sort performs at most n-1 swaps total, since it swaps only once per pass after identifying the minimum. Bubble sort can perform up to O(n²) swaps in the worst case, since a swap can occur on almost every adjacent comparison. This makes selection sort preferable when swap cost is expensive (e.g., large records) even though both share O(n²) time complexity.
Q10. How does insertion sort work?
A: Insertion sort builds a sorted prefix one element at a time: it takes the next element from the unsorted region and shifts it leftward past all sorted elements greater than it, inserting it into its correct position. This mimics how a person sorts playing cards in hand, picking up one card and inserting it into the already-sorted hand.
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}Q11. What is the best-case time complexity of insertion sort and when does it occur?
A: Insertion sort's best case is O(n), which occurs when the input is already sorted: the inner while loop condition fails immediately for every element, so each element requires only a single comparison and no shifting. This adaptive behavior is a key advantage over selection sort, which cannot exploit an already-sorted input at all.
Q12. Why is insertion sort a good choice for small or nearly-sorted arrays?
A: For small n, the low constant-factor overhead of insertion sort's simple loop beats the higher setup cost of recursive divide-and-conquer sorts like merge sort or quicksort. For nearly-sorted data, each new element only needs to shift a few positions, so total work approaches O(n) rather than O(n²). This is exactly why production sorts like TimSort and Java's dual-pivot quicksort fall back to insertion sort for small subarrays.
Q13. Is insertion sort stable?
A: Yes. The inner loop only shifts an element past elements strictly greater than it (using a strict ">" comparison), so equal elements are never moved past each other — their original relative order is preserved. This stability, combined with its adaptiveness on nearly-sorted runs, is why it's embedded inside more sophisticated hybrid sorts.
Q14. How is insertion sort used inside Java's TimSort implementation?
A: TimSort divides the array into small "runs" (chunks, typically 32-64 elements) and sorts each run using a binary-insertion-sort variant, because insertion sort is extremely fast and cache-friendly on such small sizes. It then merges the sorted runs together using the same merge-sort merge logic, combining insertion sort's small-input efficiency with merge sort's large-input scalability and stability.
Q15. What is merge sort and how does the divide-and-conquer approach work?
A: Merge sort recursively splits the array into two halves until each subarray has zero or one element (trivially sorted), then merges pairs of sorted subarrays back together in sorted order, working back up the recursion. The "divide" step just computes a midpoint (O(1)); all the actual comparison work happens in the "combine" (merge) step.
void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}Q16. What is the time complexity of merge sort in best, average and worst case, and why is it consistent?
A: Merge sort is O(n log n) in all three cases — best, average, and worst — because it always fully splits the array into log n levels and always performs a full O(n) merge at each level, regardless of the input's initial order. Unlike quicksort, there is no data-dependent worst case since the split point is always the midpoint, not a pivot chosen from the data.
Q17. What is the space complexity of merge sort, and can it be done in place?
A: Standard merge sort uses O(n) auxiliary space because the merge step needs a temporary array to hold the merged result before copying it back. A true in-place merge exists in theory but requires complex block-swapping techniques that add significant time overhead, so essentially no practical implementation bothers — the O(n) space cost is accepted as the trade-off for guaranteed O(n log n) time and stability.
Q18. Is merge sort stable? Why?
A: Yes. During the merge step, when comparing the current heads of the two sorted subarrays, ties are resolved by taking the element from the left subarray first (using a "<=" comparison rather than "<"). Since elements from the left subarray always originated earlier in the original array, this preserves their relative order among equal keys.
Q19. How do you merge two sorted subarrays during the merge step?
A: Use two pointers, one per subarray, comparing the elements they point to and copying the smaller one into a temporary output array, advancing that pointer. When one subarray is exhausted, copy the remaining elements of the other subarray directly. Finally, copy the temporary array back over the original range. This runs in O(n) time for a merge of size n.
void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}Q20. What is bottom-up (iterative) merge sort and how does it differ from the recursive version?
A: Bottom-up merge sort skips the recursive divide step entirely and instead starts by treating every single element as a sorted run of size 1, then repeatedly merges adjacent runs of size 1, then size 2, then 4, doubling the run size each pass until the whole array is one sorted run. It achieves the same O(n log n) time and O(n) space as recursive merge sort but avoids call-stack recursion overhead, which can matter for very large arrays or environments with limited stack depth.
Q21. Why is merge sort preferred for sorting linked lists compared to quicksort?
A: Merge sort's merge step only needs sequential access and pointer relinking, which linked lists support natively in O(1) per node — no random-access indexing is required, unlike quicksort's partitioning, which benefits heavily from array-style random access to swap elements efficiently. Additionally, merge sort on a linked list needs no extra array allocation, since nodes can simply be relinked, making it both time- and space-efficient for this data structure.
Q22. What is external merge sort and when is it necessary?
A: External merge sort is used when the dataset is too large to fit in memory: the data is split into chunks small enough to sort in RAM individually (using an in-memory sort), each sorted chunk is written back to disk, and then a multi-way merge reads and combines these sorted chunks sequentially. It's necessary for sorting massive files, database tables, or log data where random disk access is expensive and sequential I/O must be maximized.
Q23. What is quicksort and how does the partitioning step work?
A: Quicksort picks a pivot element, then partitions the array so all elements less than the pivot end up to its left and all elements greater end up to its right, placing the pivot at its final sorted position. It then recursively applies the same process to the left and right partitions. Unlike merge sort, the heavy lifting happens during partition (the "divide" step), and no explicit merge step is needed afterward.
void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}
int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
return i + 1;
}Q24. What is the difference between the Lomuto and Hoare partition schemes?
A: Lomuto's scheme (shown above) uses a single index to track the boundary of elements less than the pivot, scanning left to right and swapping — it's simpler to reason about but performs more swaps on average. Hoare's original scheme uses two pointers starting at opposite ends that move toward each other, swapping when they find an out-of-order pair; it performs fewer swaps on average and handles duplicate-heavy arrays better, though the index bookkeeping is trickier to get right.
Q25. What is the average-case and worst-case time complexity of quicksort, and when does the worst case occur?
A: Quicksort averages O(n log n) because a randomly chosen or well-chosen pivot typically splits the array into roughly balanced halves. The worst case is O(n²), which occurs when the pivot is repeatedly the smallest or largest element (e.g., always picking the first element on an already-sorted or reverse-sorted array), causing highly unbalanced partitions of size 1 and n-1 at every level.
Q26. How does pivot selection strategy affect quicksort performance?
A: A pivot near the true median produces balanced partitions and keeps recursion depth at O(log n), preserving the O(n log n) average case. A consistently poor pivot choice (like always the first or last element on adversarial or sorted input) produces unbalanced O(1)/O(n-1) splits, degrading to O(n²) and O(n) recursion depth. This is exactly why production implementations randomize the pivot or use median-of-three sampling rather than a fixed position.
Q27. What is randomized quicksort and how does it avoid the worst case for adversarial inputs?
A: Randomized quicksort picks the pivot uniformly at random (typically by swapping a random element into the partition boundary position before running the standard partition logic) instead of always using a fixed position like the first or last element. This makes the O(n²) worst case depend on an unlucky sequence of random choices rather than a specific, attacker-crafted input arrangement, so no fixed input can reliably force worst-case behavior — the expected time stays O(n log n) regardless of input order.
int randomizedPartition(int[] arr, int low, int high) {
int randomIndex = low + new Random().nextInt(high - low + 1);
int t = arr[randomIndex]; arr[randomIndex] = arr[high]; arr[high] = t;
return partition(arr, low, high);
}Q28. What is the median-of-three pivot strategy?
A: Median-of-three examines the first, middle, and last elements of the current subarray and picks the median of those three values as the pivot. It's a cheap heuristic (O(1) extra comparisons) that avoids the two worst pivot choices — the true minimum or maximum — on many common patterns like sorted, reverse-sorted, or already-partially-sorted data, without the overhead of a full random-number generator call per partition.
Q29. Why is quicksort typically faster in practice than merge sort despite the same average complexity?
A: Quicksort sorts in place and has better cache locality — it operates on contiguous memory regions with a tight inner loop and low constant-factor overhead, whereas merge sort allocates and copies into auxiliary arrays, adding memory-allocation and copy overhead at every level. Quicksort's partitioning also tends to do fewer total element moves in practice for random data, even though both share the same O(n log n) asymptotic average.
Q30. Is quicksort stable? Can it be made stable?
A: No, standard quicksort is not stable — the partitioning step can swap equal elements past each other in ways that change their relative order. It can be made stable by adding an auxiliary index/tag to each element to break ties consistently, but this defeats quicksort's main appeal (in-place, low memory overhead), so in practice you'd choose merge sort or TimSort instead if stability is required.
Q31. What is the space complexity of quicksort, and why does recursion depth matter?
A: Quicksort itself uses O(1) extra space for partitioning (in-place swaps), but the recursive call stack adds O(log n) space on average for balanced partitions, growing to O(n) in the worst case of consistently unbalanced partitions. This is why production implementations recurse into the smaller partition first and loop (tail-call style) into the larger one, bounding stack depth to O(log n) even in adversarial cases.
Q32. What is 3-way (Dutch National Flag) quicksort partitioning and when is it useful?
A: Instead of a two-way partition (less than / greater than pivot), 3-way partitioning splits into three regions — less than, equal to, and greater than the pivot — using three pointers. This is especially useful when the array contains many duplicate keys, because all elements equal to the pivot are grouped and excluded from further recursion, avoiding the O(n²) degradation that two-way quicksort suffers on arrays with lots of repeated values.
void quickSort3Way(int[] arr, int low, int high) {
if (low >= high) return;
int lt = low, gt = high, i = low + 1;
int pivot = arr[low];
while (i <= gt) {
if (arr[i] < pivot) swap(arr, lt++, i++);
else if (arr[i] > pivot) swap(arr, i, gt--);
else i++;
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}Q33. How would you convert quicksort from recursive to iterative using an explicit stack?
A: Push the initial (low, high) range onto a stack instead of making a recursive call. In a loop, pop a range, partition it, and push the resulting left and right sub-ranges back onto the stack if they contain more than one element, continuing until the stack is empty. This avoids call-stack overhead and gives explicit control over stack depth — you can push the larger partition first and the smaller one last so the smaller range is processed sooner, bounding auxiliary stack usage to O(log n).
Q34. What is introsort, and how does Java use a similar concept?
A: Introsort ("introspective sort") starts with quicksort for speed but monitors recursion depth; if it exceeds a threshold (indicating a degenerating, near-worst-case partition), it switches to heap sort to guarantee O(n log n) worst-case time, and it falls back to insertion sort for small subarrays. Java's dual-pivot quicksort (used by Arrays.sort() on primitives) borrows the same philosophy — it uses insertion sort for tiny ranges and switches partitioning strategy based on array size and structure to avoid pathological cases.
Q35. What is heap sort and how does it use a binary heap?
A: Heap sort first builds a max-heap from the input array (an implicit binary tree stored in array form, where every parent is >= its children). It then repeatedly swaps the root (the maximum element) with the last unsorted element, shrinks the heap by one, and re-heapifies the root — this extracts elements in descending order one at a time, placing them into their correct sorted positions from the end of the array backward.
void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int t = arr[0]; arr[0] = arr[i]; arr[i] = t;
heapify(arr, i, 0);
}
}Q36. What is the time complexity of heap sort in all cases, and why is it more consistent than quicksort?
A: Heap sort is O(n log n) in the best, average, and worst case, because building the initial heap is O(n) and each of the n extraction/heapify steps costs O(log n), regardless of the input's initial arrangement. Unlike quicksort, there is no data-dependent adversarial input that can degrade heap sort's complexity, since the heap-shape invariant guarantees O(log n) height at every step.
Q37. How do you build a max-heap from an unsorted array (heapify)?
A: Starting from the last non-leaf node and moving backward to the root, "sift down" each node: compare it to its children, and if a child is larger, swap and continue sifting down from the child's position until the max-heap property (parent >= children) holds throughout. Doing this bottom-up for all internal nodes builds the full heap in O(n) time overall, not O(n log n), due to the way work is distributed across heap levels.
void heapify(int[] arr, int n, int i) {
int largest = i, left = 2 * i + 1, right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
heapify(arr, n, largest);
}
}Q38. Is heap sort stable? Why not?
A: No. The heapify and swap operations reposition elements based purely on value comparisons with no regard for original index, so two equal elements can easily be swapped into positions that reverse their original relative order during the sift-down process. There's no straightforward, low-overhead way to make heap sort stable without adding auxiliary tie-breaking metadata.
Q39. What is the space complexity advantage of heap sort over merge sort?
A: Heap sort sorts entirely in place using O(1) auxiliary space (just a temp variable for swaps), because the heap is stored within the same array being sorted. Merge sort requires O(n) auxiliary space for its temporary merge buffers. This makes heap sort attractive when memory is tightly constrained and you still need a guaranteed O(n log n) worst case, which quicksort cannot promise.
Q40. Why is heap sort rarely used in practice despite good worst-case guarantees?
A: Heap sort has poor cache locality — sift-down operations jump between parent and child indices that are far apart in memory for large heaps, causing frequent cache misses, unlike quicksort's mostly-sequential partition scans or merge sort's sequential merges. In practice, quicksort (with worst-case mitigations like randomization or introsort fallback) or TimSort deliver better real-world throughput despite heap sort's theoretically clean guarantees.
Q41. What is counting sort and when is it applicable?
A: Counting sort counts the occurrences of each distinct value in an auxiliary count array indexed by value, then reconstructs the sorted output by writing each value out according to its count, in increasing order of value. It's applicable only when keys are integers (or map cleanly to integers) within a small, known range k, because it allocates an array of size k and its complexity depends directly on that range.
void countingSort(int[] arr, int maxVal) {
int[] count = new int[maxVal + 1];
for (int x : arr) count[x]++;
int idx = 0;
for (int v = 0; v <= maxVal; v++) {
while (count[v]-- > 0) arr[idx++] = v;
}
}Q42. What is the time and space complexity of counting sort, and why is it not a general-purpose sort?
A: Counting sort runs in O(n + k) time and O(k) space, where n is the number of elements and k is the range of possible key values. It's not general-purpose because it becomes impractical when k is very large relative to n (e.g., sorting a small array of widely-spread 32-bit integers would need a count array of billions of entries) and it doesn't work at all for non-integer or unbounded-range keys without a mapping step.
Q43. Is counting sort stable, and why does that matter for radix sort?
A: Yes, when implemented with a cumulative count/prefix-sum approach that places elements by scanning the input in original order (or reverse order while decrementing), counting sort preserves relative order among equal keys. This stability is essential for radix sort, which applies counting sort as a subroutine once per digit position — if the per-digit sort weren't stable, the ordering established by less significant digits would be destroyed when sorting by more significant digits.
Q44. What is radix sort and how does it sort numbers digit by digit?
A: Radix sort sorts integers by processing one digit position at a time, from least significant to most significant, using a stable sort (typically counting sort) at each digit. Because each pass is stable, the ordering from earlier (less significant) digit passes is preserved and refined by each subsequent (more significant) digit pass, and after processing all digit positions the array ends up fully sorted.
void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
for (int x : arr) count[(x / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[--count[digit]] = arr[i];
}
System.arraycopy(output, 0, arr, 0, n);
}Q45. What is the time complexity of radix sort, and what do d, n, and k represent?
A: Radix sort runs in O(d × (n + k)) time, where n is the number of elements, k is the number of possible digit values (10 for base-10, or the radix base), and d is the number of digits in the largest key. For fixed-width keys (like 32-bit integers, where d and k are constants), this effectively becomes linear O(n), which is why radix sort can beat O(n log n) comparison sorts for large collections of fixed-size integer keys.
Q46. Why must the digit-sorting subroutine used inside radix sort be stable?
A: Radix sort's correctness relies on each pass refining, not overwriting, the ordering established by prior passes on less significant digits. If the per-digit subroutine were unstable, two elements that already agree on all less-significant digits could end up swapped by a later, more-significant-digit pass, breaking the invariant that elements are correctly ordered up through the digits processed so far.
Q47. What is bucket sort and how does it work?
A: Bucket sort distributes n input elements into a fixed number of buckets based on their value range (e.g., value × numBuckets / maxValue determines the bucket index), sorts each bucket individually (often with insertion sort, since buckets are expected to be small), and then concatenates the buckets in order. It's especially effective when the input is uniformly distributed across a known range, so each bucket ends up with roughly the same, small number of elements.
Q48. What is the average-case complexity of bucket sort, and what assumption does it rely on?
A: Bucket sort achieves O(n + k) average time (where k is the number of buckets), assuming the input is roughly uniformly distributed so each bucket receives O(1) elements on average, making the per-bucket insertion sort constant time. If the distribution is highly skewed and most elements land in one bucket, it degrades toward O(n²) for that bucket's internal sort, so bucket sort's efficiency is data-distribution-dependent, unlike counting or radix sort.
Q49. How do counting sort, radix sort, and bucket sort compare, and when would you choose each?
A: Counting sort is best for a small, known integer range (e.g., sorting exam scores 0-100). Radix sort extends this idea to larger integers or fixed-length strings by sorting digit-by-digit, avoiding a huge count array. Bucket sort is best when data is real-valued or floating-point and roughly uniformly distributed over a range, since it can't rely on discrete digit positions the way radix sort does.
Q50. What does it mean for a sorting algorithm to be stable?
A: A sort is stable if two elements that compare as equal under the sort key retain their original relative order in the output. For example, sorting a list of employees by department where two employees share the same department: a stable sort guarantees they still appear in their original relative order (e.g., by whatever order they were in before, such as by name) within that department group.
Q51. Give a real-world scenario where sort stability matters.
A: Suppose an e-commerce order list is already sorted by order date, and you now want to additionally group orders by customer without losing the date ordering within each customer's group. Sorting by customer ID using a stable sort preserves the pre-existing date order within each group; an unstable sort could scramble the dates within a customer's orders, requiring a full multi-key sort instead of a simple stable re-sort.
Q52. Which common sorting algorithms are stable and which are not?
A: Stable: bubble sort, insertion sort, merge sort, counting sort, radix sort, and TimSort (Java's object sort). Not stable in their standard implementations: selection sort, quicksort, and heap sort — all three rearrange elements via swaps driven purely by value comparison, with no mechanism to preserve original relative order among equal keys.
Q53. Why is O(n log n) considered the lower bound for comparison-based sorting?
A: Any comparison-based sort can be modeled as a decision tree where each internal node is a comparison and each leaf represents one of the n! possible orderings of the input. Since a binary decision tree with n! leaves needs a height of at least log₂(n!) ≈ n log n (by Stirling's approximation), any comparison-based algorithm must make at least Ω(n log n) comparisons in the worst case — this is why non-comparison sorts like counting/radix sort, which exploit key structure rather than pairwise comparisons, can beat this bound.
Q54. What is an adaptive sorting algorithm, and which of the classic algorithms are adaptive?
A: An adaptive algorithm's running time improves when the input is already partially sorted, exploiting existing order rather than ignoring it. Insertion sort and bubble sort (with the early-exit optimization) are adaptive, running close to O(n) on nearly-sorted input. Selection sort, standard heap sort, and standard merge sort are not adaptive — they perform essentially the same amount of work regardless of existing order, though TimSort is specifically designed to be highly adaptive by detecting and exploiting existing sorted runs.
Q55. What sorting algorithm does Arrays.sort() use for primitive arrays?
A: For primitive arrays (int[], long[], double[], etc.), Arrays.sort() uses a dual-pivot quicksort variant (developed by Yaroslavskiy, Bentley, and Bloch), which typically outperforms classic single-pivot quicksort in practice by reducing the number of comparisons and swaps through smarter partitioning into three regions using two pivots. It falls back to insertion sort for small subarrays and is not stable — which is fine, since primitive values have no identity beyond their value, so "stability" is meaningless for them.
int[] nums = {5, 2, 8, 1, 9};
Arrays.sort(nums); // dual-pivot quicksort, O(n log n) average, not stableQ56. What sorting algorithm does Arrays.sort() use for object arrays, and why the difference from primitives?
A: For object arrays (e.g., String[], Integer[], or any array of Comparable / with a supplied Comparator), Arrays.sort() uses TimSort, a stable, adaptive hybrid of merge sort and insertion sort. The difference exists because objects can carry additional state beyond the compared key, so preserving relative order (stability) matters for correctness in ways it never does for bare primitive values.
Q57. What is TimSort and why was it chosen for Java's object sorting?
A: TimSort, originally designed by Tim Peters for Python, identifies naturally occurring sorted "runs" within the input, extends short runs using binary insertion sort up to a minimum length, and then merges runs together using an optimized merge strategy that tracks run lengths on a stack to keep merges balanced. It was chosen for Java because real-world data is often partially sorted, and TimSort exploits that structure for near-linear performance while still guaranteeing O(n log n) worst case and full stability.
Q58. What is a "run" in TimSort, and how does it exploit already-sorted subsequences?
A: A run is a maximal contiguous subsequence of the input that is already either non-decreasing or strictly decreasing (decreasing runs are simply reversed in place to become ascending, which is a stable operation since strict decrease means no ties to worry about). TimSort scans for these naturally occurring runs first, meaning on partially pre-sorted real-world data it can end up doing far less merging work than a naive merge sort that ignores existing order entirely.
Q59. What is the minimum run length in TimSort and why does it matter?
A: TimSort defines a minimum run length (typically between 32 and 64, computed based on array size) so that if a naturally occurring run is shorter than this, it extends the run using binary insertion sort until it reaches the minimum length. This ensures every run is large enough to make merging efficient and keeps the number of runs (and thus merge levels) manageable, balancing the overhead of insertion sort against the overhead of tracking many tiny runs.
Q60. How does Collections.sort() relate to Arrays.sort()?
A: Collections.sort(list) internally delegates to list.sort(null), which for ArrayList and most standard list implementations dumps the elements into an array, sorts that array using the same TimSort implementation that backs Arrays.sort() for objects, and then copies the sorted elements back into the list. So both ultimately share the same TimSort machinery for object/reference types.
List<Integer> list = new ArrayList<>(List.of(5, 2, 8, 1));
Collections.sort(list); // delegates to list.sort(null) -> TimSort internallyQ61. Why can't Arrays.sort() use TimSort for primitives?
A: It technically could, but the JDK authors chose dual-pivot quicksort for primitives specifically because it avoids the extra memory allocation and object-comparison overhead that TimSort's merge-based approach carries, and stability provides no benefit for value types with no independent identity. Dual-pivot quicksort's in-place, low-overhead partitioning is simply faster for raw numeric data where equal values are truly interchangeable.
Q62. What exception can Arrays.sort() throw with a broken Comparator, and why?
A: It can throw IllegalArgumentException("Comparison method violates its general contract!"). TimSort actively checks for contract violations (like a comparator that isn't transitive or consistent, e.g., returning inconsistent results for the same pair depending on call order) during merging, and rather than silently producing a corrupted or incorrectly sorted result, it detects the inconsistency and fails fast so the bug in the comparator gets caught during development or testing.
Q63. What is the time complexity of Arrays.sort() in Java for objects, best/worst case?
A: TimSort guarantees O(n log n) in the worst case, same as classic merge sort, but achieves O(n) in the best case when the input is already sorted or consists of a small number of long, naturally occurring runs — since then minimal merging work is needed beyond detecting and possibly reversing those runs.
Q64. How would you sort a 2D array of objects by multiple keys in Java?
A: Use Comparator.comparing() for the primary key and chain .thenComparing() for each subsequent tie-breaking key, which reads declaratively and relies on TimSort's stability to make each chained key only apply among elements tied on all previous keys. This is far cleaner than writing a hand-rolled multi-field compareTo with nested if/else branches.
list.sort(Comparator.comparing(Employee::getDepartment)
.thenComparing(Employee::getName));Q65. What is the difference between Comparable and Comparator in Java?
A: Comparable<T> is implemented by the class being sorted itself, defining a single "natural ordering" via compareTo() — a class can only have one natural order. Comparator<T> is a separate object defining an ordering externally via compare(a, b), letting you define as many different orderings as needed without modifying the original class, and it's required when the class's source isn't under your control or you need multiple sort criteria.
class Employee implements Comparable<Employee> {
int salary;
public int compareTo(Employee other) {
return Integer.compare(this.salary, other.salary);
}
}
Comparator<Employee> byNameDesc = (a, b) -> b.name.compareTo(a.name);Q66. How do you implement natural ordering using Comparable?
A: Implement the Comparable<T> interface and override compareTo(T other), returning a negative number if this object is "less than" other, zero if equal, and positive if greater. Once implemented, standard sort utilities like Collections.sort() or Arrays.sort() (called without a Comparator argument) automatically use this natural ordering.
class Person implements Comparable<Person> {
String name;
int age;
@Override
public int compareTo(Person other) {
return Integer.compare(this.age, other.age);
}
}
Collections.sort(people); // uses compareTo -> natural ordering by ageQ67. How do you sort a list in descending order using Comparator?
A: Use Comparator.reverseOrder() for natural-ordering types, or wrap any comparator with .reversed(), or write a lambda that flips the subtraction/comparison order. All three approaches ultimately just invert the sign of the comparison result that the underlying sort algorithm uses to decide ordering.
List<Integer> nums = new ArrayList<>(List.of(5, 1, 4, 2));
nums.sort(Comparator.reverseOrder());
// or
nums.sort((a, b) -> b - a);Q68. How do you chain multiple sort keys using Comparator.thenComparing()?
A: Start with a primary Comparator.comparing(keyExtractor), then append one or more .thenComparing(keyExtractor) calls — each subsequent comparator is only consulted to break ties left unresolved by the comparators before it. You can also pass a secondary comparator (like Comparator.reverseOrder()) as a second argument to any thenComparing call to reverse just that one key's direction.
list.sort(Comparator.comparing(Employee::getDepartment)
.thenComparing(Employee::getSalary, Comparator.reverseOrder())
.thenComparing(Employee::getName));Q69. What contract must compareTo()/compare() satisfy, and what happens if it's violated?
A: The contract requires antisymmetry (if a < b then b > a), transitivity (a < b and b < c implies a < c), and consistency (calling it repeatedly on the same pair yields the same sign). Violating this — for example, comparing floating-point values with subtraction that can silently produce inconsistent orderings due to overflow or NaN handling — can cause TimSort to throw IllegalArgumentException, or worse, silently produce an incorrectly ordered result with algorithms that don't perform contract validation.
Q70. What is the difference between Comparator.comparing() and Comparator.comparingInt()?
A: Comparator.comparing() extracts a key that must implement Comparable (or takes an explicit key comparator), and if the key extractor returns a boxed type like Integer, each comparison involves auto-boxing/unboxing overhead. Comparator.comparingInt() (and its comparingLong/comparingDouble siblings) work directly with primitive int keys, avoiding boxing entirely and giving a small but real performance benefit when sorting by a numeric field on a very large collection.
Q71. What is external sorting and when is it needed?
A: External sorting refers to sorting algorithms designed for data that doesn't fit entirely in main memory (RAM) and must be read from and written to slower external storage like disk. It's needed whenever the dataset size exceeds available memory — common in database systems processing large tables, log aggregation pipelines, or big-data batch jobs — where the algorithm must minimize costly random disk I/O and favor sequential access patterns.
Q72. How does external merge sort work across multiple passes?
A: In the first phase, the input is divided into chunks that fit in memory; each chunk is sorted in RAM (using any efficient in-memory sort) and written back to disk as a sorted "run." In the merge phase, a k-way merge repeatedly reads the smallest available element across all runs (using a min-heap to track the current head of each run) and writes it to the output, requiring only a small memory buffer per run regardless of total data size — multiple merge passes may be needed if there are more runs than can be merged in one pass due to file-handle or memory limits.
Q73. How is external sorting relevant to database systems and big data processing?
A: Database query engines use external merge sort internally for operations like ORDER BY, GROUP BY, and sort-merge joins when the intermediate result set exceeds the memory budget allocated to the query. Big data frameworks like Hadoop's MapReduce and Spark rely on external sort-based shuffles to group and sort key-value pairs across nodes when data volumes far exceed any single machine's RAM.
Q74. You need to sort 10 million integers with limited memory. Which algorithm would you choose and why?
A: If the integers fit in available memory, Java's Arrays.sort() (dual-pivot quicksort) is ideal since it's in-place with only O(log n) stack space. If they truly don't fit in memory, use external merge sort: sort manageable chunks in RAM, write sorted runs to disk, and k-way merge them, since this bounds memory usage to a small, constant working set regardless of total input size.
Q75. You need to sort a linked list. Which algorithm is best and why?
A: Merge sort is the standard answer, because its merge step only requires sequential traversal and pointer relinking — no random-access indexing, which linked lists lack efficiently — and it needs no extra array allocation since you can merge by rewiring existing nodes. Quicksort and heap sort both rely heavily on random access for efficient partitioning or heap-index arithmetic, making them a poor fit for linked structures.
Q76. You need to sort user records where original insertion order among equal keys must be preserved. Which algorithm(s) would you use?
A: Any stable sort works: merge sort, insertion sort, TimSort, or counting/radix sort if the key is a bounded integer. In Java specifically, just call Collections.sort() or list.sort(comparator) on object references, since TimSort's stability guarantee is built in — no special handling is required beyond choosing a correct comparator.
Q77. You need to sort an array that's already nearly sorted. Which algorithm performs best?
A: Insertion sort (or TimSort, which is built around this exact scenario) performs best, running close to O(n) because each out-of-place element only needs to shift a few positions. Algorithms like standard merge sort, heap sort, or selection sort ignore existing order entirely and always do the full O(n log n) or O(n²) amount of work regardless of how sorted the input already is.
boolean isNearlySorted(int[] arr, int maxDisplacement) {
for (int i = 0; i < arr.length; i++) {
int correctPos = /* index in fully sorted version */ i;
if (Math.abs(correctPos - i) > maxDisplacement) return false;
}
return true;
}Q78. You need worst-case guarantees for a real-time system. Which sort would you pick?
A: Heap sort or merge sort, since both guarantee O(n log n) in every case with no data-dependent degradation — critical for real-time systems where an unpredictable O(n²) spike (as plain quicksort risks on adversarial input) could violate timing deadlines. Heap sort is preferable if memory is also tightly constrained, since it needs only O(1) extra space versus merge sort's O(n).
Q79. How do you merge overlapping intervals using sorting?
A: Sort the intervals by start time in O(n log n). Then scan left to right, keeping a "current merged interval"; if the next interval's start is <= the current merged interval's end, extend the end to the max of the two; otherwise, close out the current interval and start a new one. Sorting first is what makes the single linear scan sufficient — without it, you'd need to compare every pair of intervals.
int[][] mergeIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
for (int[] iv : intervals) {
if (!result.isEmpty() && iv[0] <= result.get(result.size() - 1)[1]) {
result.get(result.size() - 1)[1] =
Math.max(result.get(result.size() - 1)[1], iv[1]);
} else {
result.add(iv);
}
}
return result.toArray(new int[0][]);
}Q80. How do you find the kth largest element in an array?
A: Three common approaches: sort descending and index k-1 (O(n log n)); maintain a min-heap of size k, pushing elements and popping the smallest whenever size exceeds k, so the heap's root ends up as the kth largest (O(n log k)); or use Quickselect, a partition-based approach that recurses only into the side of the partition containing the kth element, averaging O(n) but degrading to O(n²) worst case like quicksort. The min-heap approach is usually the best balance of simplicity and guaranteed performance in interviews.
int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
minHeap.offer(n);
if (minHeap.size() > k) minHeap.poll();
}
return minHeap.peek();
}Q81. How do you solve the "sort colors" (Dutch National Flag) problem in one pass?
A: Given an array of only three values (0, 1, 2), use three pointers — low, mid, high. If the element at mid is 0, swap it to the low region and advance both low and mid; if it's 1, just advance mid (it's already correctly placed in the middle region); if it's 2, swap it to the high region and decrement high without advancing mid, since the newly swapped-in element still needs to be examined. This sorts the array in a single O(n) pass with O(1) extra space and no general-purpose comparison sort needed.
void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
int t = nums[low]; nums[low] = nums[mid]; nums[mid] = t;
low++; mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
int t = nums[mid]; nums[mid] = nums[high]; nums[high] = t;
high--;
}
}
}Q82. How do you sort an array of 0s and 1s in place?
A: This is a simplified two-way version of the Dutch National Flag partition: use two pointers, one scanning from the left looking for a 1 to swap out, one from the right looking for a 0 to swap in, and swap whenever both are found, moving inward. Since there are only two distinct values, this is equivalent to Lomuto/Hoare partitioning around the value 1, and it runs in a single O(n) pass with O(1) space.
Q83. How do you find if two arrays are permutations of each other using sorting?
A: If the arrays differ in length, they can't be permutations. Otherwise, sort both arrays (O(n log n) each) and compare them element by element — if every position matches, they contain the same multiset of elements and are permutations of one another. A faster O(n) alternative uses a frequency HashMap instead of sorting, incrementing counts for one array and decrementing for the other, checking all counts return to zero.
Q84. How do you sort a nearly sorted array where each element is at most k positions away from its sorted position?
A: Maintain a min-heap of size k+1: push the first k+1 elements, then repeatedly pop the minimum (which is guaranteed to be the next correct element in sorted order, since no smaller element can appear beyond k positions ahead) and push the next unprocessed element. This achieves O(n log k) time, far better than a full O(n log n) sort when k is small relative to n.
void sortKSortedArray(int[] arr, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
int idx = 0;
for (int i = 0; i < arr.length; i++) {
heap.offer(arr[i]);
if (heap.size() > k) arr[idx++] = heap.poll();
}
while (!heap.isEmpty()) arr[idx++] = heap.poll();
}Q85. How do you find the top k frequent elements using sorting/heap?
A: First build a frequency map in O(n) with a single pass. Then use a min-heap of size k ordered by frequency: push each distinct element, popping the least-frequent one whenever the heap exceeds size k, leaving the k most frequent elements at the end. This runs in O(n log k) time, better than fully sorting all distinct elements by frequency (O(n log n)) when k is much smaller than the number of distinct values.
List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
PriorityQueue<Integer> heap =
new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b));
for (int key : freq.keySet()) {
heap.offer(key);
if (heap.size() > k) heap.poll();
}
return new ArrayList<>(heap);
}Q86. How do you sort an array according to the frequency of elements?
A: Build a frequency map in O(n), then sort the distinct elements by a comparator that orders primarily by descending frequency and secondarily by value (or original position, for a stable tie-break), and finally expand each element out according to its count. This is O(n log n) overall, dominated by the sort of distinct keys.
Q87. How do you find the minimum number of swaps to sort an array?
A: Pair each value with its target sorted index, then think of the array as a graph where each element points to where it should go — this decomposes into disjoint cycles. For a cycle of length L, exactly L-1 swaps are needed to place every element correctly, so the answer is the sum of (cycle length - 1) across all cycles, computable in O(n log n) (dominated by determining the sorted positions) plus O(n) for the cycle traversal.
Q88. How do you determine if an array can be sorted with at most one swap?
A: Create a sorted copy of the array and compare it position by position against the original, collecting the indices where they differ. If there are zero differing positions, the array is already sorted; if there are exactly two differing positions and swapping those two elements in the original produces the sorted array, one swap suffices; any other count of mismatches means one swap is not enough. This runs in O(n log n) due to the sort, with an O(n) comparison pass.
Q89. How do you sort an "almost sorted" array of strings case-insensitively?
A: Use insertion sort (since the array is nearly sorted, it will run close to O(n)) with a comparator that calls String.compareToIgnoreCase() instead of the default case-sensitive comparison. In Java, this maps to list.sort(String::compareToIgnoreCase) or Comparator.comparing(String::toLowerCase), letting TimSort's adaptiveness on nearly-sorted data take over automatically rather than hand-rolling insertion sort.
Q90. How do you sort meeting intervals to find the minimum number of meeting rooms required?
A: Separate all start times and all end times into two arrays and sort each independently in O(n log n). Then use two pointers to walk through both sorted arrays simultaneously: whenever the next start time is earlier than the next end time, a new room is needed (increment a room counter); otherwise a room frees up (decrement). Track the maximum concurrent room count seen — that's the answer.
int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0, maxRooms = 0, s = 0, e = 0;
while (s < n) {
if (starts[s] < ends[e]) { rooms++; s++; }
else { rooms--; e++; }
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}Q91. What is a stable sort's role in a multi-pass sorting pipeline (e.g., sort by department then by name)?
A: With a stable sort, you can achieve a multi-key sort by sorting on the least significant key first, then on the next key, and so on up to the most significant key — each pass preserves the ordering established by the previous pass among ties. This is the same principle radix sort relies on for digits, and it lets you build up a multi-field sort from repeated single-field stable sorts, though in Java it's more common and efficient to just chain comparators with thenComparing() in one pass.
Q92. How would you sort a stream of numbers where you only get one pass and limited memory (e.g., median maintenance)?
A: You can't fully sort under those constraints, but for running statistics like the median, maintain two heaps: a max-heap for the smaller half of numbers seen so far and a min-heap for the larger half, keeping their sizes balanced (differing by at most one). Each new number is inserted into the appropriate heap and rebalanced in O(log n), and the median is available in O(1) from the heap roots at any time, without ever fully sorting the stream.
Q93. What is the difference between in-place and out-of-place sorting algorithms?
A: An in-place algorithm sorts using only O(1) (or O(log n) for recursion stack) extra space beyond the input array itself — quicksort, heap sort, insertion sort, selection sort, and bubble sort are all in-place. An out-of-place algorithm requires auxiliary space proportional to the input size — standard merge sort (O(n) temp arrays) and counting/radix sort (O(n+k) auxiliary arrays) are out-of-place, trading memory for other benefits like stability or guaranteed complexity.
Q94. What is a sorting network, and where might it be used?
A: A sorting network is a fixed sequence of compare-and-swap operations between specific index pairs, determined entirely in advance regardless of the actual data values — unlike normal sorts, the sequence of comparisons never branches based on the outcome of a comparison. This makes sorting networks ideal for hardware implementations (parallel circuits), GPU/SIMD sorting of small fixed-size arrays, and cryptographic contexts where data-independent execution timing (to avoid side-channel leaks) matters more than raw average-case speed.
Q95. How would you parallelize merge sort across multiple threads/cores?
A: Use the fork/join pattern: recursively split the array in half, spawning a new task (or thread) for each half once the array is above some size threshold, and fall back to sequential sorting below that threshold to avoid excessive task overhead on tiny subarrays. After both halves complete, merge them — the merge step itself can also be parallelized for very large arrays, though it's more complex to implement correctly.
class MergeSortTask extends RecursiveAction {
int[] arr; int low, high;
protected void compute() {
if (high - low < 2) return;
int mid = (low + high) / 2;
MergeSortTask left = new MergeSortTask(arr, low, mid);
MergeSortTask right = new MergeSortTask(arr, mid, high);
invokeAll(left, right);
merge(arr, low, mid, high);
}
}Q96. What is the significance of Arrays.parallelSort() in Java?
A: Arrays.parallelSort() uses the Fork/Join framework to split large arrays into subranges, sort each subrange (often in parallel using a parallel merge sort variant), and merge the results using multiple CPU cores. For large arrays (the JDK uses a size threshold, typically around 8192 elements, below which it just calls the sequential sort), this can significantly reduce wall-clock time on multi-core machines, though it uses more total CPU work and extra memory than the sequential version.
int[] nums = new int[10_000_000];
Arrays.parallelSort(nums); // splits into subranges, sorts in parallel, mergesQ97. How do you sort a Map by its values in Java?
A: Since Map has no inherent order, stream its entrySet(), sort using Map.Entry.comparingByValue() (optionally reversed or combined with a secondary key comparator), and collect the result into a new LinkedHashMap if you need to preserve the sorted iteration order, since regular HashMap does not guarantee iteration order.
Map<String, Integer> map = new HashMap<>();
map.entrySet()
.stream()
.sorted(Map.Entry.comparingByValue())
.forEach(e -> System.out.println(e.getKey() + "=" + e.getValue()));Q98. How do you detect if an array is already sorted in O(n) time?
A: Scan the array once, comparing each element to its predecessor; if any element is smaller than the one before it, the array is not sorted and you can return immediately. If the scan completes without finding an inversion, the array is sorted. This is a useful early check before committing to an O(n log n) sort, especially combined with an adaptive algorithm like insertion sort or TimSort that would detect this anyway.
boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) return false;
}
return true;
}Q99. What is the difference between sort() and sorted() semantics when discussing mutability?
A: Methods like List.sort(), Collections.sort(), and Arrays.sort() mutate the underlying array or list in place and return void. Java Streams' Stream.sorted() instead returns a new stream that will produce elements in sorted order, leaving the original source collection completely untouched — you must collect the result into a new list if you want a sorted collection to persist.
Q100. How do you sort strings by length then lexicographically?
A: Chain two comparators: a primary one comparing by string length using Comparator.comparingInt(String::length), and a secondary one using .thenComparing(Comparator.naturalOrder()) to break ties between strings of equal length using standard lexicographic ordering.
List<String> words = new ArrayList<>(List.of("banana", "kiwi", "fig", "apple"));
words.sort(Comparator.comparingInt(String::length)
.thenComparing(Comparator.naturalOrder()));Q101. What happens if you use a Comparator that isn't consistent with equals()?
A: The sort itself will still complete correctly according to the comparator's own logic, but sorted-collection classes like TreeSet or TreeMap use the comparator (not equals()) to determine uniqueness — so two objects that are compare()-equal but equals()-unequal will be treated as duplicates and one silently discarded when added to a TreeSet. This subtle mismatch is a common source of bugs when a comparator only considers a subset of an object's fields.
Q102. How would you sort a huge dataset that doesn't fit in memory using cloud/distributed systems (conceptual)?
A: Use a distributed sort-merge approach: partition the data across multiple worker nodes (often by a range or hash of the sort key), have each node sort its local partition in memory or via external sort if needed, and then either merge results directly if partitions were range-based (each partition already covers a disjoint, ordered key range) or perform a distributed merge/shuffle phase (as in MapReduce's shuffle-and-sort) to combine hash-partitioned results into a globally sorted order.
Q103. What is Shell sort, and how does it improve on insertion sort?
A: Shell sort generalizes insertion sort by first sorting elements that are far apart (using a decreasing sequence of "gaps"), gradually reducing the gap down to 1 (standard insertion sort). Early passes with large gaps move out-of-place elements long distances quickly, so by the time the gap shrinks to 1, the array is already close to sorted, making that final pass much cheaper than plain insertion sort on the original unsorted array — achieving roughly O(n log² n) with good gap sequences, better than O(n²) but still worse than O(n log n).
Q104. What is TimSort's worst-case time complexity, and how does it guarantee O(n log n)?
A: TimSort guarantees O(n log n) worst case because, no matter how the runs are distributed, its merge strategy uses a stack-based invariant (tracked run lengths must satisfy certain size relationships, triggering a merge when violated) that keeps the total number of merge operations and total elements moved bounded to O(n log n), the same bound as classic merge sort. Its adaptiveness only ever helps (reducing work on partially sorted input); it never causes worse-than-merge-sort behavior even on adversarial input.
Q105. How do you sort an array containing only two distinct values efficiently?
A: Treat it as a simplified partition problem: use two pointers, one from the left seeking the "wrong" value and one from the right seeking the other "wrong" value, swapping them toward the correct side, similar to the two-region case of Dutch National Flag partitioning. This sorts the array in a single O(n) pass with O(1) space, no comparison-based general sort needed.
Q106. What is pancake sort, and why is it mentioned in some algorithm courses?
A: Pancake sort only allows one operation: flipping (reversing) a prefix of the array, mimicking flipping a stack of pancakes with a spatula. It repeatedly finds the maximum unsorted element and flips it to the front, then flips the growing sorted suffix to place it correctly, running in O(n²) time. It's mainly a teaching curiosity for reasoning about algorithms under unusual operation constraints (this exact idea underlies the "pancake flipping problem" in computational theory), not a practical sort.
Q107. How do you verify whether a given array is a valid result of stable-sorting another array by a specific key?
A: First confirm the output is correctly non-decreasing by the sort key. Then, for every group of elements sharing an equal key, verify that their relative order matches their relative order in the original array — this can be checked by tagging each original element with its original index before sorting and confirming that within each equal-key group in the output, the original indices appear in increasing order.
Q108. What's the risk of using a naive recursive quicksort on an already-sorted array with a fixed first-element pivot?
A: Choosing the first element as pivot on an already-sorted array means every partition splits into an empty left side and a right side of size n-1, since nothing is ever smaller than the current minimum-valued pivot. This produces maximally unbalanced recursion at every level, degrading to O(n²) time and O(n) recursion depth (risking a stack overflow on large inputs) — exactly the pathological case that pivot randomization or median-of-three selection is designed to prevent.
Q109. How do you sort objects by a key extracted with a custom function without modifying the original objects (schwartzian transform)?
A: Compute the derived sort key for each object once upfront, pair it with the original object (e.g., using a small wrapper or Map.Entry), sort the pairs by the precomputed key, and then extract just the objects back out in the new order. This avoids recomputing an expensive key-extraction function repeatedly during comparisons (which a naive Comparator calling the extractor inline would do on every comparison), turning O(n log n) key computations into just O(n).
Q110. How would you explain to an interviewer why you'd pick merge sort over quicksort for sorting on disk-backed data?
A: Merge sort's access pattern is fundamentally sequential — it reads and writes runs of data in order during both the split and merge phases, which maps naturally onto sequential disk/file I/O and is the basis of external merge sort. Quicksort's partitioning requires random access and in-place swapping across the full range being partitioned, which translates to expensive random disk seeks when the data doesn't fit in memory, making it a poor fit for external sorting despite being faster for in-memory workloads.
Q111. How do you find the median of two sorted arrays without full merging?
A: The optimal approach uses binary search over the smaller array's partition point to find a split where all elements on the left side of both arrays combined are <= all elements on the right side, achieving O(log(min(m,n))) time. A simpler but less optimal O(m+n) approach just walks both arrays with two pointers like a merge step, stopping once you've advanced past the middle element(s) without building the full merged array.
double findMedianSortedArrays(int[] a, int[] b) {
int i = 0, j = 0, count = 0, total = a.length + b.length;
int prev = 0, curr = 0;
while (count <= total / 2) {
prev = curr;
if (i < a.length && (j >= b.length || a[i] <= b[j])) curr = a[i++];
else curr = b[j++];
count++;
}
return (total % 2 == 0) ? (prev + curr) / 2.0 : curr;
}Q112. What are common mistakes candidates make when implementing quicksort in an interview?
A: Common mistakes include off-by-one errors in the partition loop bounds, forgetting to handle duplicate values (causing infinite loops in Hoare's scheme if the pointers don't move past equal elements), always picking a fixed pivot (like the first element) which invites the O(n²) worst case on sorted/adversarial input, and forgetting the base case check (low < high) which can cause infinite recursion on single-element or empty subarrays. Interviewers often probe specifically for awareness of the worst-case pivot scenario and how to mitigate it.
Post a Comment
Add