Data Structures and Algorithms Interview Questions (DSA MCQs)

Question 1

Which data structure follows Last In, First Out (LIFO)?

Accepted Answer

Stack. The last item pushed onto a stack is the first one popped.

Question 2

Which data structure follows First In, First Out (FIFO)?

Accepted Answer

Queue. A queue serves items in the order they arrive.

Question 3

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

Accepted Answer

O(log n). Each step halves the search range.

Question 4

What is the worst-case time complexity of quicksort?

Accepted Answer

O(n²). With bad pivots (e.g. already sorted input and first-element pivot) it degrades to O(n²). Average is O(n log n).

Question 5

Which sorting algorithm is guaranteed O(n log n) in the worst case?

Accepted Answer

Merge sort. Merge sort always splits in half and merges in linear time.

Question 6

Which traversal of a binary search tree gives the values in sorted order?

Accepted Answer

In-order. In-order visits left subtree, node, right subtree.

Question 7

What is the average time to look up a key in a hash table?

Accepted Answer

O(1). Hashing jumps straight to the bucket; collisions make the worst case O(n).

Question 8

Which algorithm finds the shortest path in a graph with non-negative edge weights?

Accepted Answer

Dijkstra's algorithm. Dijkstra greedily expands the closest unvisited vertex. Kruskal finds a minimum spanning tree, not shortest paths.

Question 9

Breadth-first search (BFS) typically uses which data structure?

Accepted Answer

Queue. BFS explores level by level, processing vertices in the order they were discovered.

Question 10

Depth-first search (DFS) can be implemented with recursion or which data structure?

Accepted Answer

Stack. Recursion uses the call stack; an explicit stack works the same way.

Question 11

What is the maximum number of nodes in a binary tree of height h (root at height 0)?

Accepted Answer

2^(h+1) − 1. Each level doubles: 1 + 2 + 4 + … + 2^h = 2^(h+1) − 1.

Question 12

Inserting at the beginning of a singly linked list takes:

Accepted Answer

O(1). Just point the new node at the old head.

Question 13

Accessing the i-th element of an array takes:

Accepted Answer

O(1). Arrays use contiguous memory, so the address is computed directly.

Question 14

Which data structure is best for implementing a priority queue?

Accepted Answer

Heap. A binary heap gives O(log n) insert and extract-min/max.

Question 15

What does dynamic programming rely on?

Accepted Answer

Overlapping subproblems and optimal substructure. DP stores answers to repeated subproblems instead of recomputing them.

Question 16

Which technique is used in the 'two-sum on a sorted array' O(n) solution?

Accepted Answer

Two pointers. Move the left pointer up when the sum is too small and the right pointer down when too big.

Question 17

What is the space complexity of merge sort on an array?

Accepted Answer

O(n). Merging needs a temporary array of size n.

Question 18

A graph with V vertices stored as an adjacency matrix needs how much space?

Accepted Answer

O(V²). A V × V matrix. Adjacency lists need O(V + E).

Question 19

Which problem is typically solved with backtracking?

Accepted Answer

N-Queens. Backtracking tries choices and undoes them when they lead to a dead end.

Question 20

Detecting a cycle in a linked list in O(1) extra space uses:

Accepted Answer

Floyd's slow and fast pointers. If there's a cycle, the fast pointer eventually meets the slow one. A hash set works but uses O(n) space.

Question 21

What is the time complexity of building a heap from n elements (heapify)?

Accepted Answer

O(n). Bottom-up heapify is O(n) because most nodes are near the leaves.

Question 22

Which of these is a stable sorting algorithm?

Accepted Answer

Merge sort. Stable sorts keep equal elements in their original order.

Question 23

A balanced binary search tree (like AVL) guarantees search in:

Accepted Answer

O(log n). Balancing keeps the height about log n.

Question 24

Which data structure is used to check balanced parentheses?

Accepted Answer

Stack. Push openers, pop and compare on closers.

Question 25

Kadane's algorithm solves which problem?

Accepted Answer

Maximum subarray sum. It tracks the best sum ending at each position in O(n).

Question 26

What is a 'trie' mainly used for?

Accepted Answer

Prefix searches on strings. Tries store strings character by character, making prefix lookups fast (autocomplete).

Question 27

Topological sort applies to which kind of graph?

Accepted Answer

Directed acyclic graph (DAG). It orders tasks so every dependency comes before the task that needs it.

Question 28

Which algorithm builds a minimum spanning tree?

Accepted Answer

Kruskal's algorithm. Kruskal (and Prim) find the cheapest set of edges connecting all vertices.

Question 29

The 'sliding window' technique is most useful for:

Accepted Answer

Problems on contiguous subarrays or substrings. Expand and shrink a window instead of re-checking every subarray.

Question 30

What is the time complexity of inserting into a Python list at index 0?

Accepted Answer

O(n). Every existing element shifts right. Use collections.deque for O(1) appends on both ends.

Question 31

Memoization means:

