Data Structures Sorting and Searching Algorithms 2

Question 1

What is counting sort and when should it be preferred over comparison-based sorts?

Accepted Answer

A non-comparison sort using element frequency counts; preferred when the value range k is small

Answer

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?

Accepted Answer

O(n log n) time, O(1) space

Answer

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?

Accepted Answer

Start at top-right corner, move left if target is smaller, down if larger

Answer

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?

Accepted Answer

It sorts digit by digit using a stable sort, achieving O(d×n) time independent of comparisons

Answer

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?

Accepted Answer

O(log n)

Answer

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.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Sorting and Searching Algorithms 2