Dsa Anki Deck

This deck is a foundational introduction to Data Structures and Algorithms (DSA), the building blocks of computer science and software engineering. It walks you through core concepts like Big O Notation, time and space complexity, and then moves into the essential data structures such as arrays, linked lists, stacks, queues, and trees. Each card is designed to reinforce a single idea, making it easier to build a strong mental model of how data is organized and manipulated.

The deck is well suited for students preparing for coding interviews, learners enrolled in a computer science or programming course, or anyone who wants to strengthen their problem-solving skills. Even if you have some programming experience, going through these cards helps you lock in the vocabulary and distinctions that come up constantly in technical discussions, such as the difference between an array and a linked list, or between a binary tree and a balanced AVL tree.

To get the most out of this deck, try reviewing a small batch of cards each day rather than cramming everything at once. Spaced repetition works best when you give your brain time to forget and then recall the material, so even 15 to 20 minutes a day will add up quickly. As you work through the cards, pause after each one and try to think of a real example or use case, since connecting a concept to a familiar scenario makes it far easier to remember later.

A data structure is a particular way of organizing data in a computer so that it can be used effectively, while an algorithm is a step-by-step procedure that defines a set of instructions to be executed in a certain order to produce the desired output. Together, these two concepts form the backbone of computer science, since the choice of data structure profoundly affects the efficiency of any algorithm that operates on it. To reason about efficiency, we use Big O notation, which describes the upper bound of an algorithm's time complexity and represents its worst-case scenario. Time complexity measures the amount of time an algorithm takes to run as a function of the input length, while space complexity measures the working storage it requires. Amortized analysis, a complementary technique, considers the average cost of an operation over a sequence of operations rather than the worst-case cost of a single one, which is especially useful for structures like dynamic arrays. The Master Theorem provides a direct solution for recurrence relations of the form \(T(n) = aT(n/b) + f(n)\), which commonly arise in divide-and-conquer analyses.

The simplest and most widely used data structures are linear collections. An array stores multiple items of the same type at contiguous memory locations, enabling fast random access but at the cost of a fixed size. A linked list, by contrast, stores elements at non-contiguous memory locations connected via pointers, giving it dynamic size and easier insertions and deletions, though it sacrifices fast indexed access. Several linked list variants exist: a doubly linked list contains both a previous and next pointer, a circular linked list forms a closed ring with no NULL end, an XOR linked list stores the XOR of two pointers to save space, and an unrolled linked list stores an array of elements in each node to improve cache locality. A dynamic array, supplied as a standard library in most modern languages, simulates the convenience of a variable-size list while preserving the random-access performance of contiguous storage. The Iterator pattern decouples traversal logic from the underlying container, allowing different data structures to be enumerated uniformly.

Beyond general-purpose lists, two specialized linear structures dictate the order of operations. A stack follows LIFO (Last In First Out) or FILO (First In Last Out) order, supporting the main operations Push (add an item), Pop (remove an item), Peek or Top (view the top item), and isEmpty (check whether it is empty). A queue follows FIFO (First In First Out) order, with Enqueue (add an item), Dequeue (remove an item), Front (get the first item), and Rear (get the last item) as its primary operations. A priority queue is an extension of the queue in which every item carries a priority, so that an element with high priority is dequeued before one with low priority. These structures underpin the management of function calls, breadth-first search, scheduling, and many other computational tasks, making them essential building blocks for more sophisticated algorithms.

A binary tree is a tree data structure in which each node has at most two children, referred to as the left and right child. A binary search tree (BST) imposes an ordering constraint: every node in the left subtree holds a value less than the parent, and every node in the right subtree holds a value greater. This ordering makes searching, insertion, and deletion efficient, but in the worst case a BST degenerates into a linear chain. To prevent this, self-balancing variants such as the AVL tree and the red-black tree enforce structural invariants. An AVL tree requires that the difference between the heights of the left and right subtrees of any node is at most one. A red-black tree, by contrast, colors every node red or black and obeys five properties: every node is red or black, the root is black, every NULL leaf is black, red nodes have black children, and every path from a node to its descendant leaves contains the same number of black nodes. Other advanced BST variants include the splay tree, which moves recently accessed elements to the root through a splaying step, and the treap, which combines a BST property on keys with a heap property on randomly assigned priorities.

