Data Structures and Algorithms Certification — Questions and Answers

Question 1: A max-heap is stored in an array starting at index 0. Where is the left child of the node at index i?

i + 1
i / 2
2i
2i + 1 (Correct answer)

Correct answer: 2i + 1

In a 0-indexed array heap, the left child of index i is at 2i + 1 and the right child at 2i + 2.

Question 2: What is the lower bound on comparison-based sorting algorithms?

O(n log n) (Correct answer)
O(n)
O(n log log n)
O(n²)

Correct answer: O(n log n)

Information-theoretic analysis shows that any comparison-based sort must make at least Ω(n log n) comparisons in the worst case to distinguish all n! possible orderings.

Question 3: What triggers rehashing in a hash table?

When the load factor exceeds a threshold (commonly 0.75) (Correct answer)
When a deletion creates empty slots
Any insertion operation
When a collision occurs

Correct answer: When the load factor exceeds a threshold (commonly 0.75)

Most hash table implementations rehash (resize and redistribute all entries) when the load factor exceeds a threshold like 0.75 to maintain O(1) average performance.

Question 4: Which self-balancing BST uses red-black coloring to maintain O(log n) operations?

Splay tree
AVL tree
B-tree
Red-Black tree (Correct answer)

Correct answer: Red-Black tree

Red-Black trees enforce coloring rules that guarantee the tree height stays O(log n), ensuring all operations remain O(log n).

Question 5: What is the time complexity of finding an element in a sorted rotated array using binary search?

O(n log n)
O(n)
O(log n) (Correct answer)
O(√n)

Correct answer: O(log n)

Modified binary search on a sorted rotated array identifies the sorted half at each step and determines whether the target lies within it, maintaining O(log n) complexity.

Question 6: What is bucket sort and what is its average time complexity?

A GPU-accelerated parallel sort; O(n/p) with p processors
Sorting by bit manipulation; O(n)
Sorting into fixed-size memory blocks; O(n log n)
Distributing elements into buckets, sorting each bucket, concatenating; O(n+k) average (Correct answer)

Correct answer: Distributing elements into buckets, sorting each bucket, concatenating; O(n+k) average

Bucket sort distributes n uniformly distributed elements into k buckets, sorts each small bucket with insertion sort, and concatenates them, averaging O(n+k) time.

Question 7: What does it mean for a binary tree to be height-balanced?

The tree is a complete binary tree
The height difference between left and right subtrees is at most 1 for every node (Correct answer)
Both subtrees have the same number of nodes
All leaf nodes are at the same level

Correct answer: The height difference between left and right subtrees is at most 1 for every node

A height-balanced tree (like AVL) requires that the heights of left and right subtrees differ by no more than 1 at every node, not just the root.

Question 8: Because aposterior analysis is more accurate than apriori analysis, it is

it contains the real data.
it assumes all other facets to be dynamic (Correct answer)
it assumes all other factors to be constant.
it is a result of reverse-engineering

Correct answer: it assumes all other facets to be dynamic

A posteriori analysis, also known as empirical or experimental analysis, involves running the algorithm on actual data and measuring its performance. Unlike a priori analysis, which uses theoretical calculations and assumes constant factors, a posteriori analysis accounts for real-world factors like system load, hardware, and specific input data, making its results more reflective of actual performance. Therefore, it considers other facets to be dynamic and variable.

Question 9: Why is the worst-case time complexity of hash table lookup O(n)?

Hash tables don't support lookup operations
All keys hash to the same bucket, creating a single chain of length n (Correct answer)
The table must be fully scanned on each lookup
The hash function always produces the same value

Correct answer: All keys hash to the same bucket, creating a single chain of length n

In the worst case (e.g., a poor hash function or adversarial keys), all n entries collide into one bucket, degrading lookup to O(n) list search.

Question 10: Which sorting algorithm is most efficient for nearly sorted data?

Insertion sort (Correct answer)
Selection sort
Heapsort
Merge sort

Correct answer: Insertion sort

Insertion sort performs O(n) comparisons on nearly sorted data because elements are already close to their final positions, requiring minimal shifting.

Question 11: Check that all of the statements are correct.

