Sorting and Searching Algorithms Flashcards
7 cards from real CodeSignal Technical Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Sorting and Searching Algorithms flashcards as text
Which data structure makes Heap Sort possible, and what is its defining property?
Answer: Binary Heap: parent >= children (max-heap)
Heap Sort uses a binary max-heap where every parent is ≥ its children, enabling O(1) access to the maximum element.
In a 3-way QuickSort (Dutch National Flag partition), what problem does it solve compared to standard 2-way QuickSort?
Answer: It handles arrays with many duplicate keys efficiently
3-way partitioning groups equal elements together, so arrays with many duplicates achieve O(n) or near-linear performance instead of O(n²).
What is the lower bound for comparison-based sorting algorithms, and why?
Answer: O(n log n) because the decision tree has n! leaves requiring height ≥ log₂(n!)
Any comparison-based sort must distinguish n! permutations; a binary decision tree needs at least log₂(n!) ≈ n log n comparisons.
In exponential search, what is the first step before performing binary search?
Answer: Find a range [2^k, 2^(k+1)] where the target may exist
Exponential search doubles the index until arr[i] >= target, bounding the search range, then applies binary search within that range.
What is the average-case time complexity of QuickSort and why?
Answer: O(n log n) because random pivots yield balanced partitions on average
With random pivot selection, expected partition sizes are balanced, giving a recurrence of T(n) = 2T(n/2) + O(n) which solves to O(n log n).
Which technique does Shell Sort use to improve upon Insertion Sort?
Answer: It sorts elements far apart first using decreasing gap sequences
Shell Sort moves elements large distances early by using a gap sequence, reducing the number of shifts needed in final passes.
Given a sorted rotated array (e.g., [4,5,6,1,2,3]), how do you apply binary search to find a target?
Answer: Determine which half is sorted, check if target is in that half, then recurse
At each step, at least one half of a rotated sorted array is fully sorted; check if the target falls in that half to decide which side to recurse on.