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

Bottom-up heap construction runs in O(n) because lower levels do less work, and the sum telescopes to linear time.

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

Kadane's keeps a running maximum ending at each index, resetting to 0 when it goes negative, achieving O(n) time.

Question 3

When does the Floyd-Warshall algorithm apply best?

Accepted Answer

All-pairs shortest paths on dense graphs

Answer

Floyd-Warshall computes all-pairs shortest paths in O(V³) and is efficient when the graph is dense (E ≈ V²).

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

Occasional O(n) resizing is spread across n appends, making the amortized cost per operation O(1) on average.

Question 5

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

Accepted Answer

In-order

Answer

In-order traversal (left → root → right) of a BST visits nodes in non-decreasing key order.

Codesignal Practice Test