DSA & Algorithms

1How DSA interviews actually work — what they test

The secret: they're not really testing whether you can invent an algorithm under pressure.

A coding interview evaluates several things at once, and raw algorithmic cleverness is only one. They're watching your problem-solving process (do you clarify, plan, and reason?), your communication (can you think out loud?), your coding fluency (clean, correct, bug-aware code), and your ability to analyse complexity and handle edge cases. A working solution delivered silently can score worse than a not-quite-finished one explained clearly.

That reframing is liberating and strategic: because most problems are variations on a finite set of patterns (§13), preparation is about recognition, not memorisation. Learn to map a new problem to a known pattern, and the interview becomes far more tractable. The rest of this module builds that recognition toolkit plus the spoken process that showcases it.

2Big-O — reading time & space complexity

Big-O describes how an algorithm's cost grows as input size grows, ignoring constants and lower-order terms — it's about scaling behaviour, not exact timing. You must be able to read it off your own code and state it unprompted.

The anchors: a single loop over n is O(n); nested loops are O(n²); halving the search space each step (binary search) is O(log n); good sorts are O(n log n); and O(2ⁿ)/O(n!) (often naïve recursion) are red flags to optimise. Don't forget space complexity — extra memory used, including the recursion call stack. The senior reflex is to state the brute-force complexity, then explain how your optimisation improves it.

3Arrays & strings

The most common problem substrate. Arrays give O(1) index access and are cache-friendly, but inserting/deleting in the middle is O(n) because elements shift. Strings are essentially arrays of characters, often immutable (so building one in a loop with + can be a hidden O(n²) — use a builder/list and join).

These are where the two-pointer and sliding-window patterns (§13) shine, so many "do something to a subarray/substring" problems live here. The instinct to build: when you see an array or string problem, ask whether sorting first helps, whether a hashmap can trade space for time, or whether two pointers can avoid a nested loop. That trio resolves a large share of these.

4Hashmaps & sets — the workhorse

If you remember one tool, make it the hashmap. It gives average O(1) insert, delete, and lookup, which lets you trade space for time to collapse many O(n²) brute forces into O(n). A set is the same structure for membership ("have I seen this?"); a map stores key→value (counts, indices, groupings).

The canonical example is Two Sum: instead of checking every pair (O(n²)), store each number's complement in a hashmap and look it up in one pass (O(n)). Whenever a problem involves counting frequencies, detecting duplicates, grouping, or "find the pair/element that…", a hashmap is usually the key. "Can a hashmap turn this into one pass?" should be a reflex question.

5Stacks & queues

Two restricted-access structures whose order is the point. A stack is LIFO (last in, first out) — the right tool whenever you need to track the "most recent" thing: matching brackets, undo, the call stack itself, depth-first traversal, and "next greater element" problems. A queue is FIFO (first in, first out) — for processing in arrival order, and the engine of breadth-first search (§8).

Recognising them is mostly about spotting the access pattern: nested/matching structure or "most recent" → stack; level-by-level or "process in order" → queue. A deque (double-ended queue) generalises both and powers the sliding-window-maximum pattern. Knowing which order discipline a problem needs often hands you the solution.

6Linked lists

A linked list stores elements as nodes each pointing to the next. The tradeoff versus arrays: O(1) insertion/deletion if you have the node (no shifting), but O(n) access (no indexing — you must walk). Interview problems lean on pointer manipulation: reversing a list, detecting a cycle, finding the middle, merging two sorted lists.

The signature technique is two pointers, especially fast and slow: advance one pointer twice as fast as the other to find the middle in one pass, or detect a cycle (if they ever meet, there's a loop — Floyd's algorithm). The recurring caution is careful pointer handling and edge cases: empty list, single node, and losing your reference to the rest of the list mid-reversal. Drawing the nodes on paper prevents most bugs.

7Trees & binary search trees

A tree is a hierarchy of nodes; a binary tree has up to two children each. The binary search tree (BST) adds an ordering invariant — left subtree smaller, right subtree larger — which gives O(log n) search/insert/delete when balanced (and degrades to O(n) when it degenerates into a list, which is why self-balancing trees like AVL/red-black exist).

Master the traversals, because most tree problems are a traversal in disguise: in-order (left-root-right) visits a BST in sorted order; pre-order and post-order suit copying and deletion; level-order (BFS) processes tier by tier. Most tree problems are naturally recursive (§10) — solve for a node assuming the function works on its children. "Is this a tree traversal, and which order?" cracks a huge fraction of them.

8Graphs + BFS / DFS

A graph is nodes connected by edges — the most general structure, modelling networks, maps, dependencies, relationships. Know the representations (adjacency list is the usual choice; adjacency matrix for dense graphs) and the two fundamental traversals, which are the backbone of most graph problems.

BFS uses a queue, explores neighbours level by level, and finds the shortest path in an unweighted graph. DFS uses a stack or recursion, plunges down one path before backtracking, and suits connectivity, cycle detection, and path-finding. Both must track visited nodes to avoid infinite loops — the #1 graph bug. Recognise graph problems behind disguises: grids ("number of islands"), dependencies (topological sort), and "shortest/least steps" prompts.

