pencils ready ✎

Data Structures & Algorithms MCQs multiple-choice questions with answers & explanations

All 27 Data Structures & Algorithms quiz questions on one page. Pick an answer in your head, then open Show answer to check it and read why. Want a score and a timer? Take them as a quiz instead.

Written by Aditya MishraTechnical Lead, BNP Paribas

Official reference: MIT 6.006 Introduction to Algorithms

✎ Take the Data Structures & Algorithms quiz 57 Data Structures & Algorithms interview questions →

1.
What is the time complexity of f(n)?
easy
```
def f(n):
    count = 0
    for i in range(n):
        j = 1
        while j < n:
            j *= 2
            count += 1
    return count
```
1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(n² log n)
Show answer
Answer: B (O(n log n))
The inner loop doubles j until it reaches n, so it runs about log₂ n times. It runs once for each of the n outer iterations, giving O(n log n). It would be O(n²) only if j increased by a constant step.
try it in the quiz →
2.
What is the time complexity of this loop?
easy
```
total = 0
for i in range(n):
    for j in range(i, n):
        total += 1
```
1. AO(n log n)
2. BO(n)
3. CO(n²)
4. DO(2ⁿ)
Show answer
Answer: C (O(n²))
The inner loop runs n, then n - 1, down to 1 times, which sums to n(n + 1) / 2. Dropping the constant factor leaves O(n²). Starting the inner loop at i halves the work but does not change the growth rate.
try it in the quiz →
3.
What is the time complexity of g(n)?
hard
```
def g(n):
    i = n
    while i > 0:
        for _ in range(i):
            pass            # O(1) work
        i //= 2
```
1. AO(n log n)
2. BO(log n)
3. CO(n²)
4. DO(n)
Show answer
Answer: D (O(n))
The outer loop runs log n times, but the inner work shrinks each time: n + n/2 + n/4 + ..., a geometric series below 2n. So the total is O(n), not O(n log n). Multiplying the iteration counts only works when the inner cost is the same on every pass.
try it in the quiz →
4.
A dynamic array doubles its capacity whenever it is full. What is the amortized cost of one append?
easy
1. AO(1)
2. BO(log n)
3. CO(n)
4. DO(n log n)
Show answer
Answer: A (O(1))
A resize copies all elements, but because capacity doubles, the copies over n appends total less than 2n. Spread across all appends, each costs O(1) amortized. A single append that triggers a resize is still O(n).
try it in the quiz →
5.
What is the worst-case auxiliary space of this function on a binary tree with n nodes?
mid
```
def tree_sum(node):
    if node is None:
        return 0
    return node.val + tree_sum(node.left) + tree_sum(node.right)
```
1. AO(log n)
2. BO(n)
3. CO(1)
4. DO(n log n)
Show answer
Answer: B (O(n))
No data structure is allocated, but each active call holds a stack frame, so space equals the maximum recursion depth. A skewed tree (a chain) has depth n, giving O(n). O(log n) holds only for a balanced tree.
try it in the quiz →
6.
Which operation is O(1) on a singly linked list that stores only a head pointer?
easy
1. AAccess the element at index i
2. BAppend a node at the tail
3. CInsert a node at the head
4. DDelete the last node
Show answer
Answer: C (Insert a node at the head)
Inserting at the head only creates a node and repoints head. Index access and tail append must walk the list, and deleting the last node needs the second-to-last node, which also takes a full walk. A tail pointer would make appends O(1), but not deleting the last node.
try it in the quiz →
7.
A hash table resolves collisions with linked-list chains and holds n keys. What is the worst-case time for a lookup?
easy
1. AO(1)
2. BO(log n)
3. CO(n log n)
4. DO(n)
Show answer
Answer: D (O(n))
If every key hashes to the same bucket, the table degenerates into one linked list and a lookup scans all n entries. O(1) is the average case with a good hash function and bounded load factor. Some implementations, like Java 8+ HashMap, turn long chains into balanced trees to soften this.
try it in the quiz →
8.
A queue is built from two stacks, moving elements from the input stack to the output stack only when the output stack is empty. What is the amortized cost of a dequeue?
mid
1. AO(1)
2. BO(log n)
3. CO(n)
4. DO(√n)
Show answer
Answer: A (O(1))
Each element is pushed, moved and popped at most once, so n operations do O(n) total work: O(1) amortized each. One dequeue that triggers a transfer can take O(n), which is the worst case for a single call, not the amortized cost.
try it in the quiz →
9.
What is the time complexity of building a binary heap from n unsorted elements with bottom-up heapify, as heapq.heapify does?
mid
1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(n²)
Show answer
Answer: C (O(n))
Sift-down costs at most the height of the node, and most nodes are near the bottom: half are leaves, a quarter have height 1, and so on. The total work sums to O(n). Pushing the elements one by one would be O(n log n).
try it in the quiz →
10.
To find the k largest of n numbers, you scan them while keeping a min-heap of size at most k. What is the time complexity?
mid
1. AO(n log n)
2. BO(n + k)
3. CO(k log n)
4. DO(n log k)
Show answer
Answer: D (O(n log k))
Each of the n elements causes at most one push and one pop on a heap of size k, each O(log k), for O(n log k) total. That beats sorting (O(n log n)) when k is small, and it uses only O(k) memory.
try it in the quiz →
11.
Which pair of data structures gives an LRU cache O(1) get and put?
mid
1. AMin-heap keyed by last access time
2. BHash map and doubly linked list
3. CBalanced BST and a sorted array
4. DTwo stacks and a hash set
Show answer
Answer: B (Hash map and doubly linked list)
The hash map finds the node for a key in O(1), and the doubly linked list keeps recency order, so a node can be moved to the front or evicted from the back in O(1). A heap ordered by access time would make each update O(log n).
try it in the quiz →
12.
A trie stores N words. How long does it take to check whether a word of length L is present?
easy
1. AO(L)
2. BO(N)
3. CO(L log N)
4. DO(N · L)
Show answer
Answer: A (O(L))
A lookup follows one child link per character, so it takes O(L) regardless of how many words are stored. That independence from N, plus fast prefix queries, is the main reason to use a trie.
try it in the quiz →
13.
With both union by rank and path compression, what is the amortized cost of a union-find operation?
hard
1. AO(log n)
2. BO(log log n)
3. CO(α(n))
4. DO(√n)
Show answer
Answer: C (O(α(n)))
α(n) is the inverse Ackermann function, which is at most 4 for any practical n, so operations are effectively constant. Either optimization alone gives only about O(log n).
try it in the quiz →
14.
What does this print for the tree built below?
easy
```
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def walk(n):
    return [n.val] + walk(n.left) + walk(n.right) if n else []

root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(walk(root))
```
1. A[1, 2, 4, 5, 3]
2. B[4, 2, 5, 1, 3]
3. C[4, 5, 2, 3, 1]
4. D[1, 2, 3, 4, 5]
Show answer
Answer: A ([1, 2, 4, 5, 3])
walk records the node before its left and right subtrees, which is pre-order: 1, then the whole left subtree 2, 4, 5, then 3. [4, 2, 5, 1, 3] would be in-order, [4, 5, 2, 3, 1] post-order, and [1, 2, 3, 4, 5] level-order.
try it in the quiz →
15.
Which algorithm finds the path with the fewest edges between two vertices of an unweighted graph in O(V + E)?
easy
1. ADepth-first search
2. BBreadth-first search
3. CPrim's algorithm
4. DTopological sort
Show answer
Answer: B (Breadth-first search)
BFS explores vertices in order of distance, so the first time it reaches a vertex is via a shortest path. DFS finds a path, but not necessarily the shortest. Prim builds a minimum spanning tree, and topological sort only orders a DAG.
try it in the quiz →
16.
A directed graph has some negative edge weights but no negative cycles. Which algorithm reliably computes single-source shortest paths?
mid
1. ADijkstra's algorithm
2. BBreadth-first search
3. CBellman-Ford
4. DPrim's algorithm
Show answer
Answer: C (Bellman-Ford)
Bellman-Ford relaxes every edge V - 1 times, which handles negative weights in O(V · E) and can also detect negative cycles. Dijkstra assumes a finalized vertex can never get cheaper, which negative edges break. BFS ignores weights, and Prim solves a different problem.
try it in the quiz →
17.
Kahn's topological sort runs on a directed graph with 6 vertices but outputs only 4 of them. What does that tell you?
mid
1. AThe graph contains a cycle
2. BThe graph is disconnected
3. CTwo vertices have no edges
4. DThe graph has two sources
Show answer
Answer: A (The graph contains a cycle)
Vertices on a cycle never reach in-degree 0, so Kahn's algorithm can never output them. A disconnected DAG, isolated vertices and multiple sources are all still fully ordered, since each of those vertices eventually has in-degree 0.
try it in the quiz →
18.
Which of these sorting algorithms is not stable in its standard form?
easy
1. AMerge sort
2. BInsertion sort
3. CCounting sort
4. DHeapsort
Show answer
Answer: D (Heapsort)
Heapsort swaps the root with the last heap element, moving items long distances past equal keys, so their relative order is not preserved. Merge sort (taking from the left half on ties), insertion sort and counting sort are all stable.
try it in the quiz →
19.
What is the tight asymptotic lower bound on the worst-case number of comparisons made by any comparison-based sort of n items?
hard
1. AΘ(n log n)
2. BΘ(n)
3. CΘ(n²)
4. DΘ(n log log n)
Show answer
Answer: A (Θ(n log n))
A comparison sort is a binary decision tree that must have at least n! leaves, so its height is at least log₂(n!), which is Θ(n log n). Merge sort and heapsort meet that bound. Counting and radix sort go faster only because they do not rely on comparisons.
try it in the quiz →
20.
A quicksort always picks the first element as its pivot. What is its running time on an already sorted array of n distinct values?
mid
1. AO(n)
2. BO(n log n)
3. CO(log n)
4. DO(n²)
Show answer
Answer: D (O(n²))
On sorted input the first element is the minimum, so every partition puts nothing on one side and n - 1 elements on the other. That gives n + (n - 1) + ... + 1 comparisons, O(n²), with recursion depth n. Random or median-of-three pivots avoid this.
try it in the quiz →
21.
What does this print for a sorted list containing duplicates?
mid
```
from bisect import bisect_left, bisect_right

a = [1, 2, 2, 2, 5, 7]
print(bisect_left(a, 2), bisect_right(a, 2))
```
1. A1 3
2. B1 4
3. C2 4
4. D0 3
Show answer
Answer: B (1 4)
bisect_left returns the first index whose value is >= 2, which is 1. bisect_right returns the first index whose value is > 2, which is 4, one past the last 2. So the 2s occupy indices 1 to 3, and there are 4 - 1 = 3 of them.
try it in the quiz →
22.
This attempt at "longest substring without repeating characters" has a bug. What does it print?
mid
```
def longest(s):
    last, start, best = {}, 0, 0
    for i, ch in enumerate(s):
        if ch in last:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best

print(longest("abba"))
```
1. A2
2. B3
3. C4
4. D1
Show answer
Answer: B (3)
At the second b, start moves to 2. At the final a, the stale entry last["a"] = 0 moves start back to 1, so the window "bba" is counted as length 3. The correct answer is 2; the fix is to move start only when last[ch] >= start.
try it in the quiz →
23.
With coins [1, 3, 4] and amount 6, how many coins does "always take the largest coin that fits" use, compared with the optimum?
mid
1. AGreedy 2, optimal 2
2. BGreedy 3, optimal 2
3. CGreedy 3, optimal 3
4. DGreedy 4, optimal 2
Show answer
Answer: B (Greedy 3, optimal 2)
Greedy takes 4, then 1 + 1, for 3 coins, while 3 + 3 needs only 2. Greedy is not safe for arbitrary coin systems, which is why minimum coin change is solved with DP.
try it in the quiz →
24.
This is the O(n log n) LIS technique. What does it print?
hard
```
from bisect import bisect_left

tails = []
for x in [3, 5, 6, 2]:
    i = bisect_left(tails, x)
    if i == len(tails):
        tails.append(x)
    else:
        tails[i] = x
print(tails, len(tails))
```
1. A[2, 5, 6] 3
2. B[3, 5, 6] 3
3. C[2, 6] 2
4. D[2, 3, 5, 6] 4
Show answer
Answer: A ([2, 5, 6] 3)
After 3, 5, 6 are appended, 2 replaces tails[0], giving [2, 5, 6]. The length 3 is the correct LIS length, but [2, 5, 6] is not a real subsequence, because 2 comes last in the input. Only len(tails) is meaningful.
try it in the quiz →
25.
In the 1D 0/1 knapsack DP, dp[c] = max(dp[c], dp[c - w] + v), what goes wrong if capacity c is iterated upwards instead of downwards?
hard
1. AThe result can only get smaller
2. BIt fails only for zero-weight items
3. CEach item may be used more than once
4. DThe time becomes O(n · W²)
Show answer
Answer: C (Each item may be used more than once)
Going upwards, dp[c - w] may already include the current item, so it can be added again; that computes the unbounded knapsack. Iterating downwards reads only values from before this item was considered. The time stays O(n · W) either way.
try it in the quiz →
26.
For a positive integer x, what does (x & (x - 1)) == 0 tell you?
easy
1. Ax is an odd number
2. Bx is divisible by 4
3. Cx is a power of two
4. Dx has every bit set
Show answer
Answer: C (x is a power of two)
x & (x - 1) clears the lowest set bit, so the result is zero only if x had exactly one set bit, meaning x is a power of two. Keep the parentheses in Java or C, where == binds tighter than &.
try it in the quiz →
27.
What does this XOR reduction print?
easy
```
from functools import reduce
from operator import xor

print(reduce(xor, [4, 1, 2, 1, 2]))
```
1. A0
2. B10
3. C2
4. D4
Show answer
Answer: D (4)
XOR is commutative and associative, a ^ a = 0 and a ^ 0 = a, so the pairs of 1 and 2 cancel and only 4 remains. This finds the one unpaired value in O(n) time and O(1) space. 10 is the sum, not the XOR.
try it in the quiz →