Accepted Answer

Caching function results for inputs already computed. It turns exponential recursion like naive Fibonacci into linear time.

Question 32

In a min-heap, the smallest element is always:

Accepted Answer

At the root. Every parent is ≤ its children, so the minimum sits at the top.

Question 33

How many edges does a tree with n nodes have?

Accepted Answer

n − 1. A tree is connected with no cycles, which needs exactly n − 1 edges.

Question 34

Which search works on unsorted data?

Accepted Answer

Linear search. Without order, you have to check elements one by one.

Question 35

A recursive function without a base case will cause:

Accepted Answer

Stack overflow (RecursionError in Python). Each call adds a stack frame until memory runs out.

Question 36

Which data structure follows Last In, First Out (LIFO)?

Accepted Answer

Stack. The last item pushed is the first one popped.

Question 37

Which data structure follows First In, First Out (FIFO)?

Accepted Answer

Queue. Items leave in the order they arrived, like a ticket counter line.

Question 38

Which data structure is best for checking balanced brackets?

Accepted Answer

Stack. Push opening brackets and pop on closing ones.

Question 39

What is a circular queue used for?

Accepted Answer

Reusing empty slots at the front of a fixed array. The rear wraps around to index 0 when space is free.

Question 40

In a singly linked list, what does each node store?

Accepted Answer

Data and a pointer to the next node. A doubly linked list also stores a pointer to the previous node.

Question 41

What is the main advantage of a linked list over an array?

Accepted Answer

Fast insertion and deletion without shifting elements. Arrays give O(1) indexing; linked lists give O(1) insert/delete once you have the node.

Question 42

Which technique detects a cycle in a linked list using O(1) extra space?

Accepted Answer

Floyd's slow and fast pointers. If the fast pointer ever meets the slow one, there is a cycle.

Question 43

How do you find the middle of a linked list in one pass?

Accepted Answer

Move one pointer by 1 and another by 2; when the fast one ends, the slow one is in the middle. The slow/fast pointer technique.

Question 44

In a binary search tree, where are values smaller than the root stored?

Accepted Answer

In the left subtree. Left subtree < node < right subtree.

Question 45

Which traversal of a binary search tree gives the values in sorted order?

Accepted Answer

Inorder. Inorder visits left, node, right.

Question 46

Which traversal visits a tree level by level?

Accepted Answer

Breadth-first (level order). It uses a queue.

Question 47

What is the maximum number of nodes in a binary tree of height h (root at height 1)?

Accepted Answer

2^h − 1. A full tree has 1 + 2 + 4 + … + 2^(h−1) nodes.

Question 48

What is the height of a balanced binary tree with n nodes?

Accepted Answer

About log₂ n. Each level doubles the number of nodes.

Question 49

What happens to BST search time if the tree becomes a straight line (skewed)?

Accepted Answer

It becomes O(n). Self-balancing trees like AVL and red-black trees prevent this.

Question 50

Which property does every node satisfy in a max-heap?

Accepted Answer

Each parent is greater than or equal to its children. So the maximum is always at the root.

Question 51

What is the time to insert into a binary heap of n elements?

Accepted Answer

O(log n). The new element sifts up at most the height of the heap.

Question 52

Which data structure is used to implement a priority queue efficiently?

Accepted Answer

Heap. Heaps give O(log n) insert and remove-top.

Question 53

What is a hash collision?

Accepted Answer

Two keys mapping to the same bucket. Handled with chaining (lists in buckets) or open addressing (probing).

Question 54

Which collision-handling method stores colliding keys in a list per bucket?

Accepted Answer

Separate chaining. Probing methods look for another empty slot instead.

Question 55

What is the load factor of a hash table?

Accepted Answer

Number of entries divided by number of buckets. When it gets too high, tables resize (rehash) to stay fast.

Question 56

Which graph traversal uses a queue?

Accepted Answer

Breadth-first search (BFS). BFS explores neighbours level by level.

Question 57

Which graph traversal is naturally written with recursion or a stack?

Accepted Answer

Depth-first search (DFS). DFS goes as deep as possible before backtracking.

Question 58

Which algorithm finds the shortest path in an unweighted graph?

Accepted Answer

BFS. BFS reaches nodes in order of distance (number of edges).

Question 59

Which algorithm finds shortest paths from one source when edge weights are non-negative?

Accepted Answer

Dijkstra's algorithm. Bellman-Ford handles negative weights.

Question 60

Which algorithm can handle negative edge weights and detect negative cycles?

Accepted Answer

Bellman-Ford. It relaxes all edges V − 1 times.

Question 61

What does a minimum spanning tree connect?

Accepted Answer

All vertices with the smallest total edge weight and no cycles. Prim's and Kruskal's algorithms build MSTs.

Question 62

Kruskal's algorithm picks edges in which order?

Accepted Answer

Increasing order of weight. It skips edges that would form a cycle (using union-find).

Question 63

Topological sort is possible only for which graphs?