Swift has Type Inferencing, while Java does not. (Correct answer)
Swift has Structs, whereas Java 7 does not. (Correct answer)
Swift has enums, whereas Java does not.
Swift Classes are value types, unlike Java Classes, which are reference types.
Swift has Optional, whereas Java 7 does not. (Correct answer)

Correct answer: Swift has Type Inferencing, while Java does not.

Swift introduced Optionals to safely handle the absence of a value, preventing null pointer exceptions. Java 7 did not have a direct equivalent to Swift's Optional type; `null` was used, which is prone to NullPointerExceptions. Java 8 later introduced `java.util.Optional` to address this, but the question specifically refers to Java 7.

Question 12: What is the degree of a vertex in an undirected graph?

The number of edges incident to that vertex (Correct answer)
The shortest path from that vertex to all others
The number of vertices in the graph
The number of vertices adjacent to it minus one

Correct answer: The number of edges incident to that vertex

The degree of a vertex is the count of edges connected to it; self-loops are typically counted twice.

Question 13: What is the time complexity of AVL tree insertion including rebalancing?

O(1)
O(log n) (Correct answer)
O(n)
O(n log n)

Correct answer: O(log n)

AVL insertion follows the BST insert path in O(log n) time, and rebalancing via rotations also takes O(log n) since the tree height is O(log n).

Question 14: Which sorting algorithm has the best worst-case time complexity?

Bubble sort
Quicksort
Insertion sort
Merge sort (Correct answer)

Correct answer: Merge sort

Merge sort guarantees O(n log n) in all cases — best, average, and worst — because it always splits evenly and merges linearly.

Question 15: What is the time and space complexity of using a hash map to detect the first non-repeating character in a string?

O(n) time, O(1) space since the character set is fixed (Correct answer)
O(n²) time, O(n) space
O(n log n) time, O(n) space
O(n) time, O(n) space

Correct answer: O(n) time, O(1) space since the character set is fixed

You need two passes over the string (O(n)) and a fixed-size frequency array of at most 26 or 128 entries (O(1) space) to find the first unique character.

Question 16: Which operation is most expensive in a dynamic array when it needs to resize?

Reading an element
Checking the length
Appending when capacity is full (Correct answer)
Accessing the last element

Correct answer: Appending when capacity is full

When a dynamic array exceeds capacity, all existing elements must be copied to a new larger array, making it an O(n) operation.

Question 17: What is the average time and space complexity of heapsort?

O(n) time, O(n) space
O(n log n) time, O(n) space
O(n log n) time, O(1) space (Correct answer)
O(n²) time, O(1) space

Correct answer: O(n log n) time, O(1) space

Heapsort builds a max-heap in O(n), then performs n extractions each taking O(log n), totaling O(n log n) with O(1) extra space since it sorts in place.

Question 18: What is the time complexity of Tim sort (used in Python and Java) in the worst case?

O(n log² n)
O(n log n) (Correct answer)
O(n²)
O(n)

Correct answer: O(n log n)

Timsort is a hybrid of merge sort and insertion sort that guarantees O(n log n) worst-case time while exploiting natural runs for near-O(n) performance on partially sorted data.

Question 19: Which problem can be solved optimally using a hash map to track complement pairs?

Detecting cycles in a linked list
Finding the longest increasing subsequence
Two Sum: finding two indices that add to a target (Correct answer)
Computing the shortest path in a graph

Correct answer: Two Sum: finding two indices that add to a target

For Two Sum, store each number and its index in a hash map; for each new number, check if its complement (target - number) is already in the map in O(1).

Question 20: How does a frequency map help solve the 'top k frequent elements' problem?

Store all frequencies and sort the entire map in O(n²)
Sort by frequency using the frequency map then scan
Use the frequency map with a min-heap of size k to maintain the top k elements in O(n log k) (Correct answer)
Use the frequency map to build a sorted array in O(n)

Correct answer: Use the frequency map with a min-heap of size k to maintain the top k elements in O(n log k)

Build a frequency map in O(n), then maintain a min-heap of size k as you process frequencies; the heap always holds the top k elements, giving O(n log k) total time.

Question 21: What is the height of a complete binary tree with n nodes?

O(√n)
O(log n) (Correct answer)
O(n)
O(n log n)

Correct answer: O(log n)

A complete binary tree doubles the number of nodes at each level, so its height is floor(log₂ n), which is O(log n).

