CodeSignal Technical Assessment Algorithm Design 2

Question 1

Which algorithmic technique solves the 0/1 Knapsack problem optimally?

Accepted Answer

Dynamic programming

Answer

Dynamic programming solves 0/1 Knapsack in O(n·W) time by building a table of optimal subproblem solutions.

Question 2

What is the worst-case time complexity of quicksort?

Accepted Answer

O(n²)

Answer

Quicksort degrades to O(n²) when the pivot is always the smallest or largest element (e.g., sorted input with naive pivot).

Question 3

In Dijkstra's algorithm, which data structure gives the best practical performance?

Accepted Answer

Min-heap (priority queue)

Answer

A min-heap reduces the extract-minimum operation to O(log n), giving overall O((V + E) log V) complexity.

Question 4

Which sorting algorithm is stable and has O(n log n) worst-case time?

Accepted Answer

Merge sort

Answer

Merge sort is stable (preserves relative order of equal elements) and guarantees O(n log n) in all cases.

Question 5

What does memoization primarily optimize?

Accepted Answer

Repeated computation of identical subproblems

Answer

Memoization caches results of subproblems so each unique input is computed only once, converting exponential recursion to polynomial time.

Codesignal Practice Test