CodeSignal Technical Assessment Sorting and Searching Algorithms 2

Question 1

What is the worst-case time complexity of QuickSort when the pivot is always the smallest or largest element?

Accepted Answer

O(n²)

Answer

O(n log n)

Answer

O(n)

Answer

O(log n)

Question 2

Which property must an array satisfy for binary search to work correctly?

Accepted Answer

Array must be sorted

Answer

Elements must be unique

Answer

Array length must be a power of 2

Answer

Elements must be integers

Question 3

Merge sort on a linked list is preferred over QuickSort because:

Accepted Answer

Linked lists allow O(1) merging without extra space

Answer

Merge sort uses less memory on linked lists

Answer

QuickSort cannot be implemented on linked lists

Answer

Merge sort is always faster

Question 4

What is the space complexity of the iterative version of binary search?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n log n)

Question 5

In a stable sort, what is preserved?

Accepted Answer

The relative order of equal elements

Answer

The absolute positions of all elements

Answer

The sorted order is achieved in fewer swaps

Answer

Only unique elements are kept

Question 6

Which sorting algorithm is most efficient for sorting a nearly-sorted array with only a few elements out of place?

Accepted Answer

Insertion Sort

Answer

Merge Sort

Answer

Heap Sort

Answer

Shell Sort

Question 7

What does the 'k' represent in the time complexity O(n + k) of Counting Sort?

Accepted Answer

Range of input values

Answer

Number of comparisons

Answer

Number of swaps

Answer

Stack depth