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 worst-case time complexity of QuickSort when the pivot is always the smallest or largest element?
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.
Which property must an array satisfy for binary search to work correctly?
Answer: Array must be sorted
Binary search relies on the sorted order to determine which half to discard at each step.
Merge sort on a linked list is preferred over QuickSort because:
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.
What is the space complexity of the iterative version of binary search?
Answer: O(1)
Iterative binary search uses a constant number of pointer variables regardless of input size.
In a stable sort, what is preserved?
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.
Which sorting algorithm is most efficient for sorting a nearly-sorted array with only a few elements out of place?
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.
What does the 'k' represent in the time complexity O(n + k) of Counting Sort?
Answer: Range of input values
k is the range (max - min + 1) of the input values, which determines the size of the counting array.