Coding Patterns quiz

Question 1

What is the sliding window technique and when is it most applicable?

Accepted Answer

O(n)

Answer

O(n·k)

Answer

O(k)

Answer

O(n log n)

Question 2

Which pattern is best suited for the problem 'merge all overlapping intervals'?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n²)

Answer

O(log n)

Question 3

When should you prefer BFS over DFS for graph traversal?

Accepted Answer

BFS guarantees shortest path in unweighted graphs

Answer

DFS guarantees shortest path in unweighted graphs

Answer

Both guarantee shortest path equally

Answer

Neither guarantees shortest path

Question 4

What data structure underpins the Top-K elements pattern and what is its time complexity?

Accepted Answer

O(n log k)

Answer

O(n log n)

Answer

O(k log n)

Answer

O(n·k)

Question 5

What is cyclic sort and when should you use it over comparison-based sorting?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(n²)

Answer

O(n + k)

Question 6

How does the two-heaps pattern solve problems like finding the running median?

Accepted Answer

O(log n) per insertion

Answer

O(1) per insertion

Answer

O(n) per insertion

Answer

O(n log n) per insertion

Question 7

Describe the modified binary search pattern for finding an element in a rotated sorted array.

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n log n)

Answer

O(log²n)

Question 8

What is topological sort and which two algorithms implement it?

Accepted Answer

O(V + E)

Answer

O(V²)

Answer

O(E log V)

Answer

O(V log E)

Question 9

What is multi-source BFS and how does it differ from standard BFS?

Accepted Answer

O(V + E)

Answer

O(V²)

Answer

O(V·E)

Answer

O(E log V)

Question 10

How does the DP pattern for 0/1 Knapsack differ from fractional Knapsack?

Accepted Answer

O(n·W)

Answer

O(n log n)

Answer

O(2^n)

Answer

O(W log n)

Question 11

What is reservoir sampling and why is it needed for streaming data?

Accepted Answer

O(k)

Answer

O(n)

Answer

O(n·k)

Answer

O(log n)

Question 12

Describe the pattern for Trapping Rain Water and its O(n) solution.

Accepted Answer

O(n) time, O(1) space

Answer

O(n) time, O(n) space

Answer

O(n²) time, O(1) space

Answer

O(n log n) time, O(1) space

Question 13

What is the sliding window maximum problem and which data structure solves it in O(n)?

Accepted Answer

O(n)

Answer

O(n·k)

Answer

O(n log k)

Answer

O(k log n)

Question 14

How does the word search backtracking solution work on a 2D grid?

Accepted Answer

O(m·n·4^L)

Answer

O(m·n·L)

Answer

O(4^(m·n))

Answer

O(m·n·2^L)

Question 15

What is Kahn's algorithm and how does it detect cycles while producing a topological order?

Accepted Answer

It detects cycles when output size < V

Answer

It only works on trees

Answer

It requires O(V²) space

Answer

It cannot produce a topological order

Question 16

How does the Number of Islands problem demonstrate both BFS and DFS graph patterns on a grid?

Accepted Answer

O(m·n)

Answer

O(m + n)

Answer

O(m·n·log(m·n))

Answer

O((m·n)²)

Question 17

Describe the Jump Game II pattern for finding the minimum number of jumps to reach the end.

Accepted Answer

O(n)

Answer

O(n²)

Answer

O(n log n)

Answer

O(n·max_jump)

Question 18

What is the Longest Increasing Subsequence (LIS) pattern and what is its O(n log n) solution?

Accepted Answer

O(n log n)

Answer

O(n²)

Answer

O(n)

Answer

O(2^n)

Question 19

Explain the matrix spiral traversal pattern.

Accepted Answer

O(m·n)

Answer

O(m+n)

Answer

O(m·n·log(m·n))

Answer

O((m+n)²)

Question 20

What is the interval DP pattern and how does Matrix Chain Multiplication exemplify it?

Accepted Answer

O(n³)

Answer

O(n²)

Answer

O(2^n)

Answer

O(n⁴)

Test yourself