Accepted Answer

Directed acyclic graphs (DAGs). Used for task scheduling and course prerequisites.

Question 64

How is a graph with V vertices stored in an adjacency matrix?

Accepted Answer

A V × V table where cell [i][j] marks an edge. Matrices use O(V²) space; adjacency lists use O(V + E).

Data Structures and Algorithms Interview Questions (DSA MCQs)

Q1. Which data structure follows Last In, First Out (LIFO)?

Q2. Which data structure follows First In, First Out (FIFO)?

Q3. What is the time complexity of binary search on a sorted array?

Q4. What is the worst-case time complexity of quicksort?

Q5. Which sorting algorithm is guaranteed O(n log n) in the worst case?

Q6. Which traversal of a binary search tree gives the values in sorted order?

Q7. What is the average time to look up a key in a hash table?

Q8. Which algorithm finds the shortest path in a graph with non-negative edge weights?

Q9. Breadth-first search (BFS) typically uses which data structure?

Q10. Depth-first search (DFS) can be implemented with recursion or which data structure?

Q11. What is the maximum number of nodes in a binary tree of height h (root at height 0)?

Q12. Inserting at the beginning of a singly linked list takes:

Q13. Accessing the i-th element of an array takes:

Q14. Which data structure is best for implementing a priority queue?

Q15. What does dynamic programming rely on?

Q16. Which technique is used in the 'two-sum on a sorted array' O(n) solution?

Q17. What is the space complexity of merge sort on an array?

Q18. A graph with V vertices stored as an adjacency matrix needs how much space?

Q19. Which problem is typically solved with backtracking?

Q20. Detecting a cycle in a linked list in O(1) extra space uses:

Q21. What is the time complexity of building a heap from n elements (heapify)?

Q22. Which of these is a stable sorting algorithm?

Q23. A balanced binary search tree (like AVL) guarantees search in:

Q24. Which data structure is used to check balanced parentheses?

Q25. Kadane's algorithm solves which problem?

Q26. What is a 'trie' mainly used for?

Q27. Topological sort applies to which kind of graph?

Q28. Which algorithm builds a minimum spanning tree?

Q29. The 'sliding window' technique is most useful for:

Q30. What is the time complexity of inserting into a Python list at index 0?

Q31. Memoization means:

Q32. In a min-heap, the smallest element is always:

Q33. How many edges does a tree with n nodes have?

Q34. Which search works on unsorted data?

Q35. A recursive function without a base case will cause:

Q36. Which data structure follows Last In, First Out (LIFO)?

Q37. Which data structure follows First In, First Out (FIFO)?

Q38. Which data structure is best for checking balanced brackets?

Q39. What is a circular queue used for?

Q40. In a singly linked list, what does each node store?

Q41. What is the main advantage of a linked list over an array?

Q42. Which technique detects a cycle in a linked list using O(1) extra space?

Q43. How do you find the middle of a linked list in one pass?

Q44. In a binary search tree, where are values smaller than the root stored?

Q45. Which traversal of a binary search tree gives the values in sorted order?

Q46. Which traversal visits a tree level by level?

Q47. What is the maximum number of nodes in a binary tree of height h (root at height 1)?

Q48. What is the height of a balanced binary tree with n nodes?

Q49. What happens to BST search time if the tree becomes a straight line (skewed)?

Q50. Which property does every node satisfy in a max-heap?

Q51. What is the time to insert into a binary heap of n elements?

Q52. Which data structure is used to implement a priority queue efficiently?

Q53. What is a hash collision?

Q54. Which collision-handling method stores colliding keys in a list per bucket?

Q55. What is the load factor of a hash table?

Q56. Which graph traversal uses a queue?

Q57. Which graph traversal is naturally written with recursion or a stack?

Q58. Which algorithm finds the shortest path in an unweighted graph?

Q59. Which algorithm finds shortest paths from one source when edge weights are non-negative?

Q60. Which algorithm can handle negative edge weights and detect negative cycles?

Q61. What does a minimum spanning tree connect?

Q62. Kruskal's algorithm picks edges in which order?

Q63. Topological sort is possible only for which graphs?

Q64. How is a graph with V vertices stored in an adjacency matrix?

Q65. Which is better for a sparse graph with few edges?

Q66. Which sorting algorithm is stable and always O(n log n)?

Q67. What is the worst-case time of quick sort?

Q68. Which sorting algorithm works best on an almost-sorted array?

Q69. Which sort repeatedly selects the minimum element and swaps it to the front?

Q70. Counting sort is efficient when:

Q71. What does 'in-place' sorting mean?

Q72. Binary search requires the array to be:

Q73. What is dynamic programming?

Q74. Which problem is a classic example of dynamic programming?

Q75. What is a greedy algorithm?

Q76. Which problem is solved correctly by a greedy approach?

Q77. What is backtracking?

Q78. What does the sliding window technique help with?

Q79. Which technique solves 'pair with given sum' in a sorted array in O(n)?