Skip to content
Tutorials Center
My learning

Topics

Lesson 222 of 225 ยท Practice and Review

DSA Interview Questions and Answers

Forty data structures and algorithms interview questions with clear short answers: complexity, arrays, hashing, trees, graphs, sorting, DP, and runnable Python.

Interviewers rarely ask you to recite definitions. They ask a short question, listen to how you reason, and then push with "why?" and "what if?". This page collects about forty of the most common conceptual questions, grouped by topic, with answers short enough to say out loud in under a minute. Where a small piece of code makes the answer stick, you can run it.

Use it as a revision list after you have worked through the tutorial. For every answer, the link points to the lesson that explains the idea in depth, and the Practice Problems pages are the place to train the coding part. A good answer has three parts: the fact, the reason, and the trade-off. "A hash table has O(1) lookup" is a fact. "...on average, because a good hash function spreads keys over buckets, but a bad one or an adversary can make it O(n)" is an answer.

Complexity and analysis

1. What is Big O notation, and why do we use it?

Big O describes how the work of an algorithm grows with the input size n, ignoring constants and lower-order terms. We use it because it compares algorithms independently of the machine and the language: 3nยฒ + 10n + 7 is O(nยฒ), and doubling the input roughly quadruples the work. See Big O Notation.

2. What is the difference between O, Omega and Theta?

O is an upper bound ("grows no faster than"), Omega is a lower bound ("grows at least as fast as"), and Theta is a tight bound (both). In everyday speech people say "O(n)" when they really mean Theta(n). Linear search is O(n) in the worst case and Omega(1) in the best case, so there is no single Theta for the algorithm as a whole. See Best, Worst and Average Case.

3. What are the best, worst and average cases of quicksort?

Best and average: O(n log n), when pivots split the data reasonably evenly. Worst: O(nยฒ), when every pivot is the smallest or largest item (for example, always picking the first element of already sorted data). Randomised pivots make the worst case extremely unlikely. See Quick Sort.

4. What is amortized analysis? Give an example.

It averages the cost of an operation over a whole sequence of operations, not over random inputs. A dynamic array doubles its capacity when full. One append occasionally costs O(n) to copy everything, but the copies add up to less than 2n across n appends, so each append is amortized O(1). See Amortized Analysis and Dynamic Arrays.

5. How do you find the time complexity of a piece of code?

Count how often the innermost statement runs as a function of n. Sequential blocks add (keep the larger), nested loops multiply, a loop that halves or doubles its variable gives log n, and recursion gives a recurrence you solve with the recursion tree or the Master theorem. Do not forget the hidden costs of built-in calls: slicing, in on a list, and string concatenation in a loop are all O(n). See Analyzing Loops and Code and Recurrences.

6. What is space complexity? Does the input count?

It is the extra memory an algorithm needs as a function of n. Usually we count auxiliary space (what you allocate beyond the input), and we say so explicitly. Recursion counts too: the call stack of a recursion of depth d uses O(d) space, which is why a recursive DFS on a path-shaped tree uses O(n) stack. See Space Complexity.

Python Counting steps instead of timing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Linear search needs n steps for the last item while binary search needs about log2(n), so a million items take only about twenty comparisons.

Arrays, strings and linked lists

7. What is the difference between an array and a linked list?

An array stores items contiguously: O(1) access by index, O(n) insertion or deletion in the middle (everything shifts), and great cache behaviour. A linked list stores nodes connected by pointers: O(1) insertion or deletion once you hold the node, but O(n) to reach the k-th item and poor cache locality. In practice arrays win far more often than textbooks suggest. See Arrays and Linked Lists.

8. How does Python's list work internally?

It is a dynamic array of references to objects. Indexing is O(1), append is amortized O(1), insert(0, x) and pop(0) are O(n) because everything moves, and x in lst is O(n). If you need fast removal from the front, use collections.deque.

9. How do you reverse a singly linked list?

Walk the list once, keeping prev, current and next. At each node, save the next node, point the current node backwards, and advance. Time O(n), extra space O(1). See Linked List Problems.

