These are the conceptual DSA questions interviewers ask — not "solve this problem" but "explain this concept." Strong answers demonstrate understanding, not memorization. Use these to calibrate your knowledge gaps and practice articulating ideas clearly.

Q1: What does Big O notation actually measure?

Big O describes an upper bound on the growth rate of an algorithm's resource consumption (time or space) as input size n approaches infinity. Importantly, it describes the order of growth, not the exact count of operations. O(2n) and O(n) are both O(n) — constant factors are dropped. We care about the dominant term: O(n² + n) is O(n²).

Q2: Difference between O(n) and O(n log n)?

O(n) = linear — double the input, double the time. O(n log n) = linearithmic — doubling input slightly more than doubles the time (by a log factor). For n = 10^6: O(n) ≈ 10^6 operations; O(n log n) ≈ 20×10^6. O(n log n) is the theoretical minimum for comparison-based sorting. The gap is significant at n = 10^8 but negligible at n = 100.

Q3: What is amortized O(1)?

Amortized analysis averages the cost across a sequence of operations. A dynamic array's push is usually O(1) but occasionally O(n) when it resizes. Over any sequence of n pushes, the total work is O(n), so the amortized cost per push is O(1). Each individual operation may be expensive, but rare enough that the average stays constant. Other examples: Union-Find's find, two-stack queue's dequeue.

Q4: Can two algorithms with the same Big O have very different real-world performance?

Absolutely. O() hides constant factors and ignores cache behavior, branch prediction, memory allocation overhead, and input distribution. Quicksort and mergesort are both O(n log n) average, but quicksort typically runs 2–3× faster in practice because it accesses memory sequentially (cache-friendly) and avoids allocating auxiliary arrays. Always benchmark when constant factors matter.

Q5: When should you use a hash map instead of an array?

Use a hash map when: (a) keys are non-consecutive integers or non-integers, (b) you need O(1) lookup by key without knowing the index, (c) the key space is sparse (most possible keys are unused), (d) you need to track counts or mappings. Use an array when: keys are dense consecutive integers starting from 0 — an array lookup is O(1) with a smaller constant and better cache performance than a hash map.

Q6: What causes hash collisions and how are they handled?

A collision occurs when two distinct keys hash to the same bucket. Two main strategies: chaining — each bucket holds a linked list of entries; worst case O(n) if all keys collide. Open addressing — probe for the next free slot (linear, quadratic, or double hashing). The load factor (n/buckets) must be kept low (typically ≤ 0.75) by resizing. A prime table size reduces clustering.

Q7: DFS vs BFS — when do you choose each?

Q8: How do you handle cycles in graph traversal?

Maintain a visited set. Before processing a node, check if it is in visited — if yes, skip it. For directed graphs, you additionally need to distinguish "currently in the DFS stack" (gray) from "fully processed" (black) to detect back edges. The three-color DFS (white/gray/black) detects directed cycles; a simple visited set suffices for undirected graph cycle detection.

Q9: When does a BST beat a hash map?