Beyond search trees, several specialized tree structures serve other needs. A heap is a complete binary tree used as a priority container, with the min-heap and max-heap variants enforcing parent-child ordering by value. A B-tree is a self-balancing, generalized search tree in which each internal node may have more than two children, allowing it to maintain sorted data and provide logarithmic-time searches, sequential access, insertions, and deletions, which is why it is widely used in databases and filesystems. A B+ tree refines this design by storing all data in the leaf nodes and using internal nodes purely for indexing, with leaves typically linked for fast sequential access. A trie, also called a digital or prefix tree, is a search tree used for locating keys, especially strings, by traversing character by character along the path determined by each digit or letter.

Many other tree structures target specific query patterns. A segment tree stores information about intervals or segments, allowing range queries such as which stored segments contain a given point to be answered efficiently. A Fenwick tree, also called a binary indexed tree, supports efficient element updates and prefix-sum queries in a table of numbers. Spatial data is often organized using a quadtree, which recursively subdivides a two-dimensional space into four quadrants, an octree, which does the same for three-dimensional space using eight octants, an R-tree, which indexes multi-dimensional information such as geographical coordinates, rectangles, or polygons, or a k-d tree, a space-partitioning binary search tree for points in a k-dimensional space. Less common but still important structures include the expression tree, which represents expressions with operands as leaves and operators as internal nodes; the Cartesian tree, which is heap-ordered with an in-order traversal matching the original sequence; the threaded binary tree, which uses empty child pointers to speed up in-order traversal without recursion or a stack; the Van Emde Boas tree, which implements an associative array with integer keys and runs all operations in \(O(\log \log M)\) time, where M is the universe size; the rope, which efficiently stores and manipulates very long strings; the persistent data structure, which preserves previous versions of itself when modified; and the Judy array, a fast cache-friendly associative array for integers or strings. To walk through any of these structures, four standard binary tree traversals are available: inorder (Left, Root, Right), preorder (Root, Left, Right), postorder (Left, Right, Root), and level order, which is simply a breadth-first traversal of the tree.

A hash table stores data in an associative manner, arranging values in an array format where each data value has its own unique index. Hashing is the process of converting a given key into a numeric value that is then used as that index. When two different keys hash to the same index, a collision occurs. Collisions are commonly resolved in two broad ways: chaining, which stores a linked list of all colliding entries at that index, and open addressing, which probes for another available slot using linear probing, quadratic probing, or double hashing. Beyond standard hash tables, consistent hashing is a technique that minimizes the number of keys that must be remapped when a hash table is resized, making it especially valuable in distributed systems where servers may be added or removed dynamically. Universally Unique Identifiers (UUIDs) and Globally Unique Identifiers (GUIDs) are 128-bit labels that, in the context of data structures and algorithms, are used as keys where collision probability must be negligible even without central coordination.

Several data structures extend hashing into the realm of probabilistic answers, where absolute accuracy is traded for significant savings in space or query time. A Bloom filter is a space-efficient probabilistic structure that tests set membership: false positive matches are possible, but false negatives are not, so if the filter reports that an element is not in the set, it definitely is not. A cuckoo filter is a related probabilistic structure that supports dynamic addition and removal of items and achieves higher space efficiency than a Bloom filter. A skip list is a probabilistic alternative to balanced trees that provides \(O(\log n)\) search and insertion within an ordered sequence by using multiple levels of linked lists with random promotion. A disjoint set, also called a union-find or DSU, is a data structure that tracks elements partitioned into disjoint subsets, providing near-constant-time operations (bounded by the inverse Ackermann function) for adding sets, merging them, and testing whether two elements are in the same set, with Find determining the subset of an element and Union joining two subsets.

