DSA Multiple Choice Questions (MCQs)

1. Introduction: Testing Your Intuition

While writing code on a whiteboard is the primary way FAANG companies test engineers, many initial screening rounds (like HackerRank or Codility tests) include Multiple Choice Questions (MCQs). Furthermore, conceptual questions are heavily used in System Design interviews and behavioral "Dive Deep" sessions to test if you actually understand the underlying mathematics of the data structures you are using.

This document provides a university-grade quiz covering the core theoretical principles of Data Structures and Algorithms. Each question is followed by a detailed explanation of the correct answer, helping you solidify your understanding of time complexities, space complexities, and algorithmic behaviors.

2. Arrays & Strings

Q1. In Java, what is the time complexity of deleting an element from the middle of an ArrayList?

• A) $O(1)$
• B) $O(\log N)$
• C) $O(N)$
• D) $O(N \log N)$

Answer: C. When you remove an element from the middle of an ArrayList, every subsequent element to the right must be shifted one index to the left to fill the gap. In the worst case (removing the first element), you must shift $N-1$ elements, making it an $O(N)$ operation.

Q2. Which of the following is true about Strings in Java?

• A) They are mutable and can be changed in-place.
• B) Appending characters in a loop using str += "a" takes $O(N)$ total time.
• C) They are backed by a char array (or byte array in newer versions) and are immutable.
• D) StringBuilder is thread-safe while StringBuffer is not.

Answer: C. Strings in Java are strictly immutable. Modifying a string creates a completely new String object in memory. Because of this, doing str += "a" inside a loop of size $N$ takes $O(N^2)$ time because the entire string is copied on every iteration. StringBuilder is used for $O(1)$ appends.

3. Linked Lists & Stacks

Q3. Which data structure is explicitly used by the operating system to manage function calls and recursion?

• A) Queue
• B) Stack
• C) Heap
• D) Graph

Answer: B. The Call Stack is a LIFO (Last-In-First-Out) data structure. When a function calls another function, the current state is pushed onto the stack. When the nested function finishes, it is popped off the stack, and execution resumes. This is why infinite recursion causes a StackOverflowError.

Q4. You need to implement a Queue using two Stacks. What is the amortized time complexity of the dequeue operation?

• A) $O(1)$
• B) $O(\log N)$
• C) $O(N)$
• D) $O(N^2)$

Answer: A. To dequeue, you pop from Stack2. If Stack2 is empty, you pop everything from Stack1 and push it into Stack2 (which takes $O(N)$ time). However, because those $N$ elements are now in Stack2, the next $N-1$ dequeue operations will take strictly $O(1)$ time. Averaged out over all operations, the amortized time is $O(1)$.

4. Trees & Graphs

Q5. What is the maximum number of nodes in a perfectly balanced binary tree of height $H$? (Assuming a single root node has height 0).

• A) $2^H$
• B) $2^{H+1} - 1$
• C) $2^H - 1$
• D) $H^2$

Answer: B. Level 0 has $2^0=1$ node. Level 1 has $2^1=2$ nodes. Level 2 has $2^2=4$ nodes. The sum of the geometric series $1 + 2 + 4 + \dots + 2^H$ is exactly $2^{H+1} - 1$.

Q6. Which algorithm is best for finding the shortest path between a starting node and a target node in an UNWEIGHTED graph?

• A) Depth-First Search (DFS)
• B) Dijkstra's Algorithm
• C) Breadth-First Search (BFS)
• D) Kruskal's Algorithm

Answer: C. BFS expands outward level-by-level concentrically. The moment BFS discovers the target node, it is mathematically guaranteed to be the shortest path in an unweighted graph. While Dijkstra's would also work, it uses a Priority Queue which adds an unnecessary $O(\log N)$ overhead compared to BFS's $O(1)$ standard Queue.

5. Sorting & Searching

Q7. Which sorting algorithm is NOT stable by default?

• A) Merge Sort
• B) Insertion Sort
• C) Quick Sort
• D) Bubble Sort

Answer: C. A stable sort maintains the relative order of items with equal keys. Quick Sort's partitioning phase swaps elements across vast distances based on the pivot, easily destroying the original relative order of duplicate elements.

