Data Structures and Algorithms (DSA)

Big O describes how the time or space an algorithm needs grows as the input size increases. To analyze it, identify the input size, count the dominant operations, and express their asymptotic growth; constants and lower-order terms are usually omitted. For example, traversing an array takes O(n), while comparing every pair of elements usually takes O(n²).

Clarify whether you mean worst, average, or best case, and distinguish total space from auxiliary space. In an interview, also state your assumptions: a hash-table lookup is usually O(1) on average but can reach O(n) in the worst case.

A dynamic array provides O(1) indexed access and good memory locality. Appending takes amortized O(1), although an occasional resize copies its elements and costs O(n). Inserting or deleting in the middle usually requires shifting elements and also costs O(n).

A linked list lets you insert or remove a node in O(1) when you already have its reference, but finding that position takes O(n), and indexed access takes O(n). Explain the operations that dominate and the memory constraints before choosing.

A hash table maps a key to an index so it can look up, insert, or delete values in expected O(1) time. Two keys can map to the same index: the table handles collisions, for example, by storing multiple entries in one bucket or probing for another available position.

If collisions accumulate, operations can degrade to O(n). Keeping the load factor under control and resizing help preserve average performance. Keys must also keep equality and hashing consistent: equal keys must produce the same hash.

A stack follows last in, first out (LIFO); its typical operations add to and remove from the top. It is useful for undoing actions, evaluating expressions, and backtracking.

A queue follows first in, first out (FIFO), with insertions at the back and removals at the front. A deque allows insertions and removals at both ends. In an interview, connect the data structure to the processing order the problem requires.

In a sorted sequence, compare the middle element with the target and discard the half that cannot contain it. The time complexity is O(log n); on an array, an iterative version uses O(1) auxiliary space.

Define the search interval first and keep the same convention when updating its bounds. Decide whether you need any match, the first valid position, or an insertion position. “First position that satisfies a condition” variants work when the condition is monotonic: it changes from false to true, or true to false, only once.

In a binary search tree, values in each subtree follow the ordering rule relative to its node. Searching, inserting, or deleting takes O(h), where h is the height: O(log n) when balanced, but O(n) if the tree degenerates into a chain.

An in-order traversal visits keys in sorted order. Balanced trees such as AVL and red-black trees limit height through balancing rules, at the cost of extra work during updates.

BFS explores a graph layer by layer and finds paths with the fewest edges in an unweighted graph. DFS follows a branch as far as it can before backtracking; it is useful for cycle detection, traversing components, and processing dependencies.

With adjacency lists, both searches take O(V + E), where V is the number of vertices and E is the number of edges. Mark vertices when they are discovered so they are not processed repeatedly. For weighted graphs, BFS is not generally enough to find the lowest-cost path.

A binary heap is a nearly complete tree that keeps its minimum or maximum at the root. Reading the root takes O(1), insertion and removal of the root take O(log n), and building a heap from n elements can take O(n).

A priority queue is useful when you must repeatedly process the highest- or lowest-priority element, for example, to find the k largest elements or choose the next vertex in Dijkstra's algorithm. It does not keep all elements fully sorted.

A stable sort preserves the relative order of elements with equal keys. This lets you sort by multiple criteria in sequence without losing the order of an earlier criterion. For example, sorting records by date and then stably by category preserves date order within each category.

Comparison sorts have a lower bound of Ω(n log n) comparisons in the general case. Counting sort and radix sort can achieve better growth when the keys have a range or representation that allows additional assumptions.

A greedy algorithm takes the locally best-looking decision at each step and usually does not revisit it. It is correct only when those decisions can be shown to lead to a globally optimal solution; the proof often relies on a greedy-choice property or an exchange argument.

Dynamic programming applies when subproblems repeat and their results help solve larger problems. Define the state, transition, and base cases, then compute each subproblem once using memoization or tabulation. Explain the number of states and the cost of each transition to derive the complexity.

Use it to build solutions incrementally when a partial choice can either lead to a complete solution or be discarded. Define a base case, choose an option, explore its consequences, and undo the choice before trying the next one. It works for permutations, combinations, Sudoku, and maze search.

Its worst case can explore an exponential search space. Reduce work by pruning branches that violate constraints early; if different paths reach the same subproblem, consider memoization or dynamic programming.

Two pointers move through a sequence to find a relationship between elements, such as a pair with a target sum in a sorted array. A sliding window maintains a contiguous interval and updates its state as one or both boundaries move; it often finds the longest or shortest subarray that meets a condition.

Either technique can reduce an O(n²) solution to O(n) when each pointer advances at most n times. First check the property that lets you discard elements; for example, a window based on sum behaves differently when negative values are present.

A prefix sum stores cumulative totals from the beginning. It lets you calculate an interval sum in O(1) after O(n) preprocessing, and can also count subarrays with a target sum using a frequency map.

