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 algorithm is used internally by most standard library sort implementations (e.g., Python's sorted())?
Answer: Timsort
Timsort, a hybrid of merge sort and insertion sort, is used in Python and Java because it performs well on real-world data.
What is the time complexity of finding the k-th smallest element using a min-heap of size n?
Answer: O(k log n)
Building the heap is O(n), then extracting the minimum k times costs O(k log n) total.
In the context of searching, what is an interpolation search and when does it outperform binary search?
Answer: It searches by value interpolation; O(log log n) on uniformly distributed data
Interpolation search estimates the probe position based on value distribution, achieving O(log log n) average case for uniform distributions.
What is the best-case time complexity of Bubble Sort?
Answer: O(n)
With an early-termination flag, Bubble Sort detects a fully sorted array in a single pass, giving O(n) best case.
Which of the following sorting algorithms is NOT comparison-based?
Answer: Radix Sort
Radix Sort distributes elements into buckets by digit, never comparing elements directly, so it bypasses the O(n log n) lower bound.
When performing binary search on a sorted array, how do you calculate the midpoint to avoid integer overflow?
Answer: mid = low + (high - low) / 2
mid = low + (high - low) / 2 avoids overflow because (high - low) is computed first, which stays within bounds.
What is the space complexity of Merge Sort when sorting an array (not a linked list)?
Answer: O(n)
Merge Sort requires an auxiliary array of size n to store merged results, giving O(n) auxiliary space.