Data Structures and Algorithms Certification — Questions and Answers

Question 1: What is the average time complexity of lookup in a hash table?

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

Correct answer: O(1)

With a good hash function and low load factor, hash table lookups are O(1) on average because the key maps directly to a bucket.

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

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

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 3: What is linear probing in the context of open addressing?

Rehashing with a secondary hash function
Jumping by a fixed prime offset on collision
Searching buckets in reverse order
On collision, scanning sequentially (index+1, +2, ...) until an empty slot is found (Correct answer)

Correct answer: On collision, scanning sequentially (index+1, +2, ...) until an empty slot is found

Linear probing resolves collisions by sequentially checking the next bucket until an empty slot is found, keeping all entries in the main array.

Question 4: In ___, the herder node serves as a sentinel.

Stacks
Binary tree (Correct answer)
Graphs
Queues

Correct answer: Binary tree

While 'herder node' is not a standard term, a 'sentinel node' is sometimes used in data structures like linked lists or trees to simplify boundary conditions. In the context of binary trees, a sentinel node might represent null children, simplifying traversal or insertion/deletion logic by always having a node to point to, even if it's a dummy.

Question 5: What is the load factor of a hash table?

The number of buckets times the number of keys
The maximum chain length in separate chaining
The ratio of stored entries to total bucket count (Correct answer)
The number of collisions divided by inserts

Correct answer: The ratio of stored entries to total bucket count

Load factor = (number of entries) / (number of buckets); a high load factor increases collision probability and degrades performance.

Question 6: Which of the following isn't an example of an internal sort?

Insertion Sort
Bubble Sort
Heap Sort
Merge Sort (Correct answer)

Correct answer: Merge Sort

Internal sorting algorithms process data entirely within the main memory of a computer. Bubble Sort, Insertion Sort, and Heap Sort are all examples of internal sorts. Merge Sort, while it can be implemented internally, is often used as an external sorting algorithm when the data to be sorted is too large to fit into main memory, requiring the use of external storage like disk drives.

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

