DSA practice questions with answers

Practise DSA questions at your own pace: time complexity, arrays, linked lists, stacks, queues, trees, graphs, heaps and dynamic programming. Pick an answer to see whether you are right and why. Nothing is timed or ranked here; for that, play the Daily Quiz at 4 PM IST.

1. Which data structure gives O(1) average-time insert, delete and lookup by key?

   easy

   1. Sorted array
   2. Hash table
   3. Binary search tree
   4. Linked list

   Answer: B. Hash table

   Explanation: A hash table maps keys to buckets directly. A balanced BST gives O(log n); arrays and lists need O(n) searches.

2. What is the time complexity of finding an element in an unsorted linked list?

   easy

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n log n)

   Answer: C. O(n)

   Explanation: There is no random access, so you may have to walk every node.

3. A queue is used for which traversal?

   easy

   1. Inorder
   2. Depth-first
   3. Breadth-first (level order)
   4. Postorder

   Answer: C. Breadth-first (level order)

   Explanation: BFS visits nodes in the order they were discovered: first in, first out.

4. What is the worst-case time of insertion sort?

   easy

   1. O(n)
   2. O(n log n)
   3. O(n²)
   4. O(log n)

   Answer: C. O(n²)

   Explanation: On reverse-sorted input every element shifts past all earlier ones. On nearly sorted input it is close to O(n), which is why it is used for small or almost-sorted arrays.

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

   medium

   1. O(1)
   2. O(log n)
   3. O(√n)
   4. O(n)

   Answer: B. O(log n)

   Explanation: Balanced trees (AVL, red-black) keep the height logarithmic, so search, insert and delete are O(log n). An unbalanced BST can degrade to O(n).

6. What does this return for "racecar"?

   medium

   def check(s):
       i, j = 0, len(s) - 1
       while i < j:
           if s[i] != s[j]:
               return False
           i += 1
           j -= 1
       return True

   1. True
   2. False
   3. An IndexError
   4. "racecar"

   Answer: A. True

   Explanation: Two pointers compare characters from both ends: racecar reads the same backwards, so it is a palindrome.

7. Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?

   medium

   1. Prim's
   2. Kruskal's
   3. Dijkstra's
   4. Floyd–Warshall

   Answer: B. Kruskal's

   Explanation: Kruskal's sorts edges by weight and uses Union-Find to skip edges that would close a cycle. Prim's grows one tree from a start vertex.

8. The minimum number of coins for amount 6 with coins [1, 3, 4] is:

   medium

   1. 2
   2. 3
   3. 4
   4. 6

   Answer: A. 2

   Explanation: 3 + 3 = 6 uses 2 coins. A greedy choice (4 + 1 + 1) uses 3, which is why coin change needs dynamic programming.

9. What is the time complexity of the Floyd–Warshall all-pairs shortest path algorithm?

   hard

   1. O(V + E)
   2. O(V²)
   3. O(V³)
   4. O(E log V)

   Answer: C. O(V³)

   Explanation: Three nested loops over the vertices: for every intermediate k, try to improve the path between every pair i, j.

10. You need the median of a stream of numbers after every insert. What is the standard approach?

    hard

    1. Sort after every insert
    2. Two heaps: a max-heap for the lower half and a min-heap for the upper half
    3. A hash map of counts
    4. A single queue

    Answer: B. Two heaps: a max-heap for the lower half and a min-heap for the upper half

    Explanation: Keep the heaps balanced in size; the median is at one or both tops. Each insert is O(log n) and reading the median is O(1).

11. What is the time complexity of this function?

    hard

    def f(n):
        if n <= 1:
            return 1
        return f(n - 1) + f(n - 1)

    1. O(n)
    2. O(n log n)
    3. O(n²)
    4. O(2ⁿ)

    Answer: D. O(2ⁿ)

    Explanation: Each call makes two calls on n - 1, so the call tree doubles at every level: 2ⁿ calls. Memoising f(n - 1) once would make it O(n).

