Data Structures and Algorithms Certification — Questions and Answers

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

Bubble sort
Insertion sort
Quicksort
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 2: Which graph representation is more space-efficient for sparse graphs?

Adjacency matrix
Edge matrix
Adjacency list (Correct answer)
Incidence matrix

Correct answer: Adjacency list

An adjacency list stores only the existing edges, using O(V + E) space, which is efficient when E << V².

Question 3: What is the average time complexity of quicksort?

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

Correct answer: O(n log n)

Quicksort's average case is O(n log n) because the partition step is O(n) and on average produces balanced halves, giving O(log n) levels of recursion.

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

Use the frequency map to build a sorted array in O(n)
Use the frequency map with a min-heap of size k to maintain the top k elements in O(n log k) (Correct answer)
Sort by frequency using the frequency map then scan
Store all frequencies and sort the entire map 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 5: 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 6: What is a segment tree used for?

Representing graph adjacency
Balancing a BST automatically
Answering range queries (sum, min, max) and point updates in O(log n) (Correct answer)
Storing hierarchical file structures

Correct answer: Answering range queries (sum, min, max) and point updates in O(log n)

A segment tree preprocesses an array in O(n) and supports range queries and point updates in O(log n) time.

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

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

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 8: What makes radix sort efficient for sorting integers?

It uses a divide-and-conquer strategy
It sorts integers using their binary representation with O(1) space
It sorts digit by digit using a stable sort, achieving O(d×n) time independent of comparisons (Correct answer)
It uses randomization to avoid worst-case behavior

Correct answer: It sorts digit by digit using a stable sort, achieving O(d×n) time independent of comparisons

Radix sort applies a stable counting sort to each digit position, running in O(d×n) time where d is the number of digits — faster than O(n log n) when d is small.

Question 9: What is an LRU Cache and which data structures implement it in O(1) for both get and put?

Least Recently Used cache using an array and binary search
Least frequently used cache using a min-heap
Most recently used cache using a stack
LRU cache using a doubly linked list and hash map (Correct answer)

Correct answer: LRU cache using a doubly linked list and hash map

An LRU cache combines a doubly linked list (for order tracking) and a hash map (for O(1) lookup) to achieve O(1) get and put operations.

Question 10: Which algorithm efficiently finds the kth order statistic (kth smallest element) in a set of n unsorted elements in expected O(n) time?

Heapsort extracting k times
Quickselect (partition-based selection) (Correct answer)
Binary search after sorting
Counting sort on the full range

Correct answer: Quickselect (partition-based selection)

Quickselect uses quicksort's partition step but recurses only into the side containing the kth element, achieving O(n) expected time without fully sorting.

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