More specialized probabilistic structures support streaming, similarity, and spatial computations. HyperLogLog is an algorithm that approximates the number of distinct elements in a multiset using very little memory, making it a workhorse for count-distinct problems in big data. Count-Min Sketch is a probabilistic frequency table of events in a stream that uses hash functions to map events to frequencies; because multiple events may collide, it can overestimate counts. MinHash is a technique for quickly estimating the Jaccard similarity coefficient between two sets. Geohashing is a public domain geocode system that encodes a geographic location into a short hierarchical string of letters and digits; compared to a quadtree, a geohash effectively linearizes the 2D grid into a string and is often implemented using Z-order curves, which are related to quadtree decomposition. To support efficient range updates, a difference array allows range updates in \(O(1)\) time, with the actual array reconstructed via a prefix sum. For range queries on static arrays, a sparse table answers queries like Range Minimum Query in \(O(1)\) after \(O(n \log n)\) preprocessing. Square root decomposition divides an array into blocks of size \(\sqrt{n}\) to reduce query time to \(O(\sqrt{n})\), and Mo's algorithm extends this idea to offline range queries by sorting queries to minimize pointer movement. Heavy-light decomposition and centroid decomposition are two complementary techniques for decomposing a tree into paths or recursively splitting it at centroids to enable efficient path and subtree queries.

A graph is a non-linear data structure consisting of nodes, also called vertices, and edges that connect pairs of vertices. Two principal ways exist to represent a finite graph in memory: an adjacency matrix is a square matrix whose entries indicate whether pairs of vertices are adjacent, while an adjacency list is a collection of unordered lists where each list describes the set of neighbors of one vertex. Several specialized graph types also appear in practice: a directed acyclic graph (DAG) has no directed cycles and forms the basis of topological sorting, a forest is a disjoint union of trees in which any two vertices are connected by at most one path, a multigraph permits multiple edges between the same pair of vertices, a hypergraph generalizes the edge to connect any number of vertices, and a planar graph can be drawn in the plane with no crossing edges, a property captured by Euler's formula \(v - e + f = 2\) for a connected planar graph with v vertices, e edges, and f faces. Graph decomposition, the process of breaking a graph into subgraphs such as connected components, biconnected components, or strongly connected components, often simplifies analysis and solution design.

The two foundational traversal algorithms for graphs are breadth-first search (BFS) and depth-first search (DFS). BFS starts at a source node and explores the graph layer by layer, visiting all neighbors of the current depth before moving to the next. DFS starts at a chosen root and explores as far as possible along each branch before backtracking. A spanning tree of a graph is a subset of edges that covers all vertices with the minimum possible number of edges, contains no cycles, and is connected; a minimum spanning tree (MST) further minimizes the total edge weight. Two classical greedy algorithms find an MST: Prim's algorithm grows a single tree by repeatedly adding the cheapest edge that connects the tree to a new vertex, while Kruskal's algorithm picks the edge of least possible weight that connects any two trees in the forest. For shortest paths, Dijkstra's algorithm finds shortest paths from a source in a graph with non-negative weights, the Bellman-Ford algorithm handles graphs with negative edge weights (though not negative-weight cycles) and is improved by SPFA, the Shortest Path Faster Algorithm, which works well on random sparse graphs but has worst-case exponential behavior. Floyd-Warshall solves the all-pairs shortest path problem, and Johnson's algorithm finds all-pairs shortest paths while allowing negative edge weights but no negative-weight cycles, using Dijkstra with reweighted edges. A* search is a graph traversal and path search algorithm that is complete, optimal, and optimally efficient when guided by an admissible heuristic.

