CodeSignal Technical Assessment Core Data Structures 3 — Questions and Answers
Question 1: What is the amortized time complexity of appending to a dynamic array (e.g., Python list or Java ArrayList)?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n²)
Correct answer: O(1)
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?
- O(V²)
- O(V + E) (Correct answer)
- O(E²)
- O(V × E)
Correct answer: O(V + E)
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?
- Pre-order
- Post-order
- Level-order
- In-order (Correct answer)
Correct answer: In-order
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?
- Faster random access by index
- Efficient insertion and deletion at both ends (Correct answer)
- Automatic sorting of elements
- O(1) search by value
Correct answer: Efficient insertion and deletion at both ends
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?
- Min-heap
- Two stacks (Correct answer)
- Hash map
- Circular queue
Correct answer: Two stacks
Two stacks (one for back history, one for forward history) naturally model pushing/popping pages visited.
Question 6: What is a key difference between a tree and a graph?
- A tree can have cycles; a graph cannot
- A tree is a connected acyclic graph; a graph may have cycles and disconnected components (Correct answer)
- A graph always has a root node; a tree does not
- Trees store only integers; graphs store any data
Correct answer: A tree is a connected acyclic graph; a graph may have cycles and disconnected components
A tree is a special case of a graph that is connected, undirected (structurally), and contains no cycles.
Question 7: Given a stack, what is the result of performing: push(1), push(2), push(3), pop(), peek()?
- 1
- 3
- 2 (Correct answer)
- Empty stack error
Correct answer: 2
After pushing 1, 2, 3 the top is 3; pop() removes 3, leaving 2 on top; peek() returns 2 without removing it.
CodeSignal Technical Assessment Core Data Structures 3
What is the amortized time complexity of appending to a dynamic array (e.g., Python list or Java ArrayList)?