12. Which problems can be solved with a monotonic stack in O(n)? (Select all that apply)

    hard

    1. Next greater element for every array item
    2. Largest rectangle in a histogram
    3. Daily temperatures (days until a warmer day)
    4. Shortest path in a weighted graph

    Answer: A. Next greater element for every array item; B. Largest rectangle in a histogram; C. Daily temperatures (days until a warmer day)

    Explanation: Each element is pushed and popped at most once. Weighted shortest paths need Dijkstra or Bellman–Ford.

From past Daily Quizzes

1. Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

   DSA · easy

   1. Merge sort
   2. Quick sort
   3. Bubble sort
   4. Heap sort

   Answer: C. Bubble sort

   Explanation: Bubble sort compares neighbours and swaps them, so large values “bubble” to the end on each pass. It is O(n²).

2. What is the minimum number of comparisons any comparison-based sort needs in the worst case?

   DSA · hard

   1. Θ(n)
   2. Θ(n log n)
   3. Θ(n²)
   4. Θ(log n)

   Answer: B. Θ(n log n)

   Explanation: There are n! possible orders, and a decision tree with n! leaves has height ≥ log₂(n!) = Θ(n log n). Counting sort beats this only by not comparing.

3. What is the space complexity of a recursive DFS on a tree of height h (ignoring the output)?

   DSA · medium

   1. O(1)
   2. O(h)
   3. O(n log n)
   4. O(2^h)

   Answer: B. O(h)

   Explanation: The call stack holds one frame per level on the current root-to-node path, so at most h + 1 frames.

4. Which data structure does breadth-first search (BFS) use to decide which node to visit next?

   DSA · easy

   1. Stack
   2. Queue
   3. Priority queue
   4. Hash set

   Answer: B. Queue

   Explanation: BFS explores level by level: nodes are visited in the order they were discovered, which is exactly a FIFO queue. DFS uses a stack (or recursion).

5. What is the time complexity of Dijkstra’s algorithm with a binary heap on a graph with V vertices and E edges?

   DSA · hard

   1. O(V²)
   2. O((V + E) log V)
   3. O(V + E)
   4. O(E · V)

   Answer: B. O((V + E) log V)

   Explanation: Each vertex is extracted once and each edge may push or decrease a key, each costing O(log V). With a Fibonacci heap it improves to O(E + V log V).

6. Kadane’s algorithm finds:

   DSA · medium

   1. The longest increasing subsequence
   2. The maximum sum of a contiguous subarray
   3. The shortest path in a DAG
   4. The k-th smallest element

   Answer: B. The maximum sum of a contiguous subarray

   Explanation: Track the best sum ending at each index: max(x, best_ending_here + x). The best of those is the answer, in one O(n) pass.

7. What does this function return for f(5)?

   DSA · easy

   def f(n):
       if n <= 1:
           return 1
       return n * f(n - 1)

   1. 15
   2. 24
   3. 120
   4. 720

   Answer: C. 120

   Explanation: It is factorial: 5 × 4 × 3 × 2 × 1 = 120.

8. The KMP string-matching algorithm runs in O(n + m) because it:

   DSA · hard

   1. Hashes every substring
   2. Never moves the text pointer backwards, using a prefix-function (failure) table
   3. Sorts the pattern first
   4. Uses dynamic programming over all pairs of positions

   Answer: B. Never moves the text pointer backwards, using a prefix-function (failure) table

   Explanation: On a mismatch KMP jumps the pattern using the longest proper prefix that is also a suffix, so each text character is examined a bounded number of times.