10. How do you detect a cycle in a linked list?

Floyd's tortoise and hare: move one pointer by one step and another by two. If there is a cycle, the fast pointer eventually meets the slow one; if it reaches the end, there is none. O(n) time, O(1) space. The alternative, a set of visited nodes, is simpler but needs O(n) space. See Linked List Techniques and Cycle Detection.

Python Reverse a list and detect a cycle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

11. How do you find the middle of a linked list in one pass?

Use two pointers: the fast one moves two steps for every one step of the slow one. When fast reaches the end, slow is in the middle. This also powers merge sort on linked lists.

12. How do you check whether two strings are anagrams?

Compare their character counts. With collections.Counter it is O(n) time and O(k) space for k distinct characters; sorting both strings is simpler but O(n log n). See String Basics and Hashing Patterns.

Stacks, queues and hashing

13. What is the difference between a stack and a queue?

A stack is last in, first out (LIFO): push and pop at one end. A queue is first in, first out (FIFO): enqueue at the back, dequeue at the front. Stacks power function calls, undo, and DFS; queues power scheduling and BFS. See Stacks and Queues.

14. How would you implement a queue using two stacks?

Keep an "in" stack and an "out" stack. Push into "in". To dequeue, if "out" is empty, pour everything from "in" into "out" (reversing the order), then pop from "out". Each element moves at most twice, so dequeue is amortized O(1).

15. Why is list.pop(0) slow, and what is the fix?

It shifts every remaining element one place left: O(n). collections.deque is a block-linked list with O(1) operations at both ends (but O(n) indexing in the middle).

16. How does a hash table work?

A hash function maps a key to an integer, which is reduced to a bucket index. Lookup, insert and delete hit that bucket directly, giving O(1) on average. See Hash Tables and Hash Functions.

17. What is a collision, and how do you handle it?

Two different keys land in the same bucket. Chaining keeps a small list in each bucket. Open addressing probes other slots (linear, quadratic, or double hashing). Python's dict uses open addressing. A high load factor means more collisions, so tables resize when they get too full. See Collision Handling.

18. What is the worst-case time of a hash table lookup?

O(n), if all keys collide. With a good hash function and resizing the average is O(1). Some languages protect against crafted inputs with randomised hashing (Python randomises str hashes per process).

19. Why must dictionary keys in Python be hashable?

A key's hash must not change while it is in the table, otherwise lookups would look in the wrong bucket. Immutable types (int, str, tuple of hashables) qualify; list and dict do not. Objects that compare equal must have equal hashes.

20. Solve Two Sum: what is the brute force and what is better?

Brute force checks every pair: O(nยฒ) time, O(1) space. Better: one pass with a dict from value to index; for each number look up target - number first. O(n) time, O(n) space. See Hashing Patterns.

Python Two Sum: brute force against hash map

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trees and heaps

21. What is a binary search tree, and what does it guarantee?

A binary tree where, for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. Search, insert and delete take O(h), where h is the height. An in-order traversal visits keys in sorted order. See Binary Search Trees.

22. What goes wrong with an unbalanced BST?

Inserting sorted data produces a chain with height n, so every operation degrades to O(n). Self-balancing trees (AVL, red-black) keep the height at O(log n) with rotations. See Balanced Trees.

23. What are the tree traversals and when do you use each?

Pre-order (node, left, right) copies or serialises a tree; in-order (left, node, right) gives sorted order for a BST; post-order (left, right, node) deletes or evaluates children first; level-order (BFS) works layer by layer. All take O(n) time. See Tree Traversals and Tree BFS.

24. How do you check that a binary tree is a valid BST?

Passing down an allowed range (low, high) is the reliable way; comparing each node only with its direct children is a classic bug, because a deep node can violate an ancestor's bound. O(n) time, O(h) space. Alternatively check that an in-order traversal is strictly increasing.

25. What is a heap, and what does it give you?

A complete binary tree stored in an array where every parent is smaller than (min-heap) or larger than (max-heap) its children. It gives O(1) access to the extreme item and O(log n) push and pop. Building a heap from n items takes O(n). See Heaps and Priority Queues.

