Daily Coding Quiz: Thursday, 12 November 2026

All 10 coding questions with answers and explanations. 0 players took part.

1. 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.

2. 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.

3. 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.

4. 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²).

5. 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²).

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

Play the next Daily Quiz at 4 PM IST