Question 22: What is the purpose of a skip list and what is its average search time complexity?

A list that skips even-indexed nodes; O(n/2)
A sorted list with binary search; O(log n) guaranteed
A probabilistic structure with multiple levels enabling O(log n) average search (Correct answer)
To skip duplicate values; O(1)

Correct answer: A probabilistic structure with multiple levels enabling O(log n) average search

A skip list uses probabilistically built express lanes at multiple levels, achieving O(log n) average search time similar to balanced BSTs.

Question 23: What does it mean for a graph to be 'strongly connected'?

The graph has no cycles
Every vertex is connected to every other vertex by a direct edge
Every vertex has the same degree
There exists a path between every pair of vertices in both directions (Correct answer)

Correct answer: There exists a path between every pair of vertices in both directions

A directed graph is strongly connected if there is a directed path from every vertex to every other vertex.

Question 24: What is the time complexity of rotating an array of n elements by k positions in place?

O(n) (Correct answer)
O(n log n)
O(k)
O(n×k)

Correct answer: O(n)

Using the three-reversal method, an array can be rotated by k positions in O(n) time with O(1) extra space.

Question 25: Which data structure does breadth-first search (BFS) of a graph rely on?

Queue (Correct answer)
Binary search tree
Stack
Priority queue

Correct answer: Queue

BFS explores vertices level by level, using a FIFO queue to process nodes in discovery order.

Question 26: The level is the point at where the model becomes executable code.

Implementation level (Correct answer)
Abstract level
Application level
All of the above

Correct answer: Implementation level

The implementation level is where the abstract data model or algorithm design is translated into concrete, executable code using a specific programming language. At this stage, data structures are defined and algorithms are written with specific syntax and semantics, making the model functional.

Question 27: What is the key difference between stable and unstable sorting algorithms?

Stable sorts require O(1) extra space
Stable sorts preserve the relative order of equal elements; unstable sorts may not (Correct answer)
Unstable sorts cannot sort strings
Stable sorts are always faster

Correct answer: Stable sorts preserve the relative order of equal elements; unstable sorts may not

A stable sort ensures that two records with equal keys appear in the same relative order in the sorted output as in the input.

Question 28: What does a deque (double-ended queue) support that a standard queue does not?

Priority-based ordering
O(1) random access
Insertion and deletion at both front and back (Correct answer)
Infinite capacity

Correct answer: Insertion and deletion at both front and back

A deque allows O(1) insertion and deletion at both ends, making it more flexible than a standard queue which only allows rear insertion and front deletion.

Question 29: Which algorithm is commonly used to find all strongly connected components in a directed graph?

Kruskal's algorithm
Dijkstra's algorithm
Kosaraju's algorithm (Correct answer)
Prim's algorithm

Correct answer: Kosaraju's algorithm

Kosaraju's algorithm uses two passes of DFS (one on the original graph and one on its transpose) to identify all strongly connected components.

Question 30: What is the diameter of a binary tree?

The longest path between any two nodes (may not pass through root) (Correct answer)
The height of the tree multiplied by 2
The number of leaf nodes
The total number of nodes

Correct answer: The longest path between any two nodes (may not pass through root)

The diameter is the length of the longest path between any two nodes in the tree, which may or may not pass through the root.

Question 31: What is double hashing in open addressing?

Storing each key in two separate buckets
Using two separate hash tables for redundancy
Using a secondary hash function to determine the probe step size on collision (Correct answer)
Hashing the key twice to increase security

Correct answer: Using a secondary hash function to determine the probe step size on collision

Double hashing uses a secondary hash function to compute the step size for probing, reducing clustering compared to linear or quadratic probing.

Data Structures and Algorithms Certification

Tests knowledge of fundamental data structures (arrays, linked lists, stacks, queues, trees, graphs, hash tables) and algorithms (sorting, searching), including time and space complexity analysis.

Questions

35 min

Time Limit

70%

To Pass

Checking for saved progress...

Exam Rules

You can skip questions and return to them later
Flag questions for review before submitting
No feedback shown until you submit the entire exam
Unanswered questions count as wrong — answer everything
10 pretest questions are mixed in and don't affect your score
Timer auto-submits when time runs out
Your progress is auto-saved every 30 seconds