CodeSignal Technical Assessment Sorting and Searching Algorithms 2 ā Questions and Answers
Question 1: What is the worst-case time complexity of QuickSort when the pivot is always the smallest or largest element?
- O(n log n)
- O(nĀ²) (Correct answer)
- O(n)
- O(log n)
Correct answer: O(nĀ²)
When the pivot is always the min or max, each partition produces one empty subarray and one of size n-1, leading to O(nĀ²) recursive calls.
Question 2: Which property must an array satisfy for binary search to work correctly?
- Elements must be unique
- Array must be sorted (Correct answer)
- Array length must be a power of 2
- Elements must be integers
Correct answer: Array must be sorted
Binary search relies on the sorted order to determine which half to discard at each step.
Question 3: Merge sort on a linked list is preferred over QuickSort because:
- Merge sort uses less memory on linked lists
- Linked lists allow O(1) merging without extra space (Correct answer)
- QuickSort cannot be implemented on linked lists
- Merge sort is always faster
Correct answer: Linked lists allow O(1) merging without extra space
Merging linked list nodes requires only pointer reassignment (O(1) extra space), unlike arrays which need auxiliary buffers.
Question 4: What is the space complexity of the iterative version of binary search?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n log n)
Correct answer: O(1)
Iterative binary search uses a constant number of pointer variables regardless of input size.
Question 5: In a stable sort, what is preserved?
- The relative order of equal elements (Correct answer)
- The absolute positions of all elements
- The sorted order is achieved in fewer swaps
- Only unique elements are kept
Correct answer: The relative order of equal elements
A stable sort guarantees that elements with equal keys appear in the output in the same relative order as the input.
Question 6: Which sorting algorithm is most efficient for sorting a nearly-sorted array with only a few elements out of place?
- Merge Sort
- Heap Sort
- Insertion Sort (Correct answer)
- Shell Sort
Correct answer: Insertion Sort
Insertion sort runs in O(n + k) time where k is the number of inversions, making it optimal for nearly-sorted data.
Question 7: What does the 'k' represent in the time complexity O(n + k) of Counting Sort?
- Number of comparisons
- Range of input values (Correct answer)
- Number of swaps
- Stack depth
Correct answer: Range of input values
k is the range (max - min + 1) of the input values, which determines the size of the counting array.
CodeSignal Technical Assessment Sorting and Searching Algorithms 2
What is the worst-case time complexity of QuickSort when the pivot is always the smallest or largest element?