CodeSignal Technical Assessment Sorting and Searching Algorithms 3 ā Questions and Answers
Question 1: Which algorithm is used internally by most standard library sort implementations (e.g., Python's sorted())?
- QuickSort
- Merge Sort
- Timsort (Correct answer)
- Heap Sort
Correct 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.
Question 2: What is the time complexity of finding the k-th smallest element using a min-heap of size n?
- O(n)
- O(k log n) (Correct answer)
- O(n log k)
- O(k + n)
Correct answer: O(k log n)
Building the heap is O(n), then extracting the minimum k times costs O(k log n) total.
Question 3: In the context of searching, what is an interpolation search and when does it outperform binary search?
- It searches by value interpolation; O(log log n) on uniformly distributed data (Correct answer)
- It searches in O(1) using hash tables
- It is identical to binary search but uses recursion
- It is faster only on unsorted data
Correct 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.
Question 4: What is the best-case time complexity of Bubble Sort?
- O(nĀ²)
- O(n log n)
- O(n) (Correct answer)
- O(1)
Correct answer: O(n)
With an early-termination flag, Bubble Sort detects a fully sorted array in a single pass, giving O(n) best case.
Question 5: Which of the following sorting algorithms is NOT comparison-based?
- Heap Sort
- Radix Sort (Correct answer)
- Merge Sort
- QuickSort
Correct 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.
Question 6: When performing binary search on a sorted array, how do you calculate the midpoint to avoid integer overflow?
- mid = (low + high) / 2
- mid = low + (high - low) / 2 (Correct answer)
- mid = high - (high - low) / 2
- mid = (low * high) / 2
Correct answer: mid = low + (high - low) / 2
mid = low + (high - low) / 2 avoids overflow because (high - low) is computed first, which stays within bounds.
Question 7: What is the space complexity of Merge Sort when sorting an array (not a linked list)?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n log n)
Correct answer: O(n)
Merge Sort requires an auxiliary array of size n to store merged results, giving O(n) auxiliary space.
CodeSignal Technical Assessment Sorting and Searching Algorithms 3
Which algorithm is used internally by most standard library sort implementations (e.g., Python's sorted())?