Beyond traversal and shortest paths, graphs admit a rich collection of structural and combinatorial algorithms. Topological sorting of a DAG produces a linear ordering of vertices such that for every directed edge \(u \to v\), u appears before v; Kahn's algorithm implements this by repeatedly removing nodes with zero in-degree. The strongly connected components (SCCs) of a directed graph can be found in linear time by either Tarjan's algorithm, which uses DFS together with discovery times and low-link values, or Kosaraju's algorithm, which performs two passes of DFS. An articulation point, or cut vertex, is a vertex whose removal disconnects the graph, while a bridge is an edge whose removal disconnects it. Maximum flow problems are solved by the Ford-Fulkerson algorithm, which uses DFS or BFS to find augmenting paths; the Edmonds-Karp algorithm is an implementation that uses BFS and runs in \(O(VE^2)\) time; Dinic's algorithm improves on this by using level graphs and blocking flows; and the push-relabel algorithm is generally even more efficient. The Max-Flow Min-Cut theorem states that the maximum flow from source to sink equals the capacity of the minimum cut. Matching problems include maximum bipartite matching, solved efficiently by the Hopcroft-Karp algorithm in \(O(E\sqrt{V})\) time, and the stable marriage problem, which finds a stable matching between two equally sized sets given each element's preferences. An Eulerian path visits every edge exactly once, and a Hamiltonian path visits every vertex exactly once. Graph coloring assigns labels to vertices so that no two adjacent vertices share a label, and the chromatic number is the smallest number of colors required. In computational geometry, the convex hull of a set of points is the smallest convex polygon containing them, Graham scan finds it in \(O(n \log n)\) time, and line intersection seeks the intersection points of lines or line segments. Finally, 2-SAT, the satisfiability problem where each clause has exactly two literals, can be solved in linear time using strongly connected components.

Searching is one of the most fundamental algorithmic tasks. Linear search examines every item one by one, giving a time complexity of \(O(n)\). Binary search repeatedly divides a sorted array's search interval in half, achieving a time complexity of \(O(\log n)\) but requiring sorted input. Interpolation search improves on binary search for uniformly distributed sorted arrays by guessing where the key likely resides based on its value, while exponential search enables binary search on a sorted, unbounded list by first determining a bracketing range in exponential steps. Ternary search is a divide-and-conquer algorithm that locates the maximum or minimum of a unimodal function by dividing the search space into three parts. For the more specialized task of finding the kth smallest element in an unordered list, QuickSelect is related to quicksort and has an average time complexity of \(O(n)\). The Boyer-Moore majority vote algorithm finds an element appearing more than \(n/2\) times in \(O(n)\) time and \(O(1)\) space, and Kadane's algorithm finds the maximum sum of a contiguous subarray in linear time. For spatial problems, flood fill is an algorithm that determines the area connected to a given node in a multi-dimensional array, classically used in the bucket fill tool of paint programs, and the Lee algorithm is a possible solution for maze routing problems that always gives an optimal solution if one exists, at the cost of being slow and memory intensive.

Sorting algorithms arrange data in a particular order, typically numerical or lexicographical, and they fall into comparison-based and non-comparison-based families. Bubble sort repeatedly swaps adjacent elements that are out of order, with a best case of \(O(n)\) when the array is already sorted. Selection sort selects the smallest unsorted element in each iteration and places it at the front. Insertion sort builds the final sorted array one item at a time, and Shell sort is a variation that allows exchanges of far-apart elements to reduce the number of movements. Merge sort is a divide-and-conquer algorithm that splits the input in half, recursively sorts each half, and merges them, achieving \(O(n \log n)\) in all three cases. Quick sort is also divide-and-conquer, choosing a pivot and partitioning the array around it, with a worst case of \(O(n^2)\) typically when the input is sorted or reverse-sorted and the pivot is chosen poorly. Heap sort uses a heap to repeatedly extract the maximum element into the sorted region.

Non-comparison-based sorts and hybrid sorts fill out the landscape. Counting sort counts objects with distinct key values, hashing-like, and works when keys fall within a specific range. Radix sort is non-comparative and distributes elements into buckets according to their radix, repeating the bucketing process for each digit while preserving prior ordering. Bucket sort is most useful when input is uniformly distributed over a range, such as floating-point numbers in \([0.0, 1.0)\). Cycle sort is an in-place, unstable comparison sort that is theoretically optimal in the total number of writes to the original array. Modern languages rely heavily on hybrid sorts: TimSort, used as the standard sort in Python and Java, combines merge sort and insertion sort to perform well on real-world data, and Introsort begins with quicksort, switches to heapsort when recursion depth exceeds a threshold, and finishes small subarrays with insertion sort, providing both fast average and optimal worst-case performance. Beyond sorting and searching, classical number-theoretic algorithms include the Sieve of Eratosthenes for finding all primes up to a given limit, the Euclidean algorithm for computing the greatest common divisor of two integers, and modular exponentiation, which performs exponentiation over a modulus and is fundamental to public-key cryptography. The Fast Fourier Transform computes the discrete Fourier transform in \(O(n \log n)\) rather than \(O(n^2)\), Catalan numbers enumerate many recursive structures such as valid parenthesis sequences and full binary trees, and reservoir sampling draws a simple random sample of k items from a population of unknown size in a single pass. Cycle detection in linked lists is performed by Floyd's Tortoise and Hare algorithm, with Brent's algorithm providing a generally faster alternative of the same worst-case complexity, and Gaussian elimination solves systems of linear equations and computes ranks, determinants, and inverses of matrices.