26. How do you find the k largest items in a stream?

Keep a min-heap of size k. For each new item, push it; if the heap exceeds k, pop the smallest. The heap holds the k largest seen so far. O(n log k) time, O(k) space, which beats sorting everything when k is small. See Top-K Problems.

Python Top k with a size-limited min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

27. What is a trie, and when does it beat a hash table?

A tree where each edge is a character and each path spells a prefix. Looking up a word of length m costs O(m), independent of how many words are stored, and prefix queries (autocomplete) are natural. A hash set can only answer exact matches. The price is memory. See Tries.

Sorting and searching

28. Which sorting algorithms are stable, and why does it matter?

A stable sort keeps equal keys in their original order. Merge sort, insertion sort, bubble sort and Python's Timsort are stable; quicksort and heap sort (as usually written) are not. Stability matters when you sort by one key after another, such as by city and then by name. See Sorting Basics.

29. Compare merge sort and quicksort.

Merge sort is O(n log n) in every case and stable but needs O(n) extra space for arrays. Quicksort is O(n log n) on average, O(nยฒ) in the worst case, sorts in place (O(log n) stack space on average), and is usually faster in practice because of cache behaviour. See Merge Sort.

30. What is the lower bound for comparison sorting, and how can you beat it?

Any comparison sort needs Omega(n log n) comparisons in the worst case, because there are n! orderings and each comparison halves the possibilities at best. Counting, radix and bucket sort avoid comparisons by exploiting the key structure (small integer ranges, fixed-length digits) and can run in O(n + k). See Counting, Radix and Bucket Sort.

31. What algorithm does Python's sorted use?

Timsort, a hybrid of merge sort and insertion sort that finds existing runs in the data. It is stable, O(n log n) worst case and O(n) on already sorted input. See Shell Sort and Tim Sort.

32. What does binary search require, and what are common bugs?

A sorted (or otherwise monotonic) sequence and random access. Bugs: wrong loop condition (< vs <=), updating bounds without +1 or -1 and looping forever, and returning the wrong boundary when duplicates exist. O(log n) time. See Binary Search and Binary Search Variants.

33. What is "binary search on the answer"?

When the answer is a number and a yes/no check "is value x big enough?" is monotonic, you can binary search over the possible answers instead of the array. Typical: minimum capacity to ship packages in d days. See Binary Search on the Answer.

Graphs and paths

34. How do you represent a graph, and what are the trade-offs?

An adjacency list (dict of lists) uses O(V + E) space and iterates neighbours quickly: best for sparse graphs. An adjacency matrix uses O(Vยฒ) space and answers "is there an edge?" in O(1): good for dense graphs. See Graph Representations.

35. What is the difference between BFS and DFS?

BFS uses a queue and explores layer by layer, so on an unweighted graph it finds shortest paths in edge count. DFS uses a stack (or recursion), goes deep first, and suits cycle detection, topological sorting and connected components. Both run in O(V + E). See BFS and DFS.

Python BFS shortest path on an unweighted graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

36. Why does Dijkstra's algorithm fail with negative edges?

It assumes that once a node is popped with the smallest distance, no later path can improve it. A negative edge can make a longer route cheaper, breaking that assumption. Use Bellman-Ford (O(VยทE)), which also detects negative cycles. See Dijkstra and Bellman-Ford.

37. How do you detect a cycle in a directed graph?

DFS with three colours (unvisited, in progress, done): meeting an "in progress" node means a back edge, so a cycle. Alternatively run Kahn's topological sort: if fewer than V nodes can be ordered, a cycle exists. In an undirected graph, union-find or DFS with a parent check works. See Topological Sort and Union-Find.

38. What is a minimum spanning tree?

A subset of edges that connects all vertices with the smallest total weight and no cycles. Kruskal's sorts edges and adds them unless they close a cycle (checked with union-find): O(E log E). Prim's grows one tree using a heap: O(E log V). See Minimum Spanning Tree.

Recursion, DP and greedy

39. What is the difference between recursion and iteration, and what is a base case?