9Heaps & priority queues

A heap is a tree-based structure that keeps the min (or max) element instantly accessible: O(1) to peek the top, O(log n) to insert or pop. A priority queue is the abstraction it implements — "always give me the most important item next."

The pattern to recognise: any problem asking for the "top K," "K largest/smallest," "K closest," or a running median is usually a heap problem. For "K largest," a min-heap of size K is the elegant trick — keep only the K best seen so far in O(n log K), far better than sorting everything. Heaps also power Dijkstra's shortest-path and merge-K-sorted-lists. "Do I need the most/least extreme element repeatedly?" → heap.

10Recursion & the call stack

Recursion solves a problem by solving smaller instances of itself. Every recursive solution needs two things: a base case (when to stop) and a recursive case (reduce toward the base). Get the base case wrong and you get infinite recursion → a stack overflow, because each call consumes a frame on the call stack.

The mental unlock is the leap of faith: assume the recursive call correctly solves the smaller problem, and just combine its result. Don't trace every level in your head — trust the recursion and define the base case and the combine step. This is the foundation of tree/graph traversal and dynamic programming (§12). The cost to remember: recursion uses O(depth) stack space, which can matter.

11Sorting & searching essentials

You won't usually implement a sort from scratch, but you must understand the landscape. Good general sorts (merge sort, quicksort, heapsort) are O(n log n) — know that's the comparison-sort floor. Merge sort is stable and predictable; quicksort is fast in practice but O(n²) worst case. The practical move is to call the language's built-in sort and reason about its cost.

Binary search is the searching essential and a frequent star: on a sorted array it finds an element in O(log n) by halving the range each step. The deeper pattern is "binary search on the answer" — when a problem has a monotonic yes/no property, you can binary-search the answer space (e.g. "minimum capacity to ship in D days"). Recognising sortable structure or a monotonic condition often unlocks a logarithmic solution.

12Dynamic programming — the non-scary version

DP intimidates people, but the core idea is simple: break a problem into overlapping subproblems and store each subproblem's answer so you never recompute it. It applies when a problem has (1) optimal substructure (the answer is built from answers to subproblems) and (2) overlapping subproblems (the same subproblems recur).

Two flavours: memoization (top-down) — write the natural recursion, then cache results; and tabulation (bottom-up) — fill a table from the smallest cases up. The classic illustration is Fibonacci: naïve recursion recomputes the same values exponentially (O(2ⁿ)); caching them makes it O(n). The recognition cue: "count the ways," "min/max cost/path," or "can I reach…" over choices, especially where greedy fails. Start with the recursion, spot the repeated work, add a cache — that's 80% of interview DP.

13The pattern toolbox

This is the highest-leverage section: a handful of patterns covers a large fraction of problems, and recognising them is the whole game.

• Two pointers — pointers moving through a sorted array from both ends or at different speeds; pair-sums, palindromes, partitioning.
• Sliding window — a moving subarray/substring window; "longest/shortest/contains" over contiguous ranges, in O(n).
• Fast & slow pointers — cycle detection and finding the middle of a linked list.
• Binary search on the answer — minimise/maximise with a monotonic feasibility check.
• BFS/DFS — anything tree/graph/grid-shaped.
• Top-K with a heap, and DP for overlapping-subproblem optimisation.

The skill is mapping signals to patterns: "sorted array + pair" → two pointers; "contiguous subarray" → sliding window; "shortest path unweighted" → BFS; "top K" → heap; "count ways / min cost" → DP. Practising recognition (§15) is more valuable than grinding solutions, because the pattern is the solution.

14How to solve a problem live — the spoken script

This script keeps you calm, demonstrates structured thinking, and is itself half the score. Run it out loud, every time:

1. Clarify — restate the problem, ask about inputs, ranges, edge cases, and constraints. Never start coding on assumptions.
2. Examples — walk a concrete example (and an edge case) to confirm understanding.
3. Brute force — state the obvious solution and its complexity. This shows you can always produce something and gives a baseline.
4. Optimise — identify the bottleneck and the pattern (§13) that improves it; state the new complexity before coding.
5. Code — implement the agreed approach cleanly, narrating as you go.
6. Test — trace your code on the example and edge cases; fix bugs proactively.

15A realistic practice cadence

How you practise determines results far more than how much. Some key points to carry into your prep:

• Quality over quantity — deeply understanding ~100–150 well-chosen problems across the patterns beats skimming 500.
• Organise by pattern (§13), not at random — you're building recognition, so group problems by the technique they teach.
• Spaced repetition — revisit problems after a few days; re-deriving a solution cold is what cements it.
• Simulate the real thing — a timer, talking aloud, and a plain editor; practise the performance, not just the answer (Module 18).
• Review failures hardest — the problems you couldn't solve teach the most; understand the pattern you missed.
• Consistency beats cramming — a steady cadence over weeks builds durable recognition; a last-minute binge doesn't.

The throughline of this whole module: coding interviews reward pattern recognition plus a clear spoken process, and both are trainable. Prepare those two things deliberately and the round stops being a lottery.