Several recurring paradigms underlie the design of efficient algorithms. Recursion is the process in which a function calls itself as a subroutine, while iteration uses a loop to repeat a process; recursion can be more memory intensive because of call-stack overhead. Dynamic programming is a paradigm that solves a complex problem by breaking it into overlapping subproblems and storing their results to avoid recomputation, and it can be expressed either through memoization, a top-down approach that caches function call results, or through tabulation, a bottom-up approach that fills a table iteratively. A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Divide and conquer solves a problem in three steps: Divide, Conquer, and Combine. Backtracking incrementally builds a solution piece by piece, abandoning and removing partial solutions that fail to satisfy the problem's constraints. Branch and bound is a paradigm for discrete and combinatorial optimization that systematically enumerates candidate solutions through state space search, while meet-in-the-middle divides the search space into two roughly equal parts, searches each part separately, and combines results, often reducing exponential complexity from \(O(2^n)\) to \(O(2^{n/2})\).

Beyond these classical paradigms, several widely used patterns simplify specific problem classes. The two pointers technique uses two pointers that iterate through a data structure in tandem until one or both hit a stopping condition, and the sliding window technique performs an operation on a contiguous window of an array or linked list, such as finding the longest subarray containing all ones. Convex hull trick is a geometry-based optimization for DP transitions involving linear functions, often reducing complexity from \(O(n^2)\) to \(O(n \log n)\) or \(O(n)\). Binary lifting is a dynamic programming approach used to find the kth ancestor of a tree node or to compute the lowest common ancestor, the deepest node that has both v and w as descendants, efficiently in \(O(\log n)\) time. Huffman coding, which uses variable-length codes assigned to characters based on their frequencies for lossless data compression, and the A* algorithm, which combines graph traversal with a heuristic to achieve optimal pathfinding, often appear as building blocks in larger algorithmic systems. Classical number-theoretic tools such as the Sieve of Eratosthenes, the Euclidean algorithm, and modular exponentiation, along with the Fast Fourier Transform and Catalan numbers, are recurring primitives across many paradigms.

Many canonical optimization problems showcase how the paradigms interact. The knapsack problem asks for the subset of items, each with a weight and a value, that maximizes total value without exceeding a weight limit; in 0/1 knapsack items cannot be broken, while in fractional knapsack items can be split. The longest common subsequence problem finds the longest subsequence common to two or more sequences, the longest increasing subsequence problem finds the longest strictly increasing subsequence of a given sequence, the matrix chain multiplication problem determines the most efficient parenthesization of a chain of matrix multiplications, and the edit distance, or Levenshtein distance, between two strings is the minimum number of insertions, deletions, and substitutions needed to transform one into the other. Other classic problems include the traveling salesman problem, which asks for the shortest route that visits every city exactly once and returns to the origin, the vertex cover problem, which finds the smallest set of vertices such that every edge is incident to at least one chosen vertex, the set cover problem, which finds the smallest sub-collection of sets whose union equals the universe, and the clique problem, which finds a subset of vertices in which every pair is adjacent, with the maximum clique variant being NP-hard. Together these paradigms and problems illustrate how the same fundamental ideas reappear across diverse problem domains.

