Data Structures and Algorithms interview questions

22 questions from the Data Structures and Algorithms: Patterns for Interviews course, each with the correct answer and an explanation. Try to answer before you open the answer.

Module 1: Foundations

1. Input goes from 1,000 to 1,000,000. An O(log n) step count roughly...

  1. Triples
  2. Grows 1000x
  3. Grows by ~10 steps
  4. Doubles
Show answer

Answer: Grows by ~10 steps

log2(1e6) - log2(1e3) is about 20 - 10 = 10 extra steps.

Lesson: Big-O & Complexity

Module 2: Data Structures

2. Fastest way to test if two strings are anagrams?

  1. Try every permutation
  2. Reverse one and compare
  3. Sort each string and compare lengths only
  4. Compare character counts
Show answer

Answer: Compare character counts

Counting each character is O(n); permutations are O(n!).

Lesson: Strings

3. You need fast lookup by key and don't care about order. Reach for...

  1. Hash map
  2. Sorted array + binary search
  3. Linked list
  4. Stack
Show answer

Answer: Hash map

Hash map is average O(1) per lookup; binary search is O(log n) and needs sorting.

Lesson: Hash Map

4. Insert 1,2,3,4,5 in order into an empty unbalanced BST. Search cost becomes...

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

Answer: O(n)

Sorted inserts create a right-leaning chain — effectively a linked list. Balanced trees (AVL, red-black) fix this.

Lesson: Binary Search Tree

5. A Fenwick tree's update and prefix-sum operations run in:

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

Answer: O(log n)

Both walk up/down the index by flipping the lowest set bit, taking O(log n) steps.

Lesson: Fenwick Tree (BIT)

Module 3: Graph Algorithms

6. Dijkstra's algorithm gives correct results only when:

  1. The graph is undirected
  2. All edge weights are non-negative
  3. The graph has no cycles
  4. The graph is a tree
Show answer

Answer: All edge weights are non-negative

Negative weights can invalidate the greedy 'closest node is final' assumption — use Bellman-Ford instead.

Lesson: Dijkstra's Algorithm

7. With path compression and union by rank, find/union run in roughly:

  1. O(n)
  2. O(log n)
  3. O(n log n)
  4. Nearly O(1) (inverse-Ackermann)
Show answer

Answer: Nearly O(1) (inverse-Ackermann)

The amortized complexity is O(α(n)), the inverse Ackermann function, which is effectively constant for any realistic n.

Lesson: Union-Find / Disjoint Set

Module 4: Sorting & Searching

8. Binary search requires the data to be...

  1. Stored in a hash map
  2. Of prime length
  3. Sorted (or monotonic on the predicate)
  4. Containing only positive numbers
Show answer

Answer: Sorted (or monotonic on the predicate)

Discarding half only works if one side is guaranteed to not contain the target — that needs order.

Lesson: Binary Search

9. Merge sort's worst-case time is...

  1. O(n^2)
  2. O(n)
  3. O(log n)
  4. O(n log n)
Show answer

Answer: O(n log n)

The split is always balanced, so it's O(n log n) in every case — unlike quicksort.

Lesson: Merge Sort

Module 5: Algorithm Patterns

10. The opposite-ends two-pointer trick needs the array to be...

  1. Sorted
  2. All positive
  3. Even length
  4. Palindromic
Show answer

Answer: Sorted

Sorted order is what lets you decide which pointer to move from the current sum.

Lesson: Two Pointers

11. You need the shortest path in an unweighted graph. Use...

  1. DFS
  2. BFS
  3. Either works equally
  4. Bubble sort
Show answer

Answer: BFS

BFS explores in order of distance, so the first time it reaches the target is a shortest path. DFS gives no such guarantee.

Lesson: Depth-First Search

12. Coins [1, 3, 4], make 6 with fewest coins. Greedy (take 4 first) gives 3 coins (4+1+1). Optimal is...

  1. 3 coins — greedy is right
  2. Impossible
  3. 2 coins (3 + 3)
  4. 1 coin
Show answer

Answer: 2 coins (3 + 3)

3+3 = 6 uses two coins. Greedy fails here — coin change needs DP in general.

Lesson: Greedy

Module 6: Advanced Patterns

13. KMP's overall time complexity for searching pattern of length m in text of length n is:

  1. O(n*m)
  2. O(n + m)
  3. O(n log m)
  4. O(m^2)
Show answer

Answer: O(n + m)

The LPS array is built in O(m), and the search itself is O(n) since the text pointer never backtracks.

Lesson: String Matching

14. Why does LRU cache need a doubly linked list instead of a singly linked list?

  1. It uses less memory
  2. It allows O(1) removal of a node given only a pointer to it
  3. It sorts keys alphabetically
  4. Hash maps require doubly linked lists
Show answer

Answer: It allows O(1) removal of a node given only a pointer to it

With a prev pointer, a node can unlink itself in O(1); a singly linked list would need O(n) to find the previous node.

Lesson: LRU Cache Design

15. What is the time complexity of binary search?

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

Answer: O(log n)

Each step halves the search range.

Lesson: K-way Merge

16. Which structure gives average O(1) lookup by key?

  1. Linked list
  2. Stack
  3. Sorted array scan
  4. Hash map
Show answer

Answer: Hash map

A hash function maps keys to buckets.

Lesson: K-way Merge

17. Which structure suits balanced-bracket checks?

  1. Stack
  2. Queue
  3. Trie
  4. Heap
Show answer

Answer: Stack

Push openings, pop on closings.

Lesson: K-way Merge

18. Which traversal finds shortest paths in an unweighted graph?

  1. DFS
  2. BFS
  3. In-order
  4. Post-order
Show answer

Answer: BFS

BFS explores level by level.

Lesson: K-way Merge

19. When does Dijkstra's algorithm give correct results?

  1. The graph is a tree
  2. The graph is undirected
  3. All edge weights are non-negative
  4. The graph is small
Show answer

Answer: All edge weights are non-negative

Negative edges need Bellman-Ford.

Lesson: K-way Merge

20. What is the worst-case time of merge sort?

  1. O(n^2)
  2. O(n)
  3. O(log n)
  4. O(n log n)
Show answer

Answer: O(n log n)

It always splits and merges evenly.

Lesson: K-way Merge

21. Which pattern handles longest-substring problems in one pass?

  1. Sliding window
  2. Union-find
  3. Bit manipulation
  4. K-way merge
Show answer

Answer: Sliding window

Expand right, shrink left as needed.

Lesson: K-way Merge

22. What makes a problem suitable for dynamic programming?

  1. Random inputs
  2. Overlapping subproblems and optimal substructure
  3. Large strings
  4. Sorted data
Show answer

Answer: Overlapping subproblems and optimal substructure

Store subproblem answers to avoid recomputation.

Lesson: K-way Merge

← Back to the course