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.

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: