CPP CPP Algorithms & Complexity Analysis

Question 1

What is the time complexity of std::sort in C++?

Accepted Answer

O(n log n)

Answer

std::sort uses introsort, a hybrid algorithm that guarantees O(n log n) average and worst-case time complexity.

Question 2

Which STL container provides O(1) average time for insertion and lookup?

Accepted Answer

std::unordered_map

Answer

std::unordered_map uses a hash table internally, giving O(1) average time for insertions and lookups.

Question 3

What is the call-stack space complexity of a naive recursive Fibonacci implementation?

Accepted Answer

O(n)

Answer

The call stack depth reaches at most O(n) for recursive Fibonacci, even though the number of calls is exponential.

Question 4

Which algorithm is best suited for finding the shortest path in an unweighted graph?

Accepted Answer

Breadth-first search

Answer

Breadth-first search guarantees the shortest path in an unweighted graph by exploring nodes level by level.

Question 5

What does std::lower_bound return on a sorted range?

Accepted Answer

An iterator to the first element not less than the given value

Answer

std::lower_bound returns an iterator to the first element in a sorted range that is not less than (>= ) the given value.

(CPP) C++ Programming Professional Certificate Practice Test