Data Structures & Algorithms
A structured approach to mastering coding interviews. We've categorized the most important problems into clear patterns, complete with optimal solutions in Java and Python.
Arrays & Hashing
Arrays are the simplest and most common data structure. Hashing (Hash Maps and Hash Sets) provides O(1) average time complexity for lookups, making it an essential tool for optimizing array problems.
Two Pointers
The Two Pointers pattern involves using two indices to traverse an array or string, often from opposite ends or moving at different speeds. It's highly effective for finding pairs or subarrays, especially in sorted data.
Sliding Window
The Sliding Window pattern is used to perform operations on a specific window size of an array or string. The window can be of fixed size or dynamically resizable, expanding or shrinking based on specific conditions.
Stack
A Stack operates on a Last-In-First-Out (LIFO) principle. It is extremely useful for problems involving parsing, tracking state that needs to be reversed, or maintaining a monotonic property (like finding the next greater element).
Binary Search
Binary Search is a highly efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, reducing the time complexity to O(log n).
Linked List
A Linked List is a linear data structure where elements are stored in nodes, and each node points to the next. Problems often involve manipulating these pointers (e.g., reversing, merging, or detecting cycles using fast and slow pointers).
Trees
A Tree is a hierarchical data structure consisting of nodes. Binary Trees (and Binary Search Trees) are incredibly common in technical interviews. Solutions usually heavily rely on recursion and Depth-First Search (DFS) or Breadth-First Search (BFS).
Tries
A Trie (pronounced "try"), or prefix tree, is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. It is highly effective for tasks like autocomplete, spell checking, and finding words in a grid.
Heap / Priority Queue
A Heap (or Priority Queue) is a specialized tree-based data structure that satisfies the heap property: the parent node is either greater than or equal to (Max Heap) or less than or equal to (Min Heap) its children. It's ideal for problems asking for the "Top K", "Kth largest/smallest", or "Median" elements.
Backtracking
Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. It builds candidates for the solution and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Graphs
A Graph is a non-linear data structure consisting of vertices and edges. These problems often require traversal techniques like Depth-First Search (DFS) or Breadth-First Search (BFS) to explore nodes and relationships.
Advanced Graphs
Advanced graph algorithms involve more complex scenarios such as finding the shortest path with weights (Dijkstra's, Bellman-Ford), minimum spanning trees (Prim's, Kruskal's), or topological sorting. These problems often require combinations of data structures like priority queues and hash maps.
1-D Dynamic Programming
1-D Dynamic Programming involves solving optimization problems by breaking them down into simpler subproblems and storing the results of these subproblems in a 1-dimensional array (or just using a few variables to save space) to avoid redundant computations.
2-D Dynamic Programming
2-D Dynamic Programming involves solving optimization problems by breaking them down into simpler subproblems and storing the results of these subproblems in a 2-dimensional array. This is common for problems involving grids, matrices, or comparing two strings/arrays.
Greedy
Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. This strategy often yields optimal solutions for problems like jump games, scheduling, or partitioning, where local optimization leads to global optimization.
Intervals
Interval problems often involve merging, inserting, or finding overlaps among a set of intervals (typically represented as pairs of start and end times). Sorting the intervals by start or end time is usually the key first step.
Math & Geometry
Math and Geometry problems often require mathematical insights, handling numbers digit by digit, or simulating geometrical transformations on a matrix or 2D plane.
Bit Manipulation
Bit manipulation involves operating on the bit-level representation of numbers. These techniques are often used for optimization, checking parity, or finding missing/duplicate elements using properties like XOR.