CodeSignal Technical Assessment Core Data Structures 3

Question 1

What is the amortized time complexity of appending to a dynamic array (e.g., Python list or Java ArrayList)?

Accepted Answer

O(1)

Answer

Although occasional resizing is O(n), doubling the capacity each time makes the amortized cost of each append O(1).

Question 2

In a graph represented as an adjacency list, what is the space complexity for a graph with V vertices and E edges?

Accepted Answer

O(V + E)

Answer

An adjacency list stores one entry per vertex and one entry per directed edge, totaling O(V + E) space.

Question 3

Which traversal of a Binary Search Tree visits nodes in ascending sorted order?

Accepted Answer

In-order

Answer

In-order traversal (left → root → right) visits BST nodes from smallest to largest.

Question 4

What is the main advantage of using a deque (double-ended queue) over a standard queue?

Accepted Answer

Efficient insertion and deletion at both ends

Answer

A deque supports O(1) push and pop at both the front and back, unlike a queue which only allows one end per operation.

Question 5

Which data structure is most suitable for implementing a browser's back/forward navigation history?

Accepted Answer

Two stacks

Answer

Two stacks (one for back history, one for forward history) naturally model pushing/popping pages visited.

Codesignal Practice Test