Algorithms and Data Structures Interview Questions and Answers

Sample questions

A few questions from each level with the correct answer and an explanation.

Algorithms and Data Structures · Junior

1. What does Big O notation describe?

   Correct answer: How the running time or memory grows as the input size grows

   Big O describes the growth rate: how the cost changes when n grows, ignoring constants and lower-order terms. It says nothing about absolute time on a specific machine: an O(n) loop can be slower than an O(n²) one for small inputs.

2. Why is O(2n + 10) written simply as O(n)?

   Correct answer: Because constants and lower-order terms don't change the growth rate

   Big O describes the shape of growth for large n. Multiplying by 2 or adding 10 doesn't change that the cost grows linearly, so both are dropped. In practice constants still matter, which is why benchmarks exist.

3. Which complexity grows the slowest as n increases?

   Correct answer: O(log n)

   Logarithmic growth is very slow: doubling n adds just one step. For a million elements log₂ n is about 20. O(n) and O(n log n) grow much faster.

4. What is the complexity of reading arr[i] from a JavaScript array?

   Correct answer: O(1)

   Access by index is constant time: the engine computes where the element is instead of walking through the array. That's the main advantage of arrays over linked lists.

Algorithms and Data Structures · Middle

1. How does merge sort work?

   Correct answer: Split the array in halves, sort each half, then merge them

   Merge sort divides until single elements remain, then merges sorted halves with two pointers. It's O(n log n) in every case and stable, but it needs O(n) extra memory for merging.

2. What is the main drawback of merge sort on arrays?

   Correct answer: It needs O(n) extra memory for merging

   The merge step writes into a temporary buffer. The time is O(n log n) regardless of the input, and the classic implementation is stable. On linked lists merge sort can be done without the extra buffer.

3. What is the worst case of quicksort and when does it happen?

   Correct answer: O(n²), when pivots keep splitting the array very unevenly

   If the pivot is always the smallest or largest element (for example, the first element of a sorted array), each partition removes only one element. Random pivots or median-of-three make this unlikely; the average is O(n log n).

4. Why is quicksort often faster than merge sort in practice despite the same O(n log n) average?

   Correct answer: It sorts in place and accesses memory sequentially

   Partitioning works inside the array with good cache locality and small constants. Its worst case is actually worse (O(n²)), and the usual in-place version is not stable.

Algorithms and Data Structures · Senior

1. Why does Dijkstra's algorithm give wrong results with negative edge weights?

   Correct answer: A finalized vertex could still get shorter via a negative edge

   Dijkstra assumes that once the closest vertex is taken from the queue, no later path can be shorter. A negative edge breaks that assumption. Bellman-Ford handles negative weights in O(V × E) and also detects negative cycles.

2. What extra capability does Bellman-Ford have compared with Dijkstra?

   Correct answer: It works with negative weights and detects negative cycles

   It relaxes all edges V - 1 times; if a V-th pass still improves a distance, there's a negative cycle. The price is O(V × E), much slower than Dijkstra's O((V + E) log V).

3. How does A* differ from Dijkstra's algorithm?

   Correct answer: It adds an estimate of the remaining distance

   A* orders vertices by g + h: the known cost plus an estimate to the goal, such as straight-line distance on a map. If h never overestimates (admissible), the path is still optimal, and far fewer vertices are explored.

4. What is the complexity of Floyd-Warshall, and when is it a reasonable choice?

   Correct answer: O(V³); for all-pairs shortest paths on small, dense graphs

   It's three nested loops over vertices, updating dist[i][j] through every intermediate k. Simple and handles negative edges (without negative cycles), but at V = 10,000 it's already 10¹² steps.