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
What is the time complexity of Radix Sort on n integers each with d digits in base b?
Answer: O(d * (n + b))
Radix Sort performs d passes of counting sort, each taking O(n + b), giving total O(d * (n + b)).
Which searching algorithm works on unindexed data and has a time complexity of O(√n)?
Answer: Jump Search
Jump Search checks elements at intervals of √n and then does a linear scan, achieving O(√n) on sorted arrays.
In the context of CodeSignal problems, why might you prefer an O(n log n) sort over an O(n) counting sort even when the range is small?
Answer: Counting sort requires integer keys and significant extra memory proportional to the range
If the value range k >> n (e.g., sort 10 values in range [0, 10⁹]), counting sort wastes O(k) memory making it impractical.
What is the invariant maintained after each pass of Selection Sort?
Answer: The first i elements are the i smallest elements in sorted order
After i passes, Selection Sort has placed the i smallest elements in their final sorted positions at the beginning of the array.
When would you use Bucket Sort, and what is its average-case time complexity?
Answer: For uniformly distributed floating-point numbers; O(n) average
Bucket Sort distributes n uniformly distributed inputs across n buckets, each with O(1) elements on average, then sorts each bucket in O(1).
What modification to standard binary search allows finding the first occurrence of a target in a sorted array with duplicates?
Answer: When arr[mid] == target, store mid and search the left half to find the first occurrence
Instead of returning on a match, record the index and continue narrowing the search to the left half to find the leftmost occurrence.
What is the primary advantage of using an in-place sorting algorithm like QuickSort over Merge Sort?
Answer: QuickSort uses O(log n) stack space vs Merge Sort's O(n) auxiliary array
QuickSort sorts in place (needing only O(log n) stack space for recursion), while Merge Sort requires an O(n) auxiliary buffer for merging.