CodeSignal Technical Assessment Algorithm Design 4

Question 1

What is the time complexity of building a max-heap from an unsorted array of n elements?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(log n)

Answer

O(n²)

Question 2

Which technique is used in the Kadane's algorithm to find the maximum subarray sum?

Accepted Answer

Dynamic programming with a running max

Answer

Divide and conquer

Answer

Sorting then prefix sums

Answer

Binary search on the answer

Question 3

When does the Floyd-Warshall algorithm apply best?

Accepted Answer

All-pairs shortest paths on dense graphs

Answer

Single-source shortest paths on sparse graphs

Answer

Minimum spanning tree

Answer

Topological sorting

Question 4

What does amortized O(1) mean for a dynamic array's append operation?

Accepted Answer

The average cost per append over a sequence of operations is O(1)

Answer

Every append is guaranteed O(1)

Answer

Only the last append is O(1)

Answer

Space used is constant

Question 5

Which traversal order of a BST produces elements in sorted order?

Accepted Answer

In-order

Answer

Pre-order

Answer

Post-order

Answer

Level-order

Question 6

What problem does topological sorting solve?

Accepted Answer

Ordering tasks with dependencies (DAG)

Answer

Finding shortest paths in weighted graphs

Answer

Detecting negative cycles

Answer

Balancing a binary tree

Question 7

Which recurrence solves to O(n log n) by the Master Theorem?

Accepted Answer

T(n) = 2T(n/2) + O(n)

Answer

T(n) = T(n/2) + O(n)

Answer

T(n) = 4T(n/2) + O(n²)

Answer

T(n) = T(n-1) + O(1)