Free Programming learning guide
Data Structures and Algorithms for Tech Interviews
Data Structures and Algorithms for Tech Interviews — a free intermediate-level guide covering understand data structures and algorithms for tech...
What you will learn
1. Foundations of Algorithmic Thinking
The Interview Dilemma: When “Fast Enough” Becomes a Deal‑Breaker You’ve just finished coding a function that finds the most frequent word in a paragraph. It works, passes the sample tests, and you submit it with confidence. A few minutes later the interviewer asks, “What if the paragraph contains a million sentences? How does your solution scale?” In the split second before you answer, the whole problem shifts from “Did it work?” to “Will it work under pressure?” The ability to reason about algorithmic complexity—how a solution’s resource needs grow with input size—is the single most discriminating factor in technical interviews. Mastering this skill lets you: Predict performance before the code even runs. Choose the right data structure for a given constraint. Communicate clearly with interviewers, turning vague “it seems fast” into a precise, defensible claim. The rest of this chapter equips you with the mental toolbox to answer those “how does it scale?” questions confidently. --- Defining Algorithmic Complexity Algorithmic complexity measures how the amount of work (time, memory, or other resources) grows as the input size grows. It abstracts away constant factors (like CPU clock speed) and focuses on the shape of growth. | Complexity Dimension | What It Captures | Typical Symbol | |--------------------------|----------------------|--------------------| | Time complexity | Number of elementary operations performed | T(n) | | Space complexity | Additional memory allocated beyond the input | S(n) | Elementary operation: any step that the computer can execute in constant time—e.g., a variable assignment, a comparison, an arithmetic operation. Input size (n): the quantity that most naturally describes the problem (length of an array, number of nodes in a graph, etc.). When we say an algorithm runs in O(n²) time, we mean that for sufficiently large n, the number of operations is bounded above by a constant multiple of n². The exact constant (the “5” in “5 · n²”) is irrelevant for asymptotic analysis. --- Time vs. Space Complexity: Two Sides of the Same Coin Most interview problems involve a trade‑off between time and space. Understanding both dimensions lets you articulate why a solution is preferable in a given scenario. Time Complexity What it tells you – How long the algorithm will take in the worst (or average) case. Typical concerns – User‑perceived latency, CPU usage, power consumption. Space Complexity What it tells you – How much auxiliary memory the algorithm needs besides the input itself. Typical concerns – Memory limits on embedded devices, stack overflow risk, cache friendliness. Quick Comparison Table | Scenario | Prioritize | Typical Reasoning | |-------------------------------------------|----------------|-----------------------| | Mobile app with limited RAM | Space | Avoid large auxiliary arrays that could trigger OOM. | | Real‑time trading system (nanoseconds) | Time | Even …
2. Arrays and Strings Essentials
A Real‑World Prompt that Sets the Stage You’ve just been handed a stream of sensor readings from a fleet of delivery drones. The data arrives as a flat array of integers, each representing the altitude at a 1‑second interval. The interviewers ask: “In‑place, reverse the last 30 seconds of the data, then rotate the entire array so that the most recent reading becomes the first element. Explain the trade‑offs of using language‑provided helpers versus writing the logic yourself.” This single prompt touches four core skills you’ll master in this chapter: 1. In‑place array reversal – swapping elements without extra storage. 2. Array rotation – moving elements circularly with O(1) extra space. 3. Two‑pointer & sliding‑window patterns – the workhorses for many string problems. 4. Evaluating built‑in vs manual implementations – balancing readability, performance, and interview expectations. Below we unpack each skill, layer on classic interview variants, and keep a running commentary on time and space complexity, tying back to the fundamentals from Foundations of Algorithmic Thinking. --- 1. In‑Place Array Reversal 1.1 The Core Idea Reversing an array means that the element at index 0 swaps with the element at index n − 1, the element at index 1 swaps with n − 2, and so on, until the middle is reached. The classic two‑pointer technique does exactly this: | Pointer | Position | Action | |---------|----------|--------| | left | starts at 0 | move right after each swap | | right | starts at n − 1 | move left after each swap | When left = right the work is done. 1.2 Reference Implementation (Python‑style) Complexity: - Time – each element participates in at most one swap → O(n). - Space – only two integer counters → O(1). 1.3 When to Use Built‑In Helpers Most high‑level languages expose a reverse() method (e.g., list.reverse() in Python, Collections.reverse() in Java). These helpers are: - Readable – one line expresses intent clearly. - Optimized – often written in native code, yielding lower constant factors. But interviewers may penalize reliance on a black‑box if they ask you to explain the algorithm or to adapt it (e.g., reverse only a sub‑range). In such cases, the manual two‑pointer version demonstrates algorithmic fluency and aligns with the Predict performance principle from earlier chapters. 1.4 Edge Cases to Discuss | Situation | Handling | |-----------|----------| | Empty array (n = 0) | Loop never executes – no change. | | Single element (n = 1) | left == right → loop condition false – no change. | | Very large array (≥ 10⁷) | Discuss stack vs heap: swaps are in‑place, no extra heap allocation, safe for large inputs. | --- 2. Array Rotation Rotating an …
3. Linked Lists Mastery
A Real‑World Prompt Imagine you’re hired to improve the playback engine of a popular music streaming service. Users can add, remove, and reorder songs on the fly, and the service must also support “shuffle‑play” without allocating a new array for every user session. The obvious data structure? A linked list—its constant‑time inserts and deletes match the dynamic nature of a playlist, while its modest memory footprint lets the service scale to millions of concurrent users. The interview you’re about to ace will ask you to build exactly this: a mutable sequence that can be traversed forward and backward, reversed instantly, and kept free of accidental loops. Below we walk through the core linked‑list operations you’ll need, from the ground‑up construction of singly and doubly linked lists to the classic interview challenges of reversal, cycle detection, kth‑from‑end retrieval, and in‑place merging. Wherever possible, we’ll tie the discussion back to the algorithmic complexity concepts introduced in Foundations of Algorithmic Thinking and Arrays and Strings Essentials—you’ll see why a particular implementation is O(1) space or O(n) time, and how to communicate those choices clearly in an interview. --- 1. Singly Linked Lists – Building the Foundation A singly linked list (SLL) consists of nodes where each node holds a value and a pointer to the next node. The list is anchored by a head reference; the tail is the node whose next is None. 1.1 Node definition (Python‑style) Why slots? It eliminates the per‑instance dict, reducing the per‑node overhead—a concrete illustration of space complexity (S(n)) considerations. 1.2 Constructing a list from an iterable Complexity: The loop touches each element once → O(n) time, O(1) extra space (the list nodes themselves are required output). 1.3 Traversal patterns | Goal | Code sketch | Remarks | |--------------------------|-------------|---------| | Print all values | cur = head; while cur: print(cur.val); cur = cur.next | Straight‑line scan, linear time. | | Count nodes | cnt = 0; cur = head; while cur: cnt += 1; cur = cur.next | Useful for validating input size before other operations. | | Collect into array | arr = []; cur = head; while cur: arr.append(cur.val); cur = cur.next | Demonstrates conversion back to an array when needed. | 1.4 Insertion & deletion (constant‑time at head) Interview tip: Emphasize that only the head pointer changes, so the operation stays O(1) regardless of list length. 1.5 Insertion after a given node Deletion after a given node follows the same pattern: These primitives become the building blocks for more sophisticated algorithms later. --- 2. Doubly Linked Lists – Bidirectional Flexibility A doubly linked list (DLL) adds a prev pointer to each node, enabling O(1) backward traversal and O(1) removal of a node given its …
4. Stacks, Queues, and Deques
A Real‑World Prompt: “Can you validate this expression in O(n) time?” Imagine you’re interviewing for a backend role and the recruiter asks you to write a function that takes a string containing parentheses, brackets, and braces and returns whether they are properly nested. The catch? They want a single‑pass solution that uses only O(1) extra space besides the data structure you choose. The immediate mental image is a stack—push opening symbols, pop when you see a closing one, and compare. This classic problem instantly reveals whether you understand the LIFO (last‑in‑first‑out) discipline, why it matches the problem’s “most recent opening must close first” requirement, and how to reason about its time/space complexity using the tools introduced in Foundations of Algorithmic Thinking. Below we dive deep into the three workhorse linear structures—stacks, queues, and deques—showing how to implement each with arrays and linked lists, how to harness them for classic interview patterns, and how subtle variations (monotonic stacks, sliding‑window deques) turn ordinary O(n²) ideas into O(n) solutions. --- 1. Stack Fundamentals and Implementations A stack supports two primitive operations: | Operation | Meaning | |-----------|---------| | push(x) | Insert element x on top | | pop() | Remove and return the top element | | peek() (or top()) | Return the top element without removing it | | isEmpty() | Boolean test for emptiness | The LIFO order makes stacks ideal for “undo” mechanisms, depth‑first traversals, and expression evaluation. 1.1 Array‑Based Stack An array gives O(1) random access, so we can treat the end of the array as the stack top. Complexity: All operations are O(1) amortized; resizing incurs O(n) but spreads over many pushes, a classic analysis you already practiced when discussing dynamic arrays. 1.2 Linked‑List Stack A singly linked list naturally supports O(1) insertion and removal at the head, which we designate as the stack top. Complexity: Pure O(1) for all operations, no resizing overhead, and memory usage is proportional to the number of elements (plus the per‑node pointer). 1.3 Choosing Between Array and Linked Implementations | Criterion | Array Stack | Linked Stack | |-----------|------------|--------------| | Cache locality | Excellent (contiguous memory) | Poor (pointer chasing) | | Resize cost | Amortized O(1) but occasional O(n) | Never needed | | Memory overhead | Minimal (just the array) | Extra pointer per element | | Predictable worst‑case | O(1) amortized; occasional O(n) | Strict O(1) | In interview settings, the array version is often preferred because it’s concise and demonstrates awareness of dynamic resizing. The linked version shines when the maximum size is unknown and you want strict O(1) worst‑case guarantees. --- 2. Classic Stack Applications 2.1 Parentheses / Bracket Matching Problem: Given a string s containing ()[]{} …
5. Tree Structures and Traversals
Binary Tree Basics A binary tree is a hierarchical structure where each node has at most two children, conventionally called left and right. Because interview problems often model real‑world hierarchies—file‑system directories, expression parse trees, or UI component trees—being fluent with binary trees pays off immediately. Node definition (Python example) Why a tree, not a list? - Search: In a balanced binary search tree (BST) you can locate a key in O(log n) time, far faster than the linear scan required for an unsorted array. - Hierarchy: Trees naturally represent parent‑child relationships; a flat array would need extra indexing logic. The chapter’s traversal techniques are the “engine” that lets you inspect, modify, or export a tree efficiently. --- Depth‑First Traversals Depth‑first traversals explore as far as possible along each branch before backtracking. Three classic orders exist, each defined by when the node itself is visited relative to its subtrees. | Order | Visit sequence | |------------|------------------------------| | Pre‑order | Node → Left → Right | | In‑order | Left → Node → Right | | Post‑order | Left → Right → Node | Recursive Implementations Recursion mirrors the tree’s definition; the call stack implicitly tracks the path from the root. Complexities – each visits every node exactly once: Time = O(n), Space = O(h) where h is tree height (call‑stack depth). In a balanced tree h = O(log n); in a degenerate (linked‑list) tree h = O(n). Iterative Implementations When interviewers ask for an iterative version, they expect you to manage the traversal state explicitly—usually with a stack (for DFS) or a queue (for BFS). Pre‑order (stack) In‑order (stack) Post‑order (two‑stack trick) Why two stacks? The first stack produces a reverse‑postorder (Node‑Right‑Left). Popping from the second stack restores the correct Left‑Right‑Node order. When to Choose Which Order | Use case | Preferred order | |---------------------------------------|-----------------| | Copying a tree (preserve structure) | Pre‑order (root first) | | Generating sorted output (BST) | In‑order (left → node → right) | | Deleting a tree (free memory) | Post‑order (children before parent) | --- Breadth‑First (Level‑Order) Traversal Breadth‑first explores the tree level by level, from top to bottom and left to right within each level. It’s the natural fit for problems that need “closest to the root” answers, such as finding the shortest path in an unweighted graph that is modeled as a tree. Complexities – identical to DFS: Time = O(n), Space = O(w) where w is the maximum width of the tree (worst‑case O(n) for a very wide tree). Real‑World Example: File System Indexing A cloud storage service needs to display the first k files in a directory tree ordered by depth (so users see the highest‑level files first). A level‑order …
6. Graph Algorithms Fundamentals
Opening the Door to Real‑World Graphs Imagine you’re designing a feature for a professional networking app that suggests “people you may know” within three degrees of separation. The service must answer thousands of queries per second, each asking for the shortest chain of connections between two users. A naïve solution that scans every profile would collapse under load, but a well‑chosen graph representation combined with a fast traversal can return results in milliseconds. The same core ideas—how we store the graph, how we walk it, and how we compute distances—appear in routing protocols, social‑media feeds, fraud detection, and many other interview‑favorite problems. Mastering these fundamentals gives you a toolbox that translates directly into high‑impact code. --- Graph Representations: Adjacency Lists vs. Matrices A graph \(G = (V, E)\) can be encoded in memory in several ways. The two most common structures are the adjacency matrix and the adjacency list. Choosing the right one is the first step in any interview problem that involves graphs. Adjacency Matrix | Feature | Description | |---------|-------------| | Structure | A 2‑D array matrix[V][V] where matrix[u][v] = 1 (or weight) if edge \((u, v)\) exists. | | Space Complexity | O(|V|²) – every possible pair of vertices consumes a cell, even if most pairs are unrelated. | | Edge Lookup | O(1) – direct index access tells you instantly whether an edge exists. | | Iterating Neighbors | O(|V|) – you must scan the whole row to find outgoing edges. | When to use it - Graphs are dense (|E| ≈ |V|²). - Edge existence queries dominate the workload. Real‑world example – Airline route map: a major carrier with flights between most city pairs can be modeled with a matrix where each cell stores the flight distance or cost. Quick “does a direct flight exist?” checks become trivial. Adjacency List | Feature | Description | |---------|-------------| | Structure | An array (or map) of lists: adj[u] holds all vertices v such that \((u, v) ∈ E\). For weighted graphs, each entry stores a pair (v, w). | | Space Complexity | O(|V| + |E|) – only actual edges consume memory. | | Edge Lookup | O(k) where k is the degree of u (need to scan its list). | | Iterating Neighbors | O(k) – directly iterate over the stored neighbors. | When to use it - Graphs are sparse (|E| ≪ |V|²). - Traversal (BFS/DFS) dominates the algorithmic workload. Real‑world example – Social network: each user maintains a list of friends. To suggest connections within three hops, we repeatedly explore these lists, making the adjacency‑list representation natural and memory‑efficient. Choosing the Right Representation - Assess density: If |E| 0.1·|V|², a matrix may be justified; …
7. Sorting and Searching Techniques
The Interview Hook You land a phone screen for a high‑frequency trading firm. The interviewer asks: “Given a list of 1 million timestamps, each with a price, you must detect any price spikes that occur within a 5‑second window, and you have to answer each query in under 10 ms.” The fastest way is to sort the timestamps (so that windows become contiguous) and then use binary search to locate the window boundaries. This single problem forces you to master three classic sorts, understand their stability and space footprints, and apply binary search in non‑trivial ways—exactly the skill set this chapter builds. --- In‑Place QuickSort QuickSort is the go‑to algorithm when interviewers look for a “divide‑and‑conquer” solution that runs in‑place. Partition Schemes | Scheme | Pivot Choice | Number of Swaps | Typical Recursion Depth | Stability | |--------|--------------|----------------|------------------------|---------------| | Lomuto | Last element | O(n) swaps | O(log n) (average) | unstable | | Hoare | Middle/first | O(n) swaps | O(log n) (average) | unstable | Why the difference? Lomuto always swaps the pivot into its final position, potentially moving equal elements past each other. Hoare’s two‑pointer sweep can preserve the relative order of equal keys if you are careful, but the classic implementation still breaks stability. Implementation (Python) Key points In‑place – only O(log n) stack frames (the recursion) plus a few local variables. Average time – O(n log n); worst‑case – O(n²) if the pivot is always the smallest/largest element. Randomized pivot selection or median‑of‑three mitigates this risk. Stability & Space Stability – QuickSort is inherently unstable because elements equal to the pivot can be reordered during partitioning. Space – Aside from the recursive call stack, no extra array is allocated, satisfying the “in‑place” requirement. If interviewers explicitly ask for a stable in‑place sort, you must explain why QuickSort cannot meet that demand and pivot to Merge Sort or a stable variant of Heap Sort. --- Merge Sort – In‑Place Variants Classic Merge Sort (covered in Arrays and Strings Essentials) guarantees O(n log n) time and is stable, but it uses O(n) auxiliary space for the merge step. Interviewers love to probe whether you know the trade‑off between stability and space. Bottom‑up Merge Sort A non‑recursive version that builds sorted runs of size 1, then 2, 4, … The merge routine still needs a temporary buffer of size right‑left. In‑Place Merging (Katajainen & Pasanen) A true in‑place merge can be achieved with the rotation method: 1. Find the first element of the right half that is smaller than the left half’s first element. 2. Rotate the sub‑array [mid … that‑position‑1] to the front using three reversals. 3. Recursively merge the now‑contiguous left and right parts. The …
8. Recursion, Backtracking, and Divide‑and‑Conquer
Why Recursion Is a Interviewer’s Secret Weapon You’ve just been handed a whiteboard problem: “Given a list of time intervals, merge any that overlap and then place a new meeting of length k in the earliest possible slot.” Most candidates will start by scanning the list, perhaps writing a greedy loop, and then get stuck on the “earliest possible slot” part. The hidden clue is that the problem naturally splits into three classic techniques you’ve already seen in other chapters: recursion, backtracking, and divide‑and‑conquer. Mastering the decomposition patterns that underlie these techniques is what separates a “good” solution from a “great” one in a tech interview. --- Foundations of Recursive Thinking The Two‑Step Blueprint 1. Base case – the simplest input for which the answer is known immediately. 2. Recursive case – reduce the current problem to a smaller instance and combine the result. Every recursive algorithm you’ll write follows this blueprint. The earlier chapter on Complexity taught you to count elementary operations; with recursion you also have to account for the recursion depth, which directly impacts space complexity because each call adds a stack frame. Analyzing Recursions When you see a recurrence like \[ T(n) = T\!\left(\frac{n}{2}\right) + O(n) \] you already know, from the Master Theorem introduced in Sorting and Searching Techniques, that the solution is \(O(n\log n)\). Keep a notebook of common recurrences; they become a quick reference during interviews. Tail Recursion and Iterative Conversion A tail‑recursive function performs its last operation as the recursive call. In languages that support tail‑call optimization (e.g., Scheme, some functional subsets of Python with functools.lrucache tricks), the stack does not grow. When the language does not guarantee this, you can rewrite the algorithm iteratively: Understanding this transformation is essential for the “avoid stack overflow” objective. --- Classic Recursive Patterns 1. Factorial The factorial definition is the textbook example of recursion: Why it matters: Interviews love it because you can quickly discuss O(n) time, O(n) space (call stack), and the iterative alternative shown above. 2. Fibonacci A naïve recursive Fibonacci has exponential blow‑up: - Time: \(O(2^n)\) – each call spawns two more. - Space: \(O(n)\) – depth of the recursion tree. The interview follow‑up is almost always: “Can you improve it?” Memoization (top‑down DP) keeps the recursive shape but eliminates repeated work: Now both time and space become \(O(n)\). You can also present the bottom‑up version to show mastery of converting recursion to iteration. 3. Tree Traversals Recall the Tree Structures and Traversals chapter where you learned preorder, inorder, and postorder. Implementing them recursively reinforces the pattern: The same skeleton works for inorder and postorder, just by moving the visit(node) line. Discuss the O(n) time (visits each node once) and O(h) space, …
9. Complexity Optimization and Interview Strategies
The Moment the Clock Starts Ticking You’re in a virtual whiteboard interview. The recruiter asks you to design a system that, given a stream of user actions, can return the most frequently visited page in the last K minutes. The naïve solution—store every event, scan the entire window each time—runs in O(N·K) time and quickly exceeds the time limit. The interviewer leans forward, “Can you make it faster?” That split‑second decision—choosing a smarter data structure, trimming unnecessary work, and explaining it clearly—determines whether you move on to the next round. This chapter equips you with the mental toolbox to compare algorithms, weigh space‑time trade‑offs, and present polished solutions under interview pressure. --- 1. Comparing Algorithmic Paths When a problem admits several plausible approaches, a systematic comparison prevents you from falling into the “first‑thing‑that‑works” trap. 1.1 Identify the Constraint Landscape | Constraint | Typical Impact | Questions to Ask | |------------|----------------|------------------| | Input size (n) | Determines whether O(n²) is acceptable | Is n in the thousands, millions, or unbounded? | | Value range | Influences suitability of counting arrays vs. hash maps | Do keys fall in a small, dense range? | | Update frequency | Affects choice between mutable structures (e.g., balanced BST) and immutable snapshots | Will the data change often or be mostly static? | | Memory budget | Rules out structures with large overhead (e.g., adjacency matrix for sparse graphs) | Is the environment limited to a few megabytes? | | Real‑time requirements | Pushes toward amortized O(1) operations | Do we need sub‑millisecond responses? | These dimensions echo the Complexity Dimension and Typical Symbol concepts introduced in Foundations of Algorithmic Thinking. By explicitly listing constraints, you create a decision matrix that guides the next steps. 1.2 Enumerate Viable Strategies Take the “most frequent page” problem. Three natural routes appear: 1. Sliding‑window hash map – O(1) average insert/remove, O(1) query for max frequency (with auxiliary heap). 2. Balanced binary search tree (BST) keyed by frequency – O(log n) insert/remove/query, automatic ordering. 3. Segment tree / Fenwick tree for range‑frequency queries – O(log U) where U is the universe size, good for static‑range queries. 1.3 Apply a Comparison Framework | Metric | Hash Map + Heap | BST (freq‑keyed) | Segment Tree | |--------|----------------|------------------|--------------| | Time (per event) | O(1) avg insert + O(log n) heap adjust | O(log n) insert + O(log n) delete | O(log U) update | | Space | O(n) for map + O(n) for heap | O(n) nodes + O(n) pointers | O(U) (often large) | | Implementation complexity | Moderate – careful heap‑map sync | High – need custom comparator, rotations | High – build tree over value domain | | …
Continue learning
- Data Structures & Algorithms for Tech InterviewsData Structures & Algorithms for Tech Interviews — a free intermediate-level guide covering understand data structures and algorithms for tech...
- Master Data Structures & Algorithms for Tech InterviewsMaster Data Structures & Algorithms for Tech Interviews — a free intermediate-level guide covering understand data structures and algorithms for tech...
- Intermediate Python Automation Scripts for BeginnersIntermediate Python Automation Scripts for Beginners — a free intermediate-level guide covering intermediate python automation scripts for beginners....
- Intermediate Python Projects for Portfolio BuildingIntermediate Python Projects for Portfolio Building — a free intermediate-level guide covering intermediate python projects for portfolio building....