Q8. What is the worst-case time complexity of standard Quick Sort?

• A) $O(N \log N)$
• B) $O(N^2)$
• C) $O(N)$
• D) $O(N!)$

Answer: B. If you pick the last element as the pivot every time, and the array is already sorted (e.g., 1, 2, 3, 4, 5), the partition step doesn't divide the array in half. It divides it into N-1 elements and 0 elements. This degrades the recursion tree from a depth of $\log N$ to a depth of $N$, resulting in $O(N^2)$ time. (This is fixed by choosing a random pivot).

6. Hashing & Heaps

Q9. In a Java HashMap, what happens when two distinct keys produce the exact same Hash Code?

• A) The program throws a HashCollisionException.
• B) The older value is overwritten by the new value.
• C) Both keys are stored in a Linked List (or Tree) at that specific hash bucket.
• D) The HashMap automatically resizes itself to avoid the collision.

Answer: C. This is called a Hash Collision. Java resolves this using "Separate Chaining". Multiple entries map to the same bucket and are stored as a Linked List. In Java 8+, if the chain grows beyond 8 elements, the LinkedList transforms into a Red-Black Tree to optimize search time from $O(N)$ to $O(\log N)$.

Q10. How long does it take to find the Maximum element in a Min-Heap of size N?

• A) $O(1)$
• B) $O(\log N)$
• C) $O(N)$
• D) $O(N \log N)$

Answer: C. A Min-Heap strictly guarantees that the minimum element is at the root ($O(1)$). However, it provides zero guarantees about the order of the leaves at the bottom of the tree. The maximum element could be literally any of the $N/2$ leaf nodes. Therefore, you must scan all the leaves, resulting in an $O(N)$ linear search.

7. Dynamic Programming & Advanced Algorithms

Q11. What mathematical property MUST a problem have to be solvable by Dynamic Programming?

• A) It must be a graph traversal.
• B) It must have Optimal Substructure and Overlapping Subproblems.
• C) It must require a 2D Matrix.
• D) It must be solvable using a Greedy choice at each step.

Answer: B. If a problem doesn't have Overlapping Subproblems (e.g., Merge Sort), you use Divide and Conquer. If it has Overlapping Subproblems but the subproblem solutions don't build the optimal global solution (lacks Optimal Substructure), DP will yield incorrect answers.

Q12. What is the time complexity of building a Segment Tree from an array of size N?

• A) $O(\log N)$
• B) $O(N)$
• C) $O(N \log N)$
• D) $O(N^2)$

Answer: B. While querying or updating a Segment Tree takes $O(\log N)$ time, the initial construction of the tree visits every node in the tree exactly once. A segment tree for $N$ elements has roughly $2N$ nodes. Therefore, the build time is strictly $O(N)$.

8. Summary & Next Steps

If you scored 10-12: Excellent. You have a university-level grasp of data structures and are ready for FAANG interviews. If you scored 6-9: Good. You understand the basics but need to review edge cases, specifically regarding Heaps, HashMaps, and Sorting stability. If you scored 0-5: Review Needed. Do not jump into coding LeetCode problems yet. Re-read the fundamentals of Big-O notation and basic data structure implementations to build a solid theoretical foundation.

Advanced Code Implementations

// Example: Binary Search implementation to test MCQ concepts
public class BinarySearch {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

// Example: Quick Sort partition logic often tested in MCQs
public class QuickSort {
    public int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

Expanded Interview Q&A

Q1: In a binary search, why use left + (right - left) / 2 instead of (left + right) / 2?

Answer: To prevent integer overflow when both left and right are large numbers near the maximum integer limit.

Q2: Which sorting algorithm is stable by default?

Answer: Merge Sort and Insertion Sort are stable. Quick Sort is typically unstable.

Q3: What is the worst-case time complexity of Quick Sort?

Answer: O(N^2), which happens when the array is already sorted and the pivot chosen is the largest or smallest element.

Q4: What data structure is used to implement a Priority Queue?

Answer: A Binary Heap (Min-Heap or Max-Heap).

Q5: How do you detect a cycle in a linked list?

Answer: Floyd's Cycle-Finding Algorithm (Tortoise and Hare), using a slow pointer moving one step and a fast pointer moving two steps.