CodeSignal Technical Assessment Sorting and Searching Algorithms 3

Question 1

Which algorithm is used internally by most standard library sort implementations (e.g., Python's sorted())?

Accepted Answer

Timsort

Answer

Timsort, a hybrid of merge sort and insertion sort, is used in Python and Java because it performs well on real-world data.

Question 2

What is the time complexity of finding the k-th smallest element using a min-heap of size n?

Accepted Answer

O(k log n)

Answer

Building the heap is O(n), then extracting the minimum k times costs O(k log n) total.

Question 3

In the context of searching, what is an interpolation search and when does it outperform binary search?

Accepted Answer

It searches by value interpolation; O(log log n) on uniformly distributed data

Answer

Interpolation search estimates the probe position based on value distribution, achieving O(log log n) average case for uniform distributions.

Question 4

What is the best-case time complexity of Bubble Sort?

Accepted Answer

O(n)

Answer

With an early-termination flag, Bubble Sort detects a fully sorted array in a single pass, giving O(n) best case.

Question 5

Which of the following sorting algorithms is NOT comparison-based?

Accepted Answer

Radix Sort

Answer

Radix Sort distributes elements into buckets by digit, never comparing elements directly, so it bypasses the O(n log n) lower bound.

Codesignal Practice Test