Common Algorithm Interview Questions

Algorithm interviews rarely test whether you memorized a solution. They test whether you can recognize the shape of a problem, connect it to the right paradigm, and reason clearly about correctness and complexity while you code. This topic collects the questions that come up again and again across coding interviews, along with the reasoning an interviewer is actually listening for.

Look for optimal substructure (the optimal answer is built from optimal answers to subproblems) combined with overlapping subproblems (the same subproblem recurs) — that combination signals DP. If a problem has optimal substructure but making the locally best choice at each step never needs to be revisited (a greedy-choice property, often provable via an exchange argument), greedy suffices and is cheaper. If instead you must explore many candidate partial solutions and prune illegal ones as you go, with no reusable subproblem structure, that is backtracking. A quick test: try greedy first on a small example and look for a counterexample; if you find one, move to DP; if the search space is exponential and you need every valid arrangement rather than one optimum, think backtracking.

Python's list is a dynamic array: append is amortized O(1), indexing is O(1), but insert(0, x) or pop(0) is O(n) because elements shift. dict and set are hash tables: average-case O(1) for get/set/contains, O(n) worst case under pathological hashing (rare in practice). collections.deque gives O(1) append and pop from both ends, which list cannot. Sorting with sorted() or list.sort() is O(n log n) using Timsort. Knowing these lets you reason about the true complexity of code that looks simple but hides expensive operations, such as repeatedly inserting at the front of a list inside a loop.

Use BFS when you need the shortest path in an unweighted graph, or the minimum number of steps/levels between nodes, because BFS explores in increasing distance order. Use DFS when you need to explore entire paths, detect cycles, perform topological sorting, or enumerate all solutions (as in backtracking), since DFS naturally follows a path to its end before backtracking. BFS typically costs more memory (an entire frontier of nodes in the queue), while DFS uses O(depth) space via the call stack or an explicit stack. If a problem says 'shortest' or 'minimum steps' on an unweighted graph, that is almost always a BFS signal.

Start by restating the problem in your own words and clarifying constraints (input size, value ranges, duplicates allowed, sorted or not). Work a small example by hand to build intuition. Identify the brute-force solution first, even if slow, and state its complexity out loud — it anchors the conversation and often reveals the bottleneck to optimize. Then look for structural clues: sorted input suggests binary search or two pointers, a need for all subsets suggests backtracking or bitmasking, repeated overlapping computations suggest memoization, and a graph or grid suggests BFS/DFS/Union-Find. Only after settling on an approach should you write code, and you should narrate the plan before typing.

A time-space tradeoff is when you spend extra memory to reduce running time, or vice versa. Memoization is the classic example: caching subproblem results in a hash map turns an exponential-time recursive solution (like naive Fibonacci, O(2^n)) into O(n) time at the cost of O(n) extra space. Another example is using a hash set to check for duplicates in O(n) time and O(n) space instead of sorting first for O(n log n) time and O(1) extra space. Interviewers want to hear that you can name the tradeoff explicitly and justify which side matters for the given constraints, such as memory-constrained embedded systems favoring the slower, low-memory option.

Write the recurrence relation: express T(n) in terms of the size and number of subproblems, plus the work done outside the recursive calls. For example, merge sort is T(n) = 2T(n/2) + O(n). Then solve it, either by drawing the recursion tree and summing work level by level, or by applying the Master Theorem when the recurrence has the form T(n) = aT(n/b) + O(n^d). Also check whether subproblems overlap; if they do and you are not memoizing, the true complexity can be exponential even though the recurrence looks small, which is a common trap in interviews.

Dijkstra's algorithm finds shortest paths from a source in O((V + E) log V) using a priority queue, but it assumes all edge weights are non-negative; a negative edge can cause it to finalize a distance too early and produce a wrong answer. Bellman-Ford handles negative edge weights (and can detect negative cycles) by relaxing all edges V-1 times, at the cost of O(V * E) time. In an interview, if the graph can have negative weights or you need cycle detection, say Bellman-Ford; if weights are guaranteed non-negative and speed matters, say Dijkstra.

Sorting gives O(n log n), which works but is not optimal. A min-heap of size k gives O(n log k): push each element, popping when the heap exceeds size k, and the heap's root is the answer. Quickselect (a divide-and-conquer partition-based algorithm related to quicksort) achieves average O(n) time by only recursing into the partition that contains the k-th index, discarding the other side entirely, though its worst case is O(n^2) without a good pivot strategy such as median-of-medians or randomization.

State both time and space complexity precisely, including any amortized or average-case caveats, and justify each term by pointing to the specific loop, recursive call, or data structure responsible. For example, 'this is O(n) time because we visit each node once via BFS, and O(n) space for the queue and the visited set in the worst case of a completely connected level.' Interviewers value precision over guessing — if you are unsure whether something is amortized O(1) or worst-case O(n), say so and explain why.