9. Which data structure gives O(log n) insert and O(1) access to the maximum?

   DSA · medium

   1. Sorted array
   2. Max-heap
   3. Hash map
   4. Unsorted linked list

   Answer: B. Max-heap

   Explanation: A max-heap keeps the maximum at the root (O(1) peek) and inserts by sifting up the tree height (O(log n)). A sorted array needs O(n) to insert.

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

    DSA · easy

    1. Queue
    2. Stack
    3. Heap
    4. Linked list

    Answer: B. Stack

    Explanation: A stack pushes and pops from the same end, so the last item added is the first removed. A queue is FIFO.

11. In a min-heap, where is the smallest element?

    DSA · easy

    1. At a leaf
    2. At the root
    3. At the last index
    4. Anywhere

    Answer: B. At the root

    Explanation: Every parent is ≤ its children, so the minimum is always at the root (index 0 in the array form), readable in O(1).

12. A queue built on a circular array of size k: what is the time to enqueue when it is not full?

    DSA · easy

    1. O(1)
    2. O(log k)
    3. O(k)
    4. Depends on the element

    Answer: A. O(1)

    Explanation: Write at the tail index and move it forward modulo k. Nothing shifts.

13. What is printed?

    DSA · hard

    def count(grid):
        seen = set()
        def dfs(r, c):
            if (r, c) in seen or not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] == 0:
                return
            seen.add((r, c))
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc)
        n = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1 and (r, c) not in seen:
                    dfs(r, c)
                    n += 1
        return n
    
    print(count([[1, 1, 0, 0],
                 [0, 1, 0, 1],
                 [1, 0, 0, 1],
                 [0, 0, 1, 0]]))

    1. 3
    2. 4
    3. 5
    4. 6

    Answer: B. 4

    Explanation: Islands connect only up/down/left/right: {(0,0),(0,1),(1,1)}, {(1,3),(2,3)}, {(2,0)} and {(3,2)}: 4 islands. Diagonal cells do not join.

14. The 0/1 knapsack DP runs in O(n·W). Why is it still called “pseudo-polynomial”?

    DSA · hard

    1. Because it uses recursion
    2. Because W is a number whose input size is only log W bits, so the time is exponential in the input length
    3. Because it only works for small n
    4. Because it gives approximate answers

    Answer: B. Because W is a number whose input size is only log W bits, so the time is exponential in the input length

    Explanation: Running time is polynomial in the value W, not in the number of bits needed to write W. Doubling the bits squares W.

15. Which problems are NP-complete? (Select all that apply)

    DSA · hard

    1. Boolean satisfiability (SAT)
    2. Shortest path with non-negative weights
    3. Decision version of the travelling salesman problem
    4. Sorting an array

    Answer: A. Boolean satisfiability (SAT); C. Decision version of the travelling salesman problem

    Explanation: SAT was the first problem proved NP-complete (Cook–Levin), and “is there a tour of length ≤ k?” is NP-complete. Shortest paths and sorting have polynomial algorithms.

16. A trie (prefix tree) is best suited for:

    DSA · medium

    1. Range sum queries
    2. Prefix search / autocomplete
    3. Shortest paths
    4. Finding the k-th largest element

    Answer: B. Prefix search / autocomplete

    Explanation: Each edge is a character, so all words with a prefix sit under one node. Finding them costs O(length of prefix) plus the output.

17. In an adjacency list, how much memory does a graph with V vertices and E edges need?

    DSA · medium

    1. O(V)
    2. O(E)
    3. O(V + E)
    4. O(V²)

    Answer: C. O(V + E)

    Explanation: One list per vertex (V) plus one entry per edge (E, or 2E undirected). An adjacency matrix needs O(V²).

18. Which problem is solved with the sliding-window technique in O(n)?

    DSA · medium

    1. Longest substring without repeating characters
    2. Shortest path in a weighted graph
    3. Number of islands in a grid
    4. All subsets of a set

    Answer: A. Longest substring without repeating characters

    Explanation: Grow the window to the right and shrink it from the left whenever a character repeats; each index enters and leaves the window once.

