Data Structures Sorting and Searching Algorithms 2 — Questions and Answers
Question 1: What is counting sort and when should it be preferred over comparison-based sorts?
- A sort using element comparisons; always preferred
- A non-comparison sort using element frequency counts; preferred when the value range k is small (Correct answer)
- A sort that counts swaps to measure performance
- A parallel sort using multiple CPU cores
Correct answer: A non-comparison sort using element frequency counts; preferred when the value range k is small
Counting sort runs in O(n+k) time by counting element frequencies, making it faster than O(n log n) comparison sorts when k (the value range) is small relative to n.
Question 2: What is the average time and space complexity of heapsort?
- O(n log n) time, O(n) space
- O(n log n) time, O(1) space (Correct answer)
- O(n²) time, O(1) space
- O(n) time, O(n) space
Correct answer: O(n log n) time, O(1) space
Heapsort builds a max-heap in O(n), then performs n extractions each taking O(log n), totaling O(n log n) with O(1) extra space since it sorts in place.
Question 3: Which searching algorithm is used to find a target in a matrix where rows and columns are sorted?
- Linear scan of all elements
- Binary search on each row independently
- Start at top-right corner, move left if target is smaller, down if larger (Correct answer)
- Flatten the matrix and binary search
Correct answer: Start at top-right corner, move left if target is smaller, down if larger
Starting at the top-right corner exploits the sorted property: moving left decreases the value, moving down increases it, achieving O(m+n) search time.
Question 4: What makes radix sort efficient for sorting integers?
- It uses a divide-and-conquer strategy
- It sorts digit by digit using a stable sort, achieving O(d×n) time independent of comparisons (Correct answer)
- It sorts integers using their binary representation with O(1) space
- It uses randomization to avoid worst-case behavior
Correct answer: It sorts digit by digit using a stable sort, achieving O(d×n) time independent of comparisons
Radix sort applies a stable counting sort to each digit position, running in O(d×n) time where d is the number of digits — faster than O(n log n) when d is small.
Question 5: What is the time complexity of finding an element in a sorted rotated array using binary search?
- O(n)
- O(log n) (Correct answer)
- O(n log n)
- O(√n)
Correct answer: O(log n)
Modified binary search on a sorted rotated array identifies the sorted half at each step and determines whether the target lies within it, maintaining O(log n) complexity.
Question 6: Which algorithm finds the median of two sorted arrays in O(log(min(m,n))) time?
- Merge both arrays then find middle element
- Binary search on the smaller array to find the correct partition (Correct answer)
- Linear scan tracking count to the median position
- Sort both arrays together with merge sort
Correct answer: Binary search on the smaller array to find the correct partition
Binary searching on the partition point of the smaller array ensures that elements on the left of both partitions are the lower half, achieving O(log(min(m,n))) time.
Data Structures Sorting and Searching Algorithms 2
What is counting sort and when should it be preferred over comparison-based sorts?