250 Data Structures & Algorithms Flashcards for Memly
In this subject, speed comes from knowing the tradeoff before you touch the code.
250 cards
Sign up free and add it
The deck is added automatically once you finish signing up.
Nothing here is generated by AI, so the free plan is enough to add it.
See 30 sample cards
Showing a 30-card sample of 250.
| Front | Back |
|---|---|
| Big-O notation — what is it? | An asymptotic upper bound used to cap how fast running time or memory can grow for large inputs. Expresses time O(f(n)) or space O(g(n)). It does not claim the bound is tight. Often confused with Big-Theta. A function can be O(f(n)) and still be much smaller. |
| Telescoping recurrence — what is it? | A recurrence solved by expanding terms until most parts cancel, used to turn recursive cost into an explicit sum. For T(n)=T(n-1)+f(n), time is often O(the sum of f(i) for i from 1 to n). Space is O(n) with direct recursion or O(1) if rewritten iteratively. It is not the right tool for branching recurrences like T(n)=2T(n/2)+n, which do not collapse into one chain. |
| Array — what is it? | A fixed-size contiguous sequence used when you need O(1) indexing and compact storage. Index and update are O(1). Search is O(n). Insert or delete away from the end is O(n). Space is O(n). Middle edits shift many elements. O(1) access does not mean O(1) search. |
| Prefix sum array — what is it? | Stores cumulative totals so a range sum can be answered from two lookups, useful for many static interval queries. Build O(n) time and O(n) space. Range sum query O(1). Single update O(n) if prefixes stay explicit. Best for mostly read-only data. It is often confused with a difference array, which optimizes range updates instead. |
| Floyd's cycle detection — what is it? | Uses slow and fast pointers to detect a cycle in a linked structure without extra memory. Time O(n). Extra space O(1). It detects a cycle and can locate its entry, but it is not the same as reversing a list or marking visited nodes. |
| Rehashing — what is it? | Rebuilds a hash table at a new size and reinserts keys to restore low collision cost as occupancy changes. A resize step is O(n) time. Insert is O(1) average amortized and O(n) worst. Space O(n). Cached bucket indexes become invalid after resize. A full rebuild can cause latency spikes. |
| Complete binary tree — what is it? | A binary tree whose last level is filled left to right after all higher levels, which makes it efficient to store in an array. With n nodes, height is O(log n), traversal is O(n), and storage is O(n). Parent and child index jumps are O(1) in an array layout. Do not confuse complete with full or perfect. Missing nodes may appear only at the far right of the last level. |
| Binary heap — what is it? | A complete binary tree with heap order, usually stored in an array, used to implement a fast priority queue. Peek root is O(1). Insert and extract root are O(log n). Building from n items is O(n). Space is O(n). Only the root is globally smallest or largest. Searching for an arbitrary key is O(n), not O(log n). |
| Trie — what is it? | A tree over characters where each root-to-node path is a prefix, used for dictionaries, autocomplete and prefix tests. Search, insert and delete are O(m) for key length m. Space is O(number of nodes), which can be much larger than storing the keys alone. Memory use depends heavily on alphabet size and sparsity. It does not keep keys in BST order. |
| Threaded binary tree — what is it? | A binary tree that replaces null child links with inorder predecessor or successor links so traversal needs no stack. Traversal is O(n) time and O(1) extra space. Search, insert, and delete are O(h) time and must maintain threads. Updates are easy to get wrong. Do not confuse thread links with parent pointers. |
| Binomial heap — what is it? | A meldable heap built from binomial trees, useful when unioning priority queues efficiently matters. Insert, meld, extract-min, decrease-key, and delete are O(log n) worst case. Find-min is O(log n) or O(1) with a min pointer. Space O(n). It often has higher constants than a binary heap. The structure is a forest rather than one complete tree. |
| Aho-Corasick automaton — what is it? | A trie with failure links for finding many exact patterns at once while scanning the text one pass. Build is O(total pattern length) time and space. Search is O(text length plus matches). It is for exact multi-pattern search, not approximate matching. Large alphabets raise constants. |
| Quickselect — what is it? | Quickselect partitions like quicksort but recurses into one side, making it useful for finding the kth smallest item. Average O(n). Worst O(n^2). Extra space O(log n) average and O(n) worst from recursion. Bad pivots and many duplicates can hurt. It is often confused with fully sorting the array. |
| Bubble sort — what is it? | A comparison sort that repeatedly swaps adjacent out-of-order items and is used mainly for teaching or tiny nearly sorted inputs. Average and worst time O(n^2). Best time O(n) with early exit, otherwise O(n^2). Space O(1). Without a swapped flag, sorted input does not improve. It is often confused with insertion sort. |
| Jump search — what is it? | A search algorithm for sorted arrays that jumps ahead by blocks and then scans linearly within the right block. Average and worst time O(√n). Space O(1). It needs a sorted array and random access. It is slower than binary search asymptotically. |
| Floyd-Rivest algorithm — what is it? | A randomized selection algorithm that uses sampling to find the kth smallest element faster in practice than plain quickselect. Expected time O(n). Worst time O(n^2). Space O(log n) with recursion. It has no worst-case linear guarantee. It is often confused with median of medians. |
| Adjacency list — what is it? | Stores, for each vertex, the list of outgoing neighbors and is used for sparse graphs and fast neighbor traversal. Build O(V+E). Edge lookup O(deg(u)) worst. Neighbor iteration O(deg(u)). Space O(V+E). Dense graphs make it less cache friendly than a matrix. It is often confused with an edge list. |
| Breadth-first search — what is it? | Explores vertices by increasing distance from a start node and is used for reachability and shortest paths in unweighted graphs. O(V+E) time with adjacency lists, O(V^2) with a matrix. Space O(V). Weighted edges break shortest-path correctness. Mark vertices visited when enqueuing. |
| Strongly connected component — what is it? | A maximal set of vertices in a directed graph where every vertex can reach every other and is used to compress cycles. All SCCs can be found in O(V+E) time and O(V) space. This is for directed graphs. It is not the same as an undirected connected component. |
| Directed acyclic graph — what is it? | A directed graph with no directed cycles. It models dependencies and supports linear-time ordering and dynamic programs. Storage is O(V+E) with lists or O(V^2) with a matrix. Testing acyclicity or ordering takes O(V+E) time and O(V) extra space. Any directed cycle breaks it. Do not confuse a DAG with a tree, which is connected and acyclic in a different sense. |
| Bidirectional search — what is it? | A search that expands from source and target at the same time. It can cut the search depth for unweighted shortest paths. With branching factor b and distance d, balanced cases use O(b^(d/2)) time and space. Worst case remains O(b^d). It needs a known target and a way to search backward or generate reverse neighbors. |
| 0-1 BFS — what is it? | A shortest-path algorithm for graphs whose edge weights are only 0 or 1. It uses a deque instead of a priority queue. Time is O(V+E). Space is O(V). Any edge weight outside {0,1} breaks its guarantee. Do not replace general weighted shortest paths with it. |
| Bridge — what is it? | An edge whose removal increases the number of connected components of an undirected graph. It marks a single point of failure. All bridges can be found by one DFS with low-link values in O(V+E) time and O(V) extra space. In multigraphs parallel edges can prevent an edge from being a bridge even if it looks critical. |
| Closest pair of points — what is it? | A divide-and-conquer algorithm for the nearest pair in the plane. It is used to beat the quadratic all-pairs check. Time O(n log n). Space O(n). The strip combine step must examine only nearby points. Confused with the O(n^2) brute-force method. |
| Activity selection algorithm — what is it? | A greedy scheduler that repeatedly picks the compatible activity with earliest finish time. It is used to maximize the number of non-overlapping activities. Time O(n log n) with sorting, or O(n) after finish-time sorting. Space O(1) extra after sorting. It maximizes count, not total weight. Confused with weighted interval scheduling, which needs dynamic programming. |
| Backtracking — what is it? | A depth-first search technique that builds a candidate step by step and abandons partial solutions that violate constraints. It is used for exact combinatorial search. Worst-case time is often exponential, commonly O(b^d). Space O(d) for recursion depth. Weak pruning causes blowups. Confused with dynamic programming, which reuses overlapping subproblems. |
| PTAS — what is it? | A scheme that, for any fixed epsilon > 0, returns a solution arbitrarily close to optimal in polynomial time. It is used to trade accuracy for speed. For fixed epsilon, time is polynomial in n, often O(n^(f(1/epsilon))). Space is polynomial. Confused with FPTAS, which is also polynomial in 1/epsilon. A PTAS may still be impractical for small epsilon. |
| Fractional knapsack — what is it? | A greedy optimization problem where items can be split, so taking highest value density first gives the maximum value. Time O(n log n) for sorting by value density. Extra space is O(1) beyond the sort or O(n) with copied data. The greedy choice fails for the 0-1 version where items are indivisible. It is confused with 0-1 knapsack. |
| Branch and bound — what is it? | A search technique that explores a state tree but prunes branches whose bound proves they cannot beat the best known solution. Worst-case time is exponential. Space is O(depth) with DFS or exponential with best-first storage. Weak bounds give little pruning. It is confused with backtracking, which prunes by infeasibility rather than by objective bounds. |
| Pseudopolynomial time — what is it? | A running-time class where the bound is polynomial in a numeric value in the input, not in the input length. Typical forms are O(nW) time and O(W) or O(nW) space, where W is a numeric bound. It is not truly polynomial when W can be exponential in the number of input bits. |
About this deck
In data structures and algorithms, the miss is usually not forgetting a name. It is picking a hash table when ordering matters, trusting an average case when the worst case decides the answer, or blanking on the boundary rule that makes binary search go wrong. Interview and exam problems turn on those choices more than on raw memorization. This deck gives you 250 cards split across analysis (30), linear-structures (40), trees-and-heaps (45), sorting-and-searching (40), graphs (45), and algorithm-design (50). Each card covers one structure, algorithm, or concept, with the back cut into Meaning and Watch for. You review the idea and the case that breaks the obvious answer together. Where average and worst case differ, the card says so. On a spaced-repetition schedule, the answers you really know stop showing up so often, while the weak spots keep coming back until the tradeoffs stick. That turns review from rereading notes into naming the right tool on demand. The deck leaves out long proofs and full implementations by choice, so practice stays centered on recognition, complexity, and failure cases.
Frequently asked
- How is the deck split across topics?
- It has analysis (30), linear-structures (40), trees-and-heaps (45), sorting-and-searching (40), graphs (45), and algorithm-design (50). The mix keeps complexity, core structures, and named algorithms in the same review cycle.
- What kinds of cards are in this deck?
- You get single-topic cards such as Big-O notation, Binary search, and the Held-Karp algorithm. Each back is organized as Meaning and Watch for so the definition and the failure case stay linked.
- What does this deck leave out on purpose?
- It does not try to be a full textbook or a code notebook. Long proofs, full implementations, and extended worked problems are left out so review stays focused on choosing the right structure or algorithm, recalling complexity, and spotting the case that breaks it.
- Can I import the whole deck on the free plan?
- Yes. Importing a saved deck runs no new AI generation and does not use your AI allowance, so the free plan imports all 250 cards. You can study, edit and delete them afterwards.
- Will importing it twice create duplicates?
- No. Cards you already have are skipped and only cards added in a revision come through. Including re-imports after deleting it, one official deck can be imported three times per account.
- Can I use it on the web and in the mobile app?
- Yes. The deck is added to your account rather than to a device, so the same cards and the same progress are there on the web, on iOS and on Android.
- Can I edit the cards after importing?
- Yes. Imported cards are yours: you can edit both sides, delete cards you do not need, change tags, and move cards to another deck.
No official exam questions are reproduced. Every card was written for this deck.Editorial reference date 2026-08-30.