For many range updates, a difference array records where a value changes at the interval boundaries and reconstructs the result in one pass. State whether intervals include both endpoints to avoid off-by-one errors.

It is a stack whose elements are kept in increasing or decreasing order, depending on the problem. When a new value breaks that order, elements that can no longer be answers are removed. This finds, for example, the next greater value or the largest rectangle in a histogram in amortized O(n): each element enters and leaves at most once.

A monotonic queue applies a similar idea to a moving window and keeps useful candidates for finding each window's minimum or maximum in linear time.

A trie stores keys by shared prefixes, usually one character per edge. Searching, inserting, or deleting a word of length L takes O(L), independent of the number of stored words.

It is useful for autocomplete, dictionaries, and prefix search. It can use substantial memory if every node reserves space for many transitions; compare sparse or compact representations and decide whether prefix queries justify the cost.

Disjoint Set Union (DSU), also called Union-Find, maintains a collection of disjoint components. The find operation identifies an element's representative, and union combines two components. Path compression and union by size or rank make a sequence of operations amortized almost constant time.

Use it to detect whether an edge joins vertices that are already connected, as in Kruskal's algorithm, or to group related elements. By itself, it does not store graph edges or answer path queries between vertices.

It is a linear ordering of vertices in a directed graph where every edge points from an earlier vertex to a later one. It exists only if the graph is acyclic (a DAG). It can be computed by repeatedly removing vertices with in-degree zero or with DFS; both approaches take O(V + E) with adjacency lists.

It is useful for task, module, or course dependencies. If vertices remain unprocessed at the end, the graph contains a cycle and no valid ordering exists.

BFS finds paths with the fewest edges when all edges have equal cost. Dijkstra handles nonnegative weights and, with a priority queue and adjacency lists, typically takes O((V + E) log V). Bellman-Ford allows negative weights and can detect reachable negative cycles, at a higher O(VE) cost.

Choose based on the graph's properties and clarify what “shortest” means: fewest hops or lowest total weight. A reachable negative cycle that can also reach the destination means the minimum cost is unbounded.

In an undirected graph, it connects every vertex with the lowest total edge weight and no cycles. Kruskal sorts edges and adds those that connect different components, usually with Union-Find. Prim grows a current tree by choosing the cheapest edge that reaches another vertex.

Both are commonly implemented in O(E log V) or O(E log E), depending on representation and priority queue. A minimum spanning tree does not necessarily contain the shortest path between every pair of vertices.

Merge sort guarantees O(n log n), is stable in its usual form, and needs linear auxiliary space for arrays. Quicksort is often fast in practice and uses little extra space with in-place partitioning, but can degrade to O(n²) with poor pivots; randomization or introsort reduces that risk.

Heapsort guarantees O(n log n) and can sort in place, but is not stable and often has poorer memory locality. Choose based on guarantees, stability, and memory, not just the best case.

When k is small relative to n, a size-k min-heap keeps the best candidates in O(n log k) time and O(k) space. Sorting everything in O(n log n) is also suitable if you need the full ordering afterward.

Quickselect partitions around a pivot and places the k-th element without sorting the entire collection. Its expected cost is O(n), though its worst case can be O(n²); use a pivot strategy that limits that risk when guarantees matter.

It converts interval endpoints into sorted events and scans them while maintaining the active state. This can detect overlaps, merge intervals, or count how many rooms are needed for meetings. Sorting usually dominates, making the time complexity O(n log n).

Define whether intervals are open or closed and which event should be processed first when endpoints match. That convention changes boundary results and is a common source of mistakes.

Explain why it produces a valid answer for every allowed input, not only the examples. For a loop, state an invariant: a property that holds before the loop starts, remains true after each iteration, and proves the result when the loop ends.

For a recursive solution, prove that the base cases are correct and each step reduces the problem to smaller instances whose correct answers can be combined. If the strategy is greedy, also justify why a local choice does not rule out every global optimum.

Identify how many subproblems of approximate size n/b each level creates and the work needed to split and combine their results. Express the time as a recurrence, such as T(n) = aT(n/b) + f(n), and solve it with a recursion tree or the Master Theorem when its assumptions hold.

Also count recursion depth and temporary combination space. Time complexity does not automatically include the call stack or auxiliary arrays.

They inspect or change individual bits using AND, OR, XOR, shifts, and masks. They can represent a small set of choices, toggle flags, or check properties such as whether an integer has a single set bit.

Use them when the domain and limits are clear. Account for integer width and signedness, operator precedence, and overflow; a compact expression that nobody can review is not an improvement by itself.

Organize practice around arrays and hashing, stacks and queues, trees and heaps, sorting, graphs, searching, and dynamic programming. For each problem, explain edge cases, justify correctness, and calculate time and space before optimizing.

As reference material, see the MIT 6.006 syllabus, its algorithm and data structure lecture notes, and Princeton's Algorithms booksite.