O(log n) (Correct answer)
O(n log n)
O(√n)
O(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 8: Before moving on to the next vertex, the _________ traversal processes all of a vertex's descendants.

With First
Depth Limited
Breadth First
Depth First (Correct answer)

Correct answer: Depth First

Depth-First Search (DFS) explores as far as possible along each branch before backtracking. This means it fully processes all descendants of a vertex down one path before moving to an unvisited neighbor of the current vertex or backtracking to an ancestor.

Question 9: You need to check whether a string of brackets like "{[()]}" is balanced. Which data structure fits best?

Stack (Correct answer)
Binary heap
Queue
Hash table

Correct answer: Stack

Push opening brackets and pop to match each closing bracket, which is exactly LIFO stack behavior.

Question 10: Which algorithm finds the median of two sorted arrays in O(log(min(m,n))) time?

Merge both arrays then find middle element
Linear scan tracking count to the median position
Sort both arrays together with merge sort
Binary search on the smaller array to find the correct partition (Correct answer)

Correct answer: Binary search on the smaller array to find the correct partition

Binary searching on the partition point of the smaller array ensures that elements on the left of both partitions are the lower half, achieving O(log(min(m,n))) time.

Question 11: What is a directed acyclic graph (DAG)?

A graph with no vertices
A directed graph with no cycles (Correct answer)
A graph where every vertex has equal degree
A graph where all edges are bidirectional

Correct answer: A directed graph with no cycles

A DAG is a directed graph that contains no directed cycles, making topological sorting possible.

Question 12: Which data structure is used to implement Breadth-First Search (BFS) in a graph?

Priority Queue
Deque
Queue (Correct answer)
Stack

Correct answer: Queue

BFS uses a queue to visit nodes level by level, ensuring FIFO order of exploration.

Question 13: Inserting a new element into a binary min-heap of n elements takes how long in the worst case?

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

Correct answer: O(log n)

The new element is placed at the bottom and bubbles up at most the height of the heap, which is O(log n).

Question 14: Which traversal of a binary search tree visits nodes in ascending sorted order?

Post-order
Pre-order
Level-order
In-order (Correct answer)

Correct answer: In-order

In-order traversal visits left subtree, node, then right subtree, which yields sorted order in a BST.

Question 15: Which tree traversal visits nodes in ascending order for a Binary Search Tree?

In-order (Correct answer)
Level-order
Post-order
Pre-order

Correct answer: In-order

In-order traversal visits left subtree, root, then right subtree; for a BST this produces nodes in sorted ascending order.

Question 16: What is a sentinel (dummy) head node used for in linked list implementations?

To enable random access
To simplify edge cases by eliminating null checks at the head (Correct answer)
To speed up search operations
To store the list's length

Correct answer: To simplify edge cases by eliminating null checks at the head

A dummy head node ensures the list is never truly empty from the algorithm's perspective, eliminating special-case code for head insertions and deletions.

Question 17: What is consistent hashing and where is it commonly used?

A distributed system technique where adding/removing nodes minimally remaps keys (Correct answer)
A method to eliminate hash collisions entirely
A hash function that always produces consistent output for the same input
Hashing that maintains insertion order

Correct answer: A distributed system technique where adding/removing nodes minimally remaps keys

Consistent hashing arranges both keys and nodes on a virtual ring; adding or removing a node only remaps keys adjacent to that node, minimizing redistribution.

Question 18: What is a spanning tree of a connected graph?

A subgraph that contains all vertices and exactly V-1 edges with no cycles (Correct answer)
A path that visits every vertex exactly once
A graph where every vertex has exactly two children
A tree that spans the entire memory of the system

Correct answer: A subgraph that contains all vertices and exactly V-1 edges with no cycles

A spanning tree includes all V vertices of the graph connected by exactly V-1 edges, forming a tree with no cycles.

Question 19: In order for a binary search method to work, the array (list) must be empty

popped out of stack
in a heap
unsorted
sorted (Correct answer)

Correct answer: sorted

The binary search algorithm relies on the array being sorted to efficiently locate an element. It works by repeatedly dividing the search interval in half. If the array is unsorted, this division strategy will not guarantee finding the element or determining its absence correctly.

Question 20: What is the time complexity of finding all pairs with a given difference in an unsorted array using a hash set?

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

Correct answer: O(n)

Insert all elements into a hash set in O(n), then for each element check if (element + difference) exists in O(1) per check, giving O(n) total.

Question 21: What is the purpose of the 'partition' step in quicksort?

To eliminate duplicate values from the subarray
To split the array into two equal halves
To place the pivot in its final sorted position with smaller elements to its left and larger to its right (Correct answer)
To find the median element of the array

Correct answer: To place the pivot in its final sorted position with smaller elements to its left and larger to its right

The partition step rearranges elements around the pivot so everything left is smaller and everything right is larger, placing the pivot in its final position in O(n) time.

Question 22: What is the time complexity of binary search on a sorted array?

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

Correct answer: O(log n)

Binary search halves the search space at each step, requiring at most log₂ n comparisons to find or rule out a target.

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

Heapsort
Selection sort
Insertion sort (Correct answer)
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 24: What is the degree of a vertex in an undirected graph?

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

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 25: What is the time complexity of finding an element in a sorted rotated array using binary search?

O(n)
O(√n)
O(log n) (Correct answer)
O(n log 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 26: What is the space complexity of storing a string of length n?

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

Correct answer: O(n)

A string of length n requires O(n) space to store all its characters.

Question 27: Which searching algorithm is used to find a target in a matrix where rows and columns are sorted?

Start at top-right corner, move left if target is smaller, down if larger (Correct answer)
Linear scan of all elements
Binary search on each row independently
Flatten the matrix and binary search

Correct answer: Start at top-right corner, move left if target is smaller, down if larger

Starting at the top-right corner exploits the sorted property: moving left decreases the value, moving down increases it, achieving O(m+n) search time.

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

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

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 29: What is a threaded binary tree?

A tree where all nodes are connected in a circular manner
A tree where null pointers are replaced with pointers to in-order successor/predecessor (Correct answer)
A tree where each node stores a thread ID
A tree used for concurrent access

Correct answer: A tree where null pointers are replaced with pointers to in-order successor/predecessor

A threaded binary tree replaces null left/right pointers with pointers to in-order predecessor/successor, enabling traversal without recursion or a stack.

Question 30: What rotation operation is performed to fix a left-left imbalance in an AVL tree?

Right rotation (Correct answer)
Left rotation
Left-right double rotation
Right-left double rotation

Correct answer: Right rotation

A left-left imbalance is corrected by a single right rotation around the unbalanced node, restoring AVL balance properties.

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

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

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.

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