A BST maintains sorted order; a hash map does not. Use a BST (or sorted map like Java's TreeMap) when you need: ordered iteration, floor/ceiling queries (closest value ≤ or ≥ x), range queries (all keys in [a, b]), or the kth smallest/largest element. Hash maps give O(1) point lookup but cannot answer any of these range/order queries efficiently.

Q10: What is the difference between a tree and a graph?

A tree is a connected acyclic undirected graph with exactly n-1 edges for n nodes. Remove the "connected" constraint and you get a forest. Remove "acyclic" and you get a general graph. A rooted tree additionally designates one node as the root, creating parent-child relationships. A binary tree restricts each node to at most 2 children.

Q11: How do you identify a DP problem?

Two hallmarks: (1) overlapping subproblems — the same smaller problem is solved multiple times (e.g., Fibonacci naively recomputes fib(3) dozens of times). (2) optimal substructure — the optimal solution to the whole problem can be built from optimal solutions to subproblems. Signal phrases: "count the number of ways," "minimum/maximum number of steps," "can you achieve exactly X," or problems on sequences where you consider taking or skipping each element.

Q12: Recursion vs. Iteration — how do you decide?

Recursion is cleaner when the problem has a natural recursive structure (trees, divide-and-conquer, backtracking). Iteration is preferred when: (a) recursion depth is large (stack overflow risk in JavaScript with depth ~10,000), (b) performance is critical (function call overhead), (c) the problem is a simple loop. All recursive solutions can be rewritten iteratively using an explicit stack. Tail recursion optimization (TCO) is not guaranteed in JavaScript.

Q13: What is memoization and how does it differ from tabulation?

Memoization (top-down DP): add a cache to a recursive function; before computing, check if the result is already cached. Only computes subproblems that are actually needed.

Tabulation (bottom-up DP): fill a table iteratively starting from base cases, building up to the answer. Avoids recursion overhead, predictable memory usage, often faster in practice. Choose memoization when you are not sure which subproblems are needed; tabulation when all subproblems must be solved.

Q14: What makes a sorting algorithm stable?

A sort is stable if equal elements maintain their original relative order in the output. This matters when sorting objects by one key when they already have a meaningful order on another key (e.g., sort employees by department, preserving their alphabetical order within each department). Stable sorts: Insertion, Merge, Tim, Counting, Radix. Unstable: Quick Sort, Heap Sort, Selection Sort.

Q15: Why is O(n log n) the lower bound for comparison-based sorting?

To sort n elements, the algorithm must distinguish between n! possible orderings. Each comparison provides 1 bit of information, so at least log₂(n!) comparisons are needed. By Stirling's approximation, log₂(n!) = Θ(n log n). Any comparison-based sort that makes fewer than n log n comparisons cannot correctly sort all inputs. Counting sort, radix sort, and bucket sort avoid this bound because they do not use comparisons — they use the actual values.

Q16: What is an in-place algorithm?

An in-place algorithm uses O(1) extra space — it modifies the input directly rather than allocating auxiliary data structures proportional to input size. Examples: insertion sort (in-place), quick sort (in-place with O(log n) stack), two-pointer array operations. Not in-place: merge sort (needs O(n) auxiliary array), most hash map based solutions. "In-place" does not mean zero memory — O(log n) for recursion stack is acceptable.

Q17: How does tail recursion work and why does it matter?

A tail-recursive function's recursive call is the very last action — the result of the recursive call is returned directly without further computation. This allows compilers/runtimes to reuse the current stack frame instead of allocating a new one, turning recursion into iteration with O(1) stack space. JavaScript / V8 does not reliably perform TCO in strict mode. In practice, convert tail-recursive solutions to explicit loops when stack depth is a concern.

Q18: How would you design a system that needs O(1) lookup, O(1) insert, and O(1) getRandom?

Combine a dynamic array (for O(1) getRandom via random index) with a HashMap from value to array index (for O(1) lookup and O(1) insert). For O(1) delete: swap the target with the last array element, update the map for the swapped element, then pop the array. This is the Randomized Set design (LeetCode 380).

Q19: How does a HashMap's time complexity degrade to O(n)?

If all n keys hash to the same bucket (a degenerate case, e.g., all keys have the same hash code), every lookup must scan the entire chain of n elements. This happens with a bad hash function or when an attacker knows the hash function (hash collision attack). Java 8+ mitigates this by converting long chains to balanced BSTs, giving O(log n) worst case instead of O(n).

Q20: What is the two-pointer technique and why does it work?

Two pointers maintain two indices that move toward each other (or in the same direction) through an array. It works when the array is sorted (or has a monotonic property): moving the left pointer increases the sum/product; moving the right pointer decreases it. This turns an O(n²) brute-force search into an O(n) traversal. Requires sorted order because the correctness argument relies on knowing which direction to move.

Q21: When does Dijkstra's algorithm fail?

Dijkstra fails on graphs with negative edge weights. The greedy assumption (once we finalize a node's distance, it cannot decrease further) breaks down because a negative edge found later could provide a shorter path to an already-finalized node. Use Bellman-Ford for graphs with negative weights (O(VE)). Bellman-Ford also detects negative cycles.

Q22: What is topological sort and when can you apply it?

Topological sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, u appears before v. It exists if and only if the graph has no cycles. Applications: task scheduling with dependencies, course prerequisites, build systems (Makefile), symbol resolution in compilers. Two algorithms: Kahn's (BFS-based, uses in-degree), DFS with post-order stack.

Q23: What are the most common bugs in DSA solutions?

Q24: How do you prove your greedy algorithm is correct?

Two standard proof techniques: (1) Exchange argument — assume the optimal solution differs from your greedy choice at some point; show you can swap in the greedy choice without worsening the result, leading to a contradiction. (2) Greedy stays ahead — show inductively that after each step, the greedy solution is at least as good as any other algorithm at that point. Greedy algorithms are often wrong — validate with small counterexamples before assuming correctness.

Q25: What is the difference between divide and conquer and dynamic programming?

Both break a problem into subproblems. The difference: in divide and conquer, subproblems are independent (merge sort splits the array; the two halves don't overlap). In DP, subproblems overlap — the same subproblem appears in multiple places, and memoization/tabulation prevents redundant recomputation. Divide and conquer does not cache results because each subproblem is solved exactly once.