Recursion solves a problem by calling itself on smaller inputs; the base case stops it. Every recursion can be written iteratively with an explicit stack. Python has a recursion limit (about 1000 frames by default) and no tail-call optimisation, so deep recursion needs an iterative rewrite. See Recursion.

40. What is dynamic programming, and how do you recognise a DP problem?

DP solves a problem by combining answers to overlapping subproblems, each computed once. Signals: you are optimising or counting, the choice at each step depends on a small state, and a plain recursion repeats the same calls. Define the state, write the recurrence, then memoise (top-down) or fill a table (bottom-up). See DP Introduction and Memoization vs Tabulation.

Python Memoisation turns exponential into linear

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

41. When does greedy work, and how is it different from DP?

Greedy makes the best local choice and never reconsiders. It is correct only when a problem has the greedy-choice property (a local optimum extends to a global one) and optimal substructure, as in interval scheduling or Huffman coding. Coin change with coins {1, 3, 4} shows the failure: for 6, greedy takes 4+1+1 (three coins) but 3+3 uses two. DP considers all choices. See Greedy vs DP.

42. What is the difference between memoisation and tabulation?

Memoisation is top-down: recurse and cache results, computing only the states you need, at the cost of recursion depth. Tabulation is bottom-up: fill a table in dependency order, with no recursion and often an easy space optimisation (keep only the previous row). Both have the same time complexity for the same states.

43. What is backtracking?

A systematic search that builds a solution step by step and abandons ("prunes") a partial solution as soon as it cannot lead to a valid one. Examples: N-Queens, permutations, Sudoku. Worst case is exponential, but pruning makes many problems practical. See Backtracking.

Quick revision table

Structure Access Search Insert Delete
Array O(1) O(n) O(n) O(n)
Linked list O(n) O(n) O(1) at a known node O(1) at a known node
Hash table n/a O(1) average O(1) average O(1) average
Balanced BST O(log n) O(log n) O(log n) O(log n)
Binary heap min or max O(1) O(n) O(log n) O(log n)

In an interview, say your approach and its complexity before you code, name the brute force first, and then improve it. Interviewers reward the reasoning, not only the final answer. Problem Solving Strategy and the Patterns Cheat Sheet give you a repeatable routine.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You append n items to a Python list one at a time. What is the total cost, and why?

    Resizing copies the list only occasionally and the capacity grows geometrically, so the copies add up to O(n) across all appends. Each append is therefore amortized O(1).
  2. 2. Which approach finds the 5 largest values among a stream of a million numbers with the least memory?

    A size-5 min-heap uses O(k) memory and O(n log k) time. The other options store all n values.
  3. 3. Why does Dijkstra's algorithm give wrong answers on graphs with negative edge weights?

    Dijkstra's correctness relies on non-negative weights: a longer path can never become shorter. Use Bellman-Ford when edges can be negative.
  4. 4. Which pair of structures gives the correct typical behaviour for BFS and DFS?

    BFS processes nodes in the order they were discovered (FIFO), DFS follows the newest discovery first (LIFO).
  5. 5. For coins {1, 3, 4} and amount 6, what does the greedy strategy give, compared with the optimum?

    Greedy takes the largest coin first and ends with 4+1+1. Dynamic programming finds 3+3, so greedy is not correct for this coin system.

Summary

  • A strong answer states the fact, the reason and the trade-off, and names the complexity.
  • Know the cost table: arrays O(1) access, hash tables O(1) average, balanced trees and heaps O(log n), sorting O(n log n).
  • Hash tables trade memory and worst-case guarantees for speed; tries trade memory for prefix queries; heaps give the extreme item cheaply.
  • BFS finds fewest-edge paths, Dijkstra handles non-negative weights, Bellman-Ford handles negative ones.
  • DP needs overlapping subproblems and a clear state; greedy needs a proof that local choices are safe.
  • Always propose the brute force first, then improve it and explain why the improvement works.

That wraps up the Data Structures and Algorithms tutorial. Keep practising with the Practice Problems and Advanced Problems, and revisit the Patterns Cheat Sheet before your next interview.