19. What is the time complexity of building a binary heap from n unsorted elements using bottom-up heapify?

    DSA · medium

    1. O(n)
    2. O(n log n)
    3. O(log n)
    4. O(n²)

    Answer: A. O(n)

    Explanation: Most nodes are near the bottom and sift down only a short distance. Summing the work level by level gives O(n), not O(n log n).

20. Accessing the element at index i of an array takes:

    DSA · easy

    1. O(1)
    2. O(log n)
    3. O(i)
    4. O(n)

    Answer: A. O(1)

    Explanation: Array elements sit in contiguous memory, so the address is base + i × size: one calculation, no matter how large the array.

21. What does this print?

    DSA · hard

    from functools import lru_cache
    
    @lru_cache(None)
    def ways(n, k):
        # ways to write n as an ordered sum of parts each <= k
        if n == 0:
            return 1
        return sum(ways(n - p, k) for p in range(1, min(n, k) + 1))
    
    print(ways(4, 2))

    1. 3
    2. 4
    3. 5
    4. 8

    Answer: C. 5

    Explanation: Ordered sums of 4 using 1s and 2s: 1111, 112, 121, 211, 22 → 5. With k=2 it is the stair-climbing Fibonacci again: ways(4) = 5.

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

    DSA · medium

    1. O(n)
    2. O(n log n)
    3. O(n²)
    4. O(log n)

    Answer: C. O(n²)

    Explanation: If the pivot is always the smallest or largest element (e.g. first element on sorted input), partitions are n−1 and 0, giving n + (n−1) + … = O(n²).

23. Which problem is a classic use of the two-pointer technique on a sorted array?

    DSA · easy

    1. Find two numbers that add up to a target
    2. Find the median of a stream
    3. Detect a cycle in a graph
    4. Find all permutations

    Answer: A. Find two numbers that add up to a target

    Explanation: Start one pointer at each end: if the sum is too small move the left pointer right, if too big move the right pointer left. O(n) total.

24. With union by rank and path compression, the amortised cost of a Union-Find operation is:

    DSA · hard

    1. O(log n)
    2. O(α(n)), inverse Ackermann
    3. O(√n)
    4. O(1) worst case

    Answer: B. O(α(n)), inverse Ackermann

    Explanation: Tarjan proved the amortised bound is O(α(n)); α grows so slowly it is ≤ 4 for any practical n, but it is not strictly constant.

25. The recurrence T(n) = 2T(n/2) + O(n) solves to:

    DSA · medium

    1. O(n)
    2. O(n log n)
    3. O(n²)
    4. O(log n)

    Answer: B. O(n log n)

    Explanation: This is merge sort: log n levels of recursion, each doing O(n) total work. Master theorem case 2.

26. What is the time complexity of binary search on a sorted array of n elements?

    DSA · easy

    1. O(n)
    2. O(log n)
    3. O(n log n)
    4. O(1)

    Answer: B. O(log n)

    Explanation: Each comparison halves the remaining range, so at most about log₂ n steps are needed.

27. Which statement about strongly connected components (SCCs) is true?

    DSA · hard

    1. They only exist in undirected graphs
    2. Tarjan’s and Kosaraju’s algorithms find all SCCs in O(V + E)
    3. Finding SCCs needs O(V³) Floyd–Warshall
    4. Every DAG has exactly one SCC

    Answer: B. Tarjan’s and Kosaraju’s algorithms find all SCCs in O(V + E)

    Explanation: Both run DFS-based passes in linear time. In a DAG every vertex is its own SCC, so a DAG with V vertices has V SCCs.

28. How many distinct ways are there to climb 5 stairs taking 1 or 2 steps at a time?

    DSA · medium

    1. 5
    2. 8
    3. 10
    4. 13

    Answer: B. 8

    Explanation: ways(n) = ways(n−1) + ways(n−2) with ways(1)=1, ways(2)=2: 1, 2, 3, 5, 8. It is the Fibonacci sequence.

Play the Daily Quiz at 4 PM IST