O(n²)
O(n log n) (Correct answer)
O(n)
O(n log log 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 12: In a 2D array stored in row-major order, which access pattern is more cache-friendly?

Random access
Column-by-column access
Row-by-row access (Correct answer)
Diagonal access

Correct answer: Row-by-row access

Row-by-row access is cache-friendly in row-major order because consecutive row elements are stored adjacently in memory.

Question 13: How does a Bloom filter differ from a hash table?

A Bloom filter is slower but more space-efficient
A Bloom filter sorts keys during insertion
A Bloom filter uses multiple hash functions with a bit array to test membership with possible false positives but no false negatives (Correct answer)
A Bloom filter stores exact key-value pairs

Correct answer: A Bloom filter uses multiple hash functions with a bit array to test membership with possible false positives but no false negatives

A Bloom filter uses k hash functions to set bits in a bit array; it can report false positives (saying a key is present when it isn't) but never false negatives.

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

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

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 15: What is the time complexity of Dijkstra's algorithm when implemented with a binary min-heap?

O(V + E)
O((V + E) log V) (Correct answer)
O(E log E)
O(V²)

Correct answer: O((V + E) log V)

With a binary min-heap, each extract-min operation costs O(log V) and each decrease-key costs O(log V), resulting in O((V + E) log V) overall.

Question 16: What is exponential search and when is it useful?

A sort using powers of two as pivot values
A search that finds the range containing the target by doubling the index, then applies binary search; useful for unbounded or large sorted arrays (Correct answer)
A search that evaluates all elements exponentially faster than linear search
A divide and conquer search with O(2^n) complexity

Correct answer: A search that finds the range containing the target by doubling the index, then applies binary search; useful for unbounded or large sorted arrays

Exponential search finds a range [2^i, 2^(i+1)] containing the target in O(log n) steps, then binary searches that range — especially useful for unbounded sorted arrays.

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

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

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 18: How does a priority queue differ from a standard queue?

Priority queue uses a stack internally
Priority queue allows duplicate values; standard queue does not
Priority queue only supports integer elements
Elements are dequeued by priority rather than arrival order (Correct answer)

Correct answer: Elements are dequeued by priority rather than arrival order

A priority queue dequeues the element with the highest (or lowest) priority first, regardless of when it was inserted, unlike a FIFO queue.

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

Stack
Queue (Correct answer)
Priority queue
Binary search tree

Correct answer: Queue

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

Question 20: What is the main disadvantage of singly linked lists compared to arrays?

Cannot store duplicate values
No random access by index (Correct answer)
Higher insertion cost at head
Requires more CPU operations for sorting

Correct answer: No random access by index

Singly linked lists require O(n) traversal to access any element by position since there is no direct index-based access.

Question 21: Which collision resolution strategy stores multiple colliding entries in a linked list at each bucket?

Linear probing
Open addressing
Separate chaining (Correct answer)
Robin Hood hashing

Correct answer: Separate chaining

Separate chaining attaches a linked list (or other structure) to each bucket, storing all colliding keys in that list.

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

Two Sum: finding two indices that add to a target (Correct answer)
Detecting cycles in a linked list
Finding the longest increasing subsequence
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 23: What is the time complexity of binary search on a sorted array?

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

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

Jumping by a fixed prime offset on collision
Searching buckets in reverse order
Rehashing with a secondary hash function
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 25: What does the sliding window technique optimize when processing subarrays or substrings?

Reversing the array in place
Finding the median element
Avoiding nested loops by reusing previous computations (Correct answer)
Sorting the array

Correct answer: Avoiding nested loops by reusing previous computations

The sliding window technique maintains a running result as the window moves, reducing time complexity from O(n²) to O(n).

Question 26: Two-dimensional arrays are also referred to as

both A & B (Correct answer)
matrix arrays
tables arrays
none of above

Correct answer: both A & B

Two-dimensional arrays are commonly visualized and used as matrices in mathematics and computer science, representing rows and columns of data. They are also frequently referred to as tables because they organize data in a tabular format. Therefore, both 'matrix arrays' and 'tables arrays' are appropriate descriptions.

Question 27: What problem does the Floyd-Warshall algorithm solve?

All-pairs shortest paths (Correct answer)
Minimum spanning tree
Single-source shortest path with negative weights
Maximum flow in a network

Correct answer: All-pairs shortest paths

Floyd-Warshall computes shortest paths between every pair of vertices in a graph in O(V³) time using dynamic programming.

Question 28: 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 29: Which of the following isn't an example of an internal sort?

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

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 30: What is the space complexity of a recursive linked list reversal?

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

Correct answer: O(n)

Recursive reversal uses O(n) call stack space because each node generates a recursive call frame before the base case is reached.

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

To place the pivot in its final sorted position with smaller elements to its left and larger to its right (Correct answer)
To eliminate duplicate values from the subarray
To split the array into two equal halves
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 32: 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(n) space
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

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 33: How do you find the kth smallest element in a BST efficiently?

Level-order traversal and sort
Sort all elements then index
Use a max-heap of size k
In-order traversal counting nodes until the kth is reached (Correct answer)

Correct answer: In-order traversal counting nodes until the kth is reached

Since in-order traversal of a BST yields sorted order, counting nodes during traversal and stopping at the kth gives the kth smallest in O(h+k) time.

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

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
The number of buckets times the number of keys

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 35: What is topological sorting applicable to?

Any undirected graph
Directed Acyclic Graphs (DAGs) only (Correct answer)
Weighted graphs only
Complete graphs only

Correct answer: Directed Acyclic Graphs (DAGs) only

Topological sorting orders vertices so that for every directed edge u→v, u comes before v, which is only possible in a DAG.

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

Insertion sort (Correct answer)
Merge sort
Selection sort
Heapsort

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 37: Which of these alogrithmic methods attempts to find a localized optimum solution -

Divide and conquer approach
All of the above
Dynamic approach
Greedy approach (Correct answer)

Correct answer: Greedy approach

A greedy algorithm makes the locally optimal choice at each stage with the hope of finding a global optimum. It doesn't consider future consequences or backtrack, simply picking the best immediate option. This often leads to a localized optimum, which may or may not be the global optimum.

Question 38: Which of the following uses the first-in, first-out (FIFO) method?

Binary Search Tree
Stack
Queue (Correct answer)
Hash Table

Correct answer: Queue

A Queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. This means the first element added to the queue is the first one to be removed, similar to people waiting in a line. Elements are added at the rear (enqueue) and removed from the front (dequeue).

Question 39: Which of the following is NOT a valid graph traversal algorithm?

Breadth-First Search
Inorder Traversal (Correct answer)
Best-First Search
Depth-First Search

Correct answer: Inorder Traversal

Inorder traversal is specific to binary trees, not general graphs; BFS, DFS, and best-first search all work on graphs.

Question 40: Which traversal is used to create a copy of a binary tree?

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

Correct answer: Pre-order

Pre-order traversal visits the root before children, making it natural to recreate a tree by creating each node before its subtrees.

Question 41: 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)
Sorting by bit manipulation; O(n)
A GPU-accelerated parallel sort; O(n/p) with p processors

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 42: What is the main advantage of a circular queue over a linear array-based queue?

Reuses freed space at the front without shifting elements (Correct answer)
Faster enqueue time
Supports priority ordering
Eliminates the need for a size variable

Correct answer: Reuses freed space at the front without shifting elements

A circular queue wraps the rear pointer around to the front when it reaches the array end, reusing vacated front positions without element shifting.

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

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

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 44: What does it mean for a binary tree to be height-balanced?

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

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 45: What is counting sort and when should it be preferred over comparison-based sorts?

A non-comparison sort using element frequency counts; preferred when the value range k is small (Correct answer)
A sort that counts swaps to measure performance
A sort using element comparisons; always preferred
A parallel sort using multiple CPU cores

Correct answer: A non-comparison sort using element frequency counts; preferred when the value range k is small

Counting sort runs in O(n+k) time by counting element frequencies, making it faster than O(n log n) comparison sorts when k (the value range) is small relative to n.

Question 46: What is the key difference between Prim's and Kruskal's algorithms for finding a minimum spanning tree?

Prim's uses DFS, Kruskal's uses BFS
Prim's grows the tree from a starting vertex, Kruskal's adds the globally cheapest edge each time (Correct answer)
Prim's finds shortest paths, Kruskal's finds minimum cuts
Prim's works on directed graphs, Kruskal's on undirected

Correct answer: Prim's grows the tree from a starting vertex, Kruskal's adds the globally cheapest edge each time

Prim's builds the MST incrementally from a single vertex, while Kruskal's sorts all edges and greedily adds the cheapest non-cycle-forming edge.

Question 47: 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 48: What is the time complexity of insertion into a binary min-heap (underlying a priority queue)?

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

Correct answer: O(log n)

Inserting into a binary min-heap adds the element at the end and bubbles it up through at most O(log n) levels to restore the heap property.

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

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

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 50: What is an Euler path in a graph?

A path that visits every vertex exactly once
A cycle that passes through all vertices
The shortest path between two vertices
A path that traverses every edge exactly once (Correct answer)

Correct answer: A path that traverses every edge exactly once

An Euler path traverses every edge in the graph exactly once, and exists in an undirected graph when exactly 0 or 2 vertices have odd degree.

Question 51: What is the space complexity of merge sort?

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

Correct answer: O(n)

Merge sort requires O(n) auxiliary space for the temporary arrays used during the merge step.

Question 52: Before moving on to the next vertex, the _________ traversal processes all of a vertex's descendants.

Breadth First
Depth Limited
With 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 53: What is the output of evaluating the postfix expression '3 4 + 2 * 7 /'?

3.5
4
1.5
2 (Correct answer)

Correct answer: 2

Evaluate step by step: 3+4=7, 7×2=14, 14/7=2, giving a final result of 2.

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

O(n)
O(1) (Correct answer)
O(log n)
O(n log 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 55: What is the time complexity of inserting a node at the beginning of a singly linked list?

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

Correct answer: O(1)

Inserting at the head only requires updating the new node's next pointer and the head reference, both constant-time operations.

Question 56: How does Java's HashMap handle hash collisions in modern implementations?

Converts chains to balanced trees (red-black) when chain length exceeds 8 (Correct answer)
Uses only separate chaining with linked lists
Uses open addressing with quadratic probing
Rehashes immediately upon any collision

Correct answer: Converts chains to balanced trees (red-black) when chain length exceeds 8

Java 8+ HashMap starts with linked list chaining per bucket but converts a chain to a red-black tree when it exceeds 8 entries, improving worst-case lookup to O(log n).

Question 57: Which algorithm is used to find the shortest path from a single source to all other vertices in a graph with non-negative edge weights?

Floyd-Warshall
Bellman-Ford
Kruskal's
Dijkstra's (Correct answer)

Correct answer: Dijkstra's

Dijkstra's algorithm efficiently finds single-source shortest paths when all edge weights are non-negative using a greedy approach.

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

A tree that spans the entire memory of the system
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

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 59: What is the purpose of a hash set compared to a hash map?

A hash set stores only unique keys with no associated values; a hash map stores key-value pairs (Correct answer)
A hash set is ordered; a hash map is unordered
A hash set stores key-value pairs; a hash map stores only keys
A hash set uses open addressing; a hash map uses chaining

Correct answer: A hash set stores only unique keys with no associated values; a hash map stores key-value pairs

A hash set tracks membership — just unique keys — while a hash map associates each unique key with a value.

Question 60: Which property must hold for every node in a binary min-heap?

All values in its left subtree are smaller than its value
Its left child is smaller than its right child
Its value is less than or equal to its children's values (Correct answer)
It has exactly zero or two children

Correct answer: Its value is less than or equal to its children's values

The min-heap property only requires each parent to be no larger than its children, with no left-right ordering.

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

90 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