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

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?

Accepted Answer

Array must be sorted

Answer

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:

Accepted Answer

Linked lists allow O(1) merging without extra space

Answer

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?

Accepted Answer

O(1)

Answer

Iterative binary search uses a constant number of pointer variables regardless of input size.

Question 5

In a stable sort, what is preserved?

Accepted Answer

The relative order of equal elements

Answer

A stable sort guarantees that elements with equal keys appear in the output in the same relative order as the input.

Codesignal Practice Test