CodeSignal Technical Assessment Core Data Structures 5

Question 1

Which data structure best supports O(log n) insertion, deletion, AND lookup of ordered data?

Accepted Answer

Balanced BST (e.g., AVL or Red-Black tree)

Answer

Balanced BSTs maintain a height of O(log n) through rotations, guaranteeing logarithmic time for all three operations.

Question 2

In a max-heap, after calling extractMax(), what happens to maintain the heap property?

Accepted Answer

The last element replaces the root, then is sifted down

Answer

The last element is moved to the root and repeatedly swapped with its larger child (sift-down) until the heap property is restored.

Question 3

What is the space complexity of storing a graph with V vertices and E edges using an adjacency matrix?

Accepted Answer

O(V²)

Answer

An adjacency matrix allocates a V×V boolean or weight matrix regardless of the number of actual edges.

Question 4

Which scenario represents a use case where a stack is the natural choice?

Accepted Answer

Evaluating a mathematical expression with nested parentheses

Answer

Parenthesis matching and expression evaluation use a stack to track open brackets and pending operations in LIFO order.

Question 5

What is the time complexity of BFS (Breadth-First Search) on a graph with V vertices and E edges?

Accepted Answer

O(V + E)

Answer

BFS visits every vertex once and traverses each edge once, giving O(V + E) overall time complexity.

Codesignal Practice Test