Free Programming learning guide
Data Structures & Algorithms for Tech Interviews
Data Structures & Algorithms for Tech Interviews — a free intermediate-level guide covering understand data structures and algorithms for tech...
What you will learn
1. Complexity Analysis & Big O Notation
Why a Few Milliseconds Matter Imagine you’re interviewing for a software engineering role at a fast‑growing startup. Two candidates have just finished the same coding test: both wrote a function that checks whether a list of user IDs contains any duplicates. Candidate A’s solution runs in 0.02 s on the provided test data; Candidate B’s solution takes 1.8 s. The input size is tiny—only a few hundred IDs—so the difference isn’t obvious at first glance. When the company scales the service to handle millions of daily requests, Candidate A’s algorithm will stay comfortably under the latency budget, while Candidate B’s will become a bottleneck that forces the team to add more servers or rewrite the code entirely. The ability to predict how an algorithm behaves as the input grows—its asymptotic performance—is what interviewers test, and what engineers rely on when they design systems that must scale. This chapter equips you with the tools to analyze both time and space requirements, compare alternatives, and make informed choices under interview pressure. --- 1. Asymptotic Notation: The Language of Scalability 1.1 What “Big O” Really Means Big O describes an upper bound on the growth rate of a function. Formally, a function f(n) is O(g(n)) if there exist constants c 0 and n₀ such that for all n ≥ n₀: \[ 0 \le f(n) \le c \cdot g(n) \] In plain English: beyond some threshold, f(n) never exceeds a constant multiple of g(n). Big O is useful because it abstracts away machine‑specific details (CPU speed, cache effects) and focuses on how the algorithm scales. 1.2 Complementary Notations | Notation | Meaning | Typical Use | |----------|---------|-------------| | Ω(g(n)) | Lower bound: f(n) ≥ c·g(n) for sufficiently large n | Guarantees a minimum amount of work | | Θ(g(n)) | Tight bound: f(n) is both O(g(n)) and Ω(g(n)) | Exact asymptotic growth (up to constant factors) | | o(g(n)) | Strictly smaller: f(n) / g(n) → 0 as n → ∞ | Shows a function grows much slower | | ω(g(n)) | Strictly larger: f(n) / g(n) → ∞ as n → ∞ | Shows a function grows much faster | For interview work, Big O, Ω, and Θ are the most common. Knowing the relationships helps you argue why an algorithm is at least as fast as another (Ω) or exactly as fast (Θ). 1.3 Visualizing Bounds Think of the three notations as fences around the growth curve of f(n): - Ω is the inner fence (the algorithm can’t be faster than this). - O is the outer fence (the algorithm can’t be slower than this). - Θ is when both fences coincide, pinning the growth tightly. When you write “the algorithm runs …
2. Arrays and Strings
The Hidden Cost of “Just Look It Up” You’re on a call with a senior engineer who asks, “Can we check whether a user’s recent actions contain the pattern ABCD in O(1) time?” Your mind races. “That’s impossible—pattern matching is at least linear, right?” The truth is that the right data structure and the right algorithmic pattern often turn an apparently expensive operation into a trivial constant‑time lookup. Arrays and strings sit at the core of this transformation. Mastering their elementary operations, together with a handful of powerful techniques, gives you the toolbox needed for the majority of “coding‑the‑interview” questions that revolve around contiguous data. Below we dive straight into the practical side of arrays and strings: how to exploit their memory layout for O(1) index work, how to sweep through them efficiently with sliding windows and two‑pointer tricks, and how to perform in‑place reversals, rotations, and classic pattern matches without extra space. Each section includes concrete code, runtime analysis that ties back to the Big‑O concepts introduced earlier, and a real‑world example you might actually encounter on the job. --- 1. Constant‑Time Index Access & Updates Arrays (including strings, which are just immutable character arrays in most languages) give you direct addressing: the address of arr[i] is computed as baseaddress + i elementsize. Because of this, both reading and writing a single element are O(1) operations—no loops, no recursion. 1.1 When O(1) Matters | Situation | Why O(1) is critical | Typical interview twist | |-----------|----------------------|--------------------------| | Cache‑friendly look‑ups (e.g., LRU cache) | Random access must be fast to keep overall latency low | Combine an array with a hashmap to achieve O(1) get/put | | Frequent updates (e.g., stock price array) | Updating many entries each second cannot afford O(n) per update | Ask you to batch updates while preserving O(1) per element | | Bit‑masking on integer arrays | Bitwise tricks rely on constant‑time flips | Expect you to toggle a flag in O(1) using XOR | 1.2 Code Sketch (Python) Even in languages where strings are immutable (e.g., Java, Python), you can simulate O(1) updates by converting the string to a mutable list of characters, performing the change, then joining back. The conversion itself is O(n), but if you need many updates it’s cheaper to keep the mutable representation throughout. 1.3 Pitfalls & Edge Cases - Bounds checking adds a tiny constant factor but never changes the asymptotic class. - Sparse arrays (e.g., very large index ranges with few elements) waste memory; a hashmap may be preferable despite a slightly higher constant factor. --- 2. Sliding‑Window Technique for Subarray Problems The sliding window is the Swiss‑army knife for any problem that asks about contiguous sections of …
3. Linked Lists
A Playlist That Never Misses a Beat You’ve just been hired to build the core of a music‑streaming service. Users expect to add songs to the front, remove the current track, jump to the middle of the queue, and shuffle without copying the whole list. An array would give O(1) random access but every insertion or deletion costs O(n) because the underlying memory must shift. A linked list flips that trade‑off: constant‑time insertions/deletions at the ends and a modest O(n) traversal cost. Mastering linked lists is therefore a frequent interview theme—so let’s dive in. --- 1. Singly vs. Doubly Linked Lists | Feature | Singly Linked List | Doubly Linked List | |---------|-------------------|--------------------| | Node layout | value → next | prev ← value → next | | Memory per node | 1 pointer | 2 pointers | | Forward traversal | O(n) | O(n) | | Backward traversal | ✗ | O(n) | | Insert/delete at tail | O(n) (need previous) | O(1) (direct prev) | | Typical use‑case | Simple queues, stacks | LRU caches, bidirectional navigation | Both structures share the same asymptotic costs for most operations (see the Complexity Analysis chapter). The choice hinges on whether you need reverse navigation or are willing to pay the extra pointer cost. --- 2. Building the Building Blocks 2.1 Node Classes (Python) Why slots? It eliminates the per‑instance dict, shrinking each node’s footprint—an easy way to demonstrate awareness of space complexity. 2.2 List Classes For the doubly linked list we maintain both head and tail and update them symmetrically. Both classes expose the same public API (insert, delete, traverse) so you can swap implementations without changing client code—a principle you’ll see later in the Interview Problem‑Solving Framework. --- 3. Traversal Techniques 3.1 Iterative Traversal Complexity reminder: each yield is O(1); the loop runs n times, giving O(n) overall—exactly the same bound you met when scanning an array. 3.2 Recursive Traversal The recursive version trades space for readability: the call stack grows linearly with the list length. In an interview, you might be asked to convert this recursion to iteration (or vice‑versa) to demonstrate mastery of both perspectives. --- 4. Insertion & Deletion 4.1 At the Head A doubly linked list does the same but also sets newnode.prev = None and updates the old head’s prev pointer. 4.2 At the Tail Single list (without a stored tail) requires O(n) traversal to locate the last node. With a cached tail, insertion is O(1): For the doubly linked list we also set newnode.prev = self.tail. 4.3 In the Middle Insertion at an arbitrary index i (0 ≤ i ≤ n) proceeds by walking i‑1 steps, then splicing: A doubly linked list can …
4. Stacks and Queues
LIFO and FIFO: Core Abstractions When a customer adds an item to an online shopping cart, the system must remember the last item added so it can be removed first if the user clicks “undo”. Conversely, a call‑center queue must serve callers in the order they arrived. These two patterns—last‑in‑first‑out (LIFO) and first‑in‑first‑out (FIFO)—are the heart of stacks and queues. Both abstractions expose a tiny API: | Stack (LIFO) | Queue (FIFO) | |--------------|--------------| | push(x) – insert on top | enqueue(x) – insert at rear | | pop() – remove from top | dequeue() – remove from front | | peek() – read top element | front() – read front element | | isEmpty() | isEmpty() | | size() | size() | All operations should run in O(1) time, a guarantee we will keep by choosing the right underlying container. --- Implementing Stacks 1. Array‑backed Stack An array gives constant‑time index access, making push and pop trivial—just move a pointer (top). The only wrinkle is capacity: when the array fills, we allocate a larger one and copy elements (the classic dynamic array pattern you saw in the Arrays chapter). Complexity: each push/pop is amortized O(1) (the occasional resize costs O(n) but is spread over many operations). Space usage is Θ(n), where n is the number of stored elements. 2. Linked‑list Stack A singly linked list eliminates resizing entirely: each node holds a value and a pointer to the next node. The head of the list is the top of the stack. Complexity: all operations are O(1) worst‑case, and memory overhead is Θ(n) (each node stores a reference). No resizing means no hidden spikes in runtime—useful when interviewers stress worst‑case guarantees. --- Implementing Queues 1. Circular Buffer (Array Queue) A naïve array queue would shift all elements on each dequeue, yielding O(n) per operation. The trick is to treat the array as a ring: maintain two indices, front and rear, that wrap around using modulo arithmetic. Complexity: enqueue and dequeue are amortized O(1) (again because of occasional resizing). The ring eliminates the costly shift operation. 2. Linked‑list Queue A singly linked list with head (front) and tail (rear) pointers gives true O(1) worst‑case for both operations. Complexity: all operations are O(1) with Θ(n) space, no resizing overhead. --- Classic Stack Applications 1. Postfix (Reverse Polish) Expression Evaluation Postfix notation eliminates parentheses: 3 4 + 2 = (3 + 4) 2. The evaluation algorithm is a textbook stack use‑case: 1. Scan tokens from left to right. 2. If the token is an operand, push it. 3. If the token is an operator, pop the required number of operands, apply the operator, then push the result. 4. After the scan, the stack …
5. Recursion & Backtracking
A Puzzle That Stumped a Recruiter During a recent on‑site interview, a candidate was asked to list every possible way to arrange the letters of the word “CODE”. Within a minute she scribbled a handful of permutations, paused, and then produced a compact recursive routine that printed all 24 arrangements. The interviewer smiled—not because the problem was hard, but because the candidate thought recursively. That moment captures the essence of this chapter: mastering recursion and backtracking lets you turn exponential‑size search spaces into clear, interview‑ready solutions. --- 1. The Recursive Mindset 1.1 What “recursion” really means At its core, recursion is solving a problem by reducing it to a smaller instance of the same problem. The two ingredients are: 1. Base case – a condition that can be answered without further recursion. 2. Recursive case – a step that breaks the current instance into one or more strictly smaller sub‑instances and calls the same function on them. If you can picture the problem shrinking toward the base case, you’ve got the right mental model. 1.2 Visualizing a recursion tree A recursion tree is a diagram where each node represents a function call, and its children are the calls made from that node. Consider generating all binary strings of length k: The tree for k = 3 has 2³ = 8 leaves (the printed strings) and 2³‑1 = 7 internal nodes. Traversing the tree depth‑first yields the output order. 1.3 Deriving time and space from the tree Time complexity – sum the work done at each node. If each call does Θ(1) work and the tree has T(n) nodes, the total is Θ(T(n)). For the binary‑string generator, the tree is a perfect binary tree of height k, giving T(k) = 2^{k+1}‑1 = Θ(2^k). Hence the algorithm runs in O(2^k) time, matching the output size. Space complexity – determined by the deepest path (the recursion depth) plus any auxiliary data stored per call. The binary‑string generator’s depth is k, so the call stack uses Θ(k) space, i.e., O(k). This is a classic example of a linear auxiliary space despite exponential time. When you later analyze more elaborate backtracking algorithms, the same principles apply: draw the recursion tree, count nodes, and look at the longest root‑to‑leaf path. --- 2. Writing Clean Recursive Functions 2.1 Spotting the base case A base case often corresponds to an empty or singleton structure: | Problem | Typical base case | |---------|-------------------| | Factorial | n == 0 | | Linked‑list reversal | head is None | | Subset generation | index == len(nums) | If you can answer the question instantly for that case, you have a valid base case. 2.2 Ensuring progress toward the base Every …
6. Trees & Binary Search Trees
Why Trees Matter Imagine you are building a code‑completion engine for an IDE. Every time a programmer types a few characters, the engine must instantly suggest possible identifiers. Behind the scenes, the engine stores millions of words and needs to locate all entries that share a common prefix. A naïve linear scan of an array would be O(n) and far too slow for real‑time interaction. By arranging the words in a binary search tree (BST), each lookup becomes O(log n) on average, delivering the responsiveness developers expect. This chapter equips you with the tree fundamentals and BST operations that turn such ideas into production‑ready code. --- Tree Basics Nodes and Edges - Node – a container holding a value and references (pointers) to other nodes. - Edge – the link between two nodes, representing a parent‑child relationship. A tree is a connected, acyclic graph. The root is the unique node with no parent; every other node has exactly one parent. Nodes with no children are leaves. Binary Tree vs. General Tree - Binary tree – each node has at most two children, conventionally called left and right. - General (n‑ary) tree – a node may have any number of children. Binary trees are the foundation for most interview problems because they enable simple recursive algorithms and map cleanly to array‑based representations (e.g., heap). Representations | Representation | When to Use | Pros | Cons | |----------------|-------------|------|------| | Linked nodes (each node stores child pointers) | Dynamic structure, frequent inserts/deletes | Flexible, easy to modify | Extra memory for pointers | | Array (implicit) – e.g., heap stored in arr[i] | Complete or nearly‑complete trees | Cache‑friendly, no pointers | Wastes space for sparse trees | In this chapter we will work with the linked‑node representation, which aligns with the linked list concepts you already mastered. --- Implementing a Binary Tree Node Below are two idiomatic implementations: one in Python (leveraging its dynamic typing) and one in Java (showcasing explicit constructors). Python Java Both versions expose three fields: the stored value and two child references. The constructors let you create a leaf instantly or build larger sub‑trees in a single statement. --- Tree Traversals Traversals define the order in which a tree’s nodes are visited. They are the backbone of many algorithms—from printing a sorted list to evaluating arithmetic expressions. Recursive Traversals Recursive solutions exploit the self‑similarity of trees (a subtree is itself a tree). The time complexity of each traversal is O(n) because every node is visited exactly once; the auxiliary space is O(h), where h is the tree height (the call stack). 1. Pre‑order (Root → Left → Right) 2. In‑order (Left → Root → Right) Why in‑order matters …
7. Heaps & Priority Queues
Why Heaps Matter in Real‑Time Decision Making Imagine you are building a ride‑sharing platform that must constantly match drivers to riders in the most efficient way possible. Every incoming request carries a priority: the estimated time to pick up the passenger, the surge multiplier, the driver’s proximity, etc. The system needs to always surface the best match in a fraction of a millisecond, while simultaneously handling a flood of new requests. A naïve solution—scanning the entire list of pending rides each time—costs O(n) per match, which quickly becomes a bottleneck at scale. The data structure that turns this into a logarithmic operation is the heap, and its queue‑like façade, the priority queue. Mastering these tools unlocks fast top‑k queries, efficient scheduling, and the backbone of algorithms such as Dijkstra’s shortest‑path method. --- 1. Heap Fundamentals Revisited A heap is a complete binary tree that satisfies the heap property: - Max‑heap – every node’s key ≥ keys of its children. - Min‑heap – every node’s key ≤ keys of its children. Because the tree is complete, it can be stored compactly in an array without explicit node objects. For an element at index i (0‑based): | Relation | Formula | |----------|---------| | Parent | parent(i) = (i‑1) // 2 | | Left child | left(i) = 2i + 1 | | Right child | right(i) = 2i + 2 | This array representation lets us exploit the O(1) random access we already know from the Arrays chapter, while preserving the logarithmic height h = ⌊log₂ n⌋ that guarantees O(log n) percolation operations. 1.1 Visualizing the Structure Notice how the largest element (90) sits at the root—exactly the guarantee we need for fast retrieval. --- 2. Building a Heap from an Unsorted Array 2.1 Bottom‑Up Heapify (O(n) Construction) The most efficient way to turn an arbitrary array into a heap is heapify from the bottom up. Starting from the last internal node (⌊n/2⌋‑1) and moving backwards, we sift‑down each element to enforce the heap property. Why O(n)? Each siftdown call works on a subtree whose height is at most log₂ n. However, most nodes sit near the leaves, where the height is tiny. Summing the work across all nodes yields a linear bound—a classic result you may recall from the Complexity Analysis chapter. 2.2 Top‑Down Insertion (O(n log n) naïve) An alternative—insert each element one by one using the insert operation—produces a heap in O(n log n) time. While conceptually simple, it is slower than the bottom‑up approach and rarely used for bulk construction. --- 3. Core Heap Operations 3.1 Insert (push) – O(log n) 1. Append the new key at the end of the array (maintains completeness). 2. Sift‑up: while the …
8. Graphs & Traversals
A Real‑World Puzzle: Can You Find the Bottleneck in a City’s Metro Map? Imagine you’re tasked with improving a subway system that serves millions of commuters daily. The city planners hand you a diagram of stations (nodes) and the tracks that connect them (edges). They want to know: 1. Which stations are isolated from the rest of the network? 2. Are there any loops that could cause trains to circle forever? 3. Which stations, if closed for maintenance, would split the network into disconnected pieces? Answering these questions is a classic graph‑traversal problem. Mastering graph representations and the fundamental searches—DFS and BFS—gives you the tools to diagnose exactly these kinds of issues, and they appear repeatedly in tech interviews. --- 1. Graph Representations: Adjacency Lists vs. Matrices A graph \(G = (V, E\) ) consists of a set of vertices \(V\) and edges \(E\). The way we store this information determines the cost of common operations such as “what are the neighbors of u?” or “does an edge u‑v exist?”. 1.1 Adjacency Matrix | Feature | Description | |---|---| | Structure | A 2‑D \( |V| \times |V| \) boolean (or weight) array mat where mat[u][v] = 1 if edge u‑v exists. | | Space | \(O(|V|^2)\) – every possible pair of vertices occupies a cell, regardless of whether an edge is present. | | Edge Lookup | \(O(1)\) – direct index access. | | Neighbor Enumeration | \(O(|V|)\) – must scan an entire row/column. | | Best For | Dense graphs (|E| ≈ |V|²) or when constant‑time edge queries dominate. | 1.2 Adjacency List | Feature | Description | |---|---| | Structure | An array (or dict) adj where adj[u] holds a list of vertices adjacent to u. | | Space | \(O(|V| + |E|)\) – only existing edges consume memory. | | Edge Lookup | \(O(k)\) where k is the degree of u (worst‑case \(O(|V|)\)). | | Neighbor Enumeration | \(O(k)\) – directly iterate over the stored list. | | Best For | Sparse graphs (|E| ≪ |V|²) and algorithms that need to traverse neighbors frequently. | 1.3 Choosing the Right Representation - If the interview problem mentions “up to 10⁵ vertices and only 10⁶ edges,” an adjacency list is almost always the right choice because the matrix would need ~10¹⁰ cells—far beyond memory limits. - If the problem asks for “quickly test whether two stations are directly connected,” a matrix shines, provided the graph is dense enough to justify the space. Remember the Big‑O analysis from the Complexity Analysis chapter: the asymptotic cost of each operation guides you toward the most efficient representation for the given constraints. --- 2. Depth‑First Search (DFS) DFS explores a graph by …
9. Sorting & Searching Algorithms
A Real‑World Hook: The “Almost Sorted” Log File Imagine you’re on‑call for a large e‑commerce site. Every hour a 2 GB log file lands on your server, already sorted by timestamp but with a few out‑of‑order entries caused by clock drift on edge nodes. Your task: produce a clean, chronologically ordered view for the analytics team within seconds. The solution will hinge on choosing the right sorting algorithm and possibly a binary‑search‑based lookup for the out‑of‑order pieces. This scenario forces you to weigh time, space, and stability—the exact trade‑offs we’ll explore throughout this chapter. --- Quick Reference: Classic Comparison Sorts | Algorithm | Average Time | Worst‑Case | Extra Space | Stable? | In‑Place? | |-------------|--------------|------------|-------------|---------|-----------| | Quicksort | O(n log n) | O(n²) (rare with good pivot) | O(log n) recursion stack | No (standard) | Yes | | Mergesort | O(n log n) | O(n log n) | O(n) auxiliary array | Yes | No (unless clever in‑place variant) | | Heapsort | O(n log n) | O(n log n) | O(1) (uses the input array) | No | Yes | All three follow the divide‑and‑conquer paradigm introduced in earlier chapters on recursion and backtracking. --- Quicksort 1. The Partition Step The heart of quicksort is partitioning—rearranging a sub‑array so that every element ≤ pivot lies left of it, and every element pivot lies right. Two common schemes: | Scheme | Description | |--------|-------------| | Lomuto | Uses the last element as pivot; scans with a i index, swapping when a smaller element is found. Simpler but does more swaps. | | Hoare | Picks a pivot (often the middle element), moves two indices inward from both ends, swapping out‑of‑place elements. Fewer swaps, works well with duplicate keys. | Both achieve the same logical split; the choice affects constant factors and stability (neither is stable). 2. Recursive Implementation (Lomuto) Complexity analysis draws directly from the divide‑and‑conquer pattern: each level processes O(n) work, and the depth is O(log n) on average, yielding O(n log n) total time. The recursion stack contributes O(log n) extra space—still regarded as in‑place because no auxiliary array proportional to n is allocated. 3. Stability Standard quicksort swaps elements freely, so equal keys can change relative order. A stable quicksort can be built by: - Using extra memory for a temporary buffer (turning it into a hybrid of quicksort & mergesort), or - Modifying the comparison to treat equal keys as “less than” when they appear earlier (adds overhead). In most interview settings, you’ll be asked to state that quicksort is not stable and to discuss how to make it stable if required. --- Mergesort 1. Top‑Down Recursive Version The recursive calls split the array …
10. Dynamic Programming & Greedy Algorithms
When “Guess‑and‑Check” Isn’t Enough You’ve just landed a software‑engineering interview. The interviewer slides a suitcase onto the table, a list of items with weights and values, and asks: “What’s the maximum value you can fit into a suitcase that holds 15 kg?” A quick glance suggests a greedy approach—pick the most valuable items first. Yet, a moment later you realize that the optimal solution may require skipping a high‑value, heavy item in favor of several lighter ones. The same tension appears in problems like “What’s the shortest way to transform one word into another?” or “How many ways can you climb a staircase with 1‑ or 2‑step moves?” These questions are the hallmark of dynamic programming (DP) and greedy algorithms—the two most powerful tool‑kits for interview‑style optimization problems. This chapter shows how to spot them, formulate them, and decide which strategy wins. --- 1. The DP Mindset: Overlapping Subproblems & Optimal Substructure A problem is a good DP candidate when it satisfies two properties: 1. Overlapping subproblems – the same sub‑problem is solved many times during a naïve recursive exploration. 2. Optimal substructure – an optimal solution to the whole problem can be assembled from optimal solutions to its sub‑problems. Think back to the recursion & backtracking chapter: a naïve recursive solution often recomputes identical states (e.g., Fibonacci). DP eliminates this redundancy. 1.1 Recognizing Overlap | Situation | Indicator | |-----------|------------| | Recursive tree has many repeated nodes | Yes – memoization will prune them | | Each recursive call works on a new input segment | No – DP likely unnecessary | 1.2 Verifying Optimal Substructure Ask: If I know the best answer for a smaller instance, can I extend it to solve the larger one? If the answer is “yes” and the extension rule is simple (add a value, choose a branch, etc.), you have a DP formulation. --- 2. From Naïve Recursion to Efficient DP 2.1 Memoization (Top‑Down) 1. Write the plain recursive solution. 2. Create a cache (hash map or array) keyed by the sub‑problem’s state. 3. Before recursing, check the cache; if present, return the stored value. Complexity impact – The cache guarantees each distinct state is computed once, turning an exponential‑time recursion into a polynomial one. Use the same Big O analysis tools from the first chapter to quantify the gain. Example: Staircase Climbing Recursive definition: ways(i) = ways(i‑1) + ways(i‑2) with base cases ways(0)=1, ways(1)=1. Memoizing ways(i) yields O(n) time and O(n) space. 2.2 Tabulation (Bottom‑Up) 1. Identify the order in which sub‑problems must be solved (usually from smallest to largest). 2. Allocate a table (array, matrix) and fill it iteratively. 3. Derive the answer from the final table entry. Tabulation often reduces …
11. Interview Problem‑Solving Framework
1. Decode the Prompt – What Is the Interview Really Asking? A well‑crafted interview question hides three layers: | Layer | What to look for | Typical clue | |-------|------------------|--------------| | Goal | The final output or decision | “Return the length of the longest …” | | Input | Data structure(s) and size limits | “Given an array of n integers …” | | Constraints | Time, space, ordering, uniqueness, mutability | “Must run in O(n log n) or better” | Step‑by‑step drill‑down 1. Read the whole statement once – ignore details, just get the high‑level picture. 2. Identify the what and the why – e.g., “find the minimum number of rooms required so that no meetings overlap.” 3. Extract the how (constraints) – size of n, range of values, allowed operations, required complexity. 4. Rewrite the problem in your own words on a whiteboard or notebook. This forces you to internalize the goal and often reveals hidden edge cases. Real‑world example 1 – Log‑File Anomaly Detection Prompt: “Given a chronologically ordered list of timestamps (in seconds) from a server log, return the smallest interval that contains at least k error entries.” Decomposition: • Goal – shortest interval length (integer). • Input – sorted array of timestamps, integer k. • Constraints – n up to 10⁶, must be O(n) time, O(1) extra space. By forcing yourself to articulate the three layers, you eliminate ambiguity before you ever write code. --- 2. Map Constraints to Data‑Structure Choices Every constraint points you toward a family of structures you’ve already mastered: | Constraint | Ideal structure(s) | Reason | |------------|-------------------|--------| | O(1) look‑up by key | Hash map (dictionary) | Constant‑time access. | | Ordered traversal needed | Balanced BST, Heap, or Sorted array | Guarantees O(log n) insert/remove while preserving order. | | Frequent prefix/suffix queries | Prefix sum array, Trie | Pre‑processing enables O(1) or O(log n) queries. | | Sub‑array or sub‑string sliding window | Two‑pointer technique on Array | Linear scan with constant extra space. | When you spot a constraint, immediately note a candidate structure. This “constraint‑to‑structure” table becomes a mental checklist you can run through in seconds. --- 3. From Brute‑Force to Optimized – Iterative Refinement 3.1 Sketch the Naïve Solution 1. Write a literal translation of the problem using the most straightforward constructs (nested loops, repeated scans). 2. Analyze its complexity using the Big‑O tools you already know (outer loop, inner loop, cost per iteration). 3. Identify the bottleneck – which part of the algorithm dominates the runtime or space. Example: For the “minimum interval with k errors” problem, a naïve approach would examine every pair of timestamps, compute the interval length, and keep the …
Continue learning
- Data Structures and Algorithms for Tech InterviewsData Structures and 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....