String matching is a deep subfield with its own family of algorithms. The Knuth-Morris-Pratt algorithm searches for occurrences of a word W within a text S by exploiting the structure of the pattern itself, so that when a mismatch occurs, the word embodies enough information to determine where the next match could begin. The Rabin-Karp algorithm uses hashing to find any one of a set of pattern strings in a text, achieving average and best case \(O(n+m)\) but worst case \(O(nm)\). The Z-algorithm is a linear-time string matching algorithm that constructs a Z-array whose entry at position i is the length of the longest common prefix between the string and its suffix starting at i, while the Aho-Corasick algorithm constructs a finite state machine from a set of pattern strings and locates all occurrences of any of them in a text. Manacher's algorithm finds the longest palindromic substring of a string in linear time \(O(n)\), and the Boyer-Moore string search algorithm efficiently skips sections of the text using two heuristics: the bad character rule and the good suffix rule. For more complex queries on texts, a suffix tree is a compressed trie of all suffixes of a string and is a powerful structure for problems like pattern matching and longest repeated substring, while a suffix array is a sorted array of all suffixes and offers a more space-efficient alternative.

Beyond exact matching, several measures quantify the similarity or distance between sequences and other objects. The Levenshtein distance, or edit distance, counts the minimum number of insertions, deletions, and substitutions to transform one string into another, while the Hamming distance only allows substitutions and requires strings of equal length. Jaccard similarity measures the similarity between two sets as the size of their intersection divided by the size of their union, and cosine similarity measures the similarity between two non-zero vectors as the cosine of the angle between them. For geometric points, Euclidean distance is the straight-line distance between two points, and Manhattan distance is the distance measured along axes at right angles in a grid-like fashion. In data compression, Huffman coding assigns variable-length codes to input characters based on their frequencies, while arithmetic coding encodes the entire message into a single number in \([0, 1)\) and is generally more efficient but more complex. Run-length encoding stores runs of identical values as a single value and count, and the Burrows-Wheeler Transform rearranges a string into runs of similar characters as a preprocessing step for compression algorithms like bzip2. At the lowest level, bit manipulation algorithmically manipulates bits using the operators AND (&), OR (|), XOR (^), NOT (~), Left Shift (<<), and Right Shift (>>).

Underneath all of these algorithms lies a theoretical framework of complexity and a layer of systems concerns. The complexity class P contains decision problems solvable by a deterministic Turing machine in polynomial time, while NP contains problems verifiable in polynomial time. A problem is NP-complete if it is in NP and every other problem in NP can be reduced to it in polynomial time, making these the hardest problems in NP. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time, but it need not itself be in NP. Probabilistic and randomized algorithms come in two main flavors: Monte Carlo algorithms may produce an incorrect result with small probability, and running them more times reduces that error, while Las Vegas algorithms always produce a correct result, but their running time is a random variable. In game theory and AI, the minimax algorithm minimizes the possible loss for a worst case, and alpha-beta pruning decreases the number of nodes evaluated by minimax. Cache replacement policies include LRU, which discards the least recently used item first, and LFU, which discards the least frequently used item. The CAP theorem states that a distributed data store can simultaneously provide only two of Consistency, Availability, and Partition Tolerance. Database durability and atomicity are commonly ensured by write-ahead logging, in which modifications are written to a log before being applied to the main database, and by shadow paging, which maintains a current and a shadow page table and switches them at commit. The simplex algorithm is a popular method for linear programming that moves along the edges of the feasible region, a polytope, to find the optimal solution. In concurrent systems, a race condition occurs when threads access shared data concurrently with results depending on execution order, a deadlock occurs when each process holds a resource and waits for one held by another, and a livelock is similar but the states of the processes constantly change without any progressing. Synchronization primitives include a mutex, which is a locking mechanism allowing only one owner, and a semaphore, which is a signaling mechanism permitting N simultaneous accesses. Compare-And-Swap is an atomic instruction that compares a memory location to an expected value and only updates it if they match, but it can suffer from the ABA problem when a value changes from A to B and back to A. False sharing occurs when threads on different processors modify variables that share a cache line. At the hardware level, branch prediction guesses the direction of a branch to keep the instruction pipeline full, and endianness describes the byte order in a word: big-endian stores the most significant byte at the smallest address, and little-endian stores the least significant. Finally, mark and sweep is a two-phase garbage collection algorithm that first marks all reachable objects and then sweeps away unmarked ones, completing the bridge from pure algorithmic theory to the systems in which those algorithms run.