Algorithms Interview Questions

Time complexity measures how the runtime of an algorithm grows relative to input size, expressed using Big O notation (e.g., O(n), O(n^2)). Space complexity measures how memory usage grows with input size, including auxiliary space used by the algorithm. Both are crucial for algorithm analysis - time complexity affects performance, while space complexity affects memory requirements and can be traded off with time.

Binary search finds a target value in a sorted array by repeatedly dividing the search interval in half. Compare target with middle element: if equal, found; if target is smaller, search left half; if larger, search right half. Time complexity is O(log n) since each comparison eliminates half the remaining elements. Space is O(1) iterative or O(log n) recursive. Requires sorted input.

Bubble sort repeatedly steps through the array, comparing adjacent elements and swapping them if they're in wrong order. The largest elements 'bubble' to the end in each pass. Time complexity is O(n^2) in average and worst case (already sorted in reverse), O(n) in best case (already sorted with optimization flag). Space is O(1). Simple but inefficient for large datasets; mainly used for educational purposes.

Big O notation describes the upper bound of an algorithm's growth rate, representing worst-case scenario in terms of input size n. Common complexities from best to worst: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, O(2^n) exponential. It abstracts away constants and lower-order terms, allowing comparison of algorithmic efficiency regardless of hardware.

Linear search sequentially checks each element in a collection until finding the target or reaching the end. Time complexity is O(n) worst/average case, O(1) best case. Space is O(1). Use when: data is unsorted, dataset is small, search is one-time, or elements are accessed sequentially (linked lists). For sorted or frequently searched data, binary search or hash tables are preferred.

Selection sort divides the array into sorted and unsorted portions. It repeatedly finds the minimum element from the unsorted portion and swaps it with the first unsorted element. Time complexity is O(n^2) for all cases (always scans entire unsorted portion). Space is O(1). Performs fewer swaps than bubble sort (O(n) vs O(n^2)), making it useful when write operations are expensive.

Insertion sort builds the sorted array one element at a time by inserting each element into its correct position among previously sorted elements. Time complexity is O(n^2) worst/average case but O(n) for nearly sorted arrays. Space is O(1). Efficient for small datasets, nearly sorted arrays, and online algorithms (can sort as data arrives). Used as base case in hybrid sorts like Timsort.

Recursion is a technique where a function calls itself to solve smaller subproblems of the same type. Essential components are: Base case (termination condition that stops recursion), Recursive case (function calls itself with modified parameters moving toward base case). Each recursive call adds to the call stack. Common uses include tree traversal, divide-and-conquer algorithms, and mathematical computations like factorial and Fibonacci.

A stable sort preserves the relative order of elements with equal keys - if two elements are equal, they appear in the same order in the sorted output as in the input. Unstable sorts may change this relative order. Stable sorts: Merge sort, Insertion sort, Bubble sort. Unstable sorts: Quick sort, Heap sort, Selection sort. Stability matters when sorting by multiple fields or when preserving original order for ties is important.

A greedy algorithm makes the locally optimal choice at each step with the hope of finding a global optimum. It never reconsiders previous choices. Example: Coin change with denominations [25,10,5,1] - always pick the largest coin that doesn't exceed remaining amount. Works for standard denominations but not all cases (e.g., [1,3,4] making 6). Greedy algorithms are efficient but don't always yield optimal solutions.

Merge sort is a divide-and-conquer algorithm that recursively divides the array into halves until single elements, then merges them back in sorted order. Time complexity is O(n log n) for all cases - consistent performance. Space is O(n) for the merge operation. Advantages: stable sort, predictable performance, parallelizable, works well for linked lists (no random access needed). Disadvantage: requires extra space unlike in-place sorts.

Dynamic programming solves complex problems by breaking them into overlapping subproblems, storing solutions to avoid redundant computation (memoization or tabulation). Use DP when: problem has optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems (same subproblems solved multiple times). Common examples: Fibonacci, shortest paths, knapsack. DP trades space for time, reducing exponential complexity to polynomial.

Quick sort selects a pivot element, partitions the array so elements less than pivot are on the left and greater on the right, then recursively sorts the partitions. Average time complexity is O(n log n), worst case O(n^2) when pivot is always smallest/largest. Space is O(log n) for recursion stack. Fast in practice due to cache efficiency and in-place sorting. Pivot selection strategies (random, median-of-three) help avoid worst case.

DFS (Depth-First Search) explores as deep as possible before backtracking, using a stack or recursion. Used for: path finding, cycle detection, topological sorting, maze solving. BFS (Breadth-First Search) explores all neighbors at current depth before going deeper, using a queue. Used for: shortest path in unweighted graphs, level-order traversal, finding connected components. Both are O(V+E) for graphs.

Best case is the minimum time/space needed (e.g., binary search finding target at middle - O(1)). Average case represents expected performance over all possible inputs (binary search - O(log n)). Worst case is maximum resources needed (binary search - O(log n)). Big O typically describes worst case, while Big Theta describes tight bounds. Understanding all cases helps choose algorithms for specific use cases and input distributions.

Lomuto partition uses a single pointer, placing pivot at end, and scans left-to-right swapping elements smaller than pivot. Simpler but does more swaps. Hoare partition uses two pointers moving inward, swapping when they find pair out of order - fewer swaps (3x fewer on average), handles duplicates better, but pivot doesn't end at final position. Hoare is generally faster but Lomuto is easier to implement and modify.

Naive recursion has O(2^n) complexity due to repeated subproblems. Memoization (top-down DP) stores computed values, reducing to O(n) time and O(n) space. Tabulation (bottom-up DP) iteratively fills a table from base cases: O(n) time, O(n) space. Space-optimized version only keeps last two values: O(n) time, O(1) space. Matrix exponentiation achieves O(log n) time using [[1,1],[1,0]]^n property.

Dijkstra's finds shortest paths from a source to all vertices in a weighted graph with non-negative edges. Use priority queue (min-heap) storing (distance, vertex). Start with source at distance 0, others at infinity. Extract minimum, update neighbors if shorter path found (relaxation). Time complexity is O((V+E) log V) with binary heap, O(V^2) with array. Doesn't work with negative edges - use Bellman-Ford instead.

Given items with weights and values, maximize total value that fits in a knapsack of capacity W. Each item is either included or excluded (0/1). DP solution uses 2D table dp[i][w] = max value using first i items with capacity w. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]). Time and space are O(nW). Space can be optimized to O(W) using 1D array processed right-to-left.

Heap sort builds a max-heap from the array (O(n)), then repeatedly extracts the maximum, places it at the end, and re-heapifies (O(n log n)). Total complexity is O(n log n) for all cases - no worst-case degradation like quicksort. Space is O(1) - truly in-place. However, it's not stable and has poor cache locality compared to quicksort. Used when guaranteed O(n log n) is needed without extra memory.

LCS finds the longest sequence present in both strings in the same order (not necessarily contiguous). Use 2D DP table where dp[i][j] = LCS length of first i chars of X and first j chars of Y. If X[i] == Y[j], dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Time and space are O(mn). Backtrack to reconstruct the actual LCS. Used in diff tools and bioinformatics.

Given activities with start and finish times, select maximum non-overlapping activities. Greedy approach: sort by finish time, always select the activity that finishes earliest and is compatible with previous selection. This works because finishing early leaves maximum time for remaining activities. Time complexity is O(n log n) for sorting. This problem demonstrates when greedy gives optimal solution - can be proven by exchange argument.

For first occurrence: when target found, continue searching left half (right = mid - 1) and track result. For last occurrence: when target found, continue searching right half (left = mid + 1) and track result. Both are O(log n). This technique applies to finding lower/upper bound, count of element, and insertion position. Python's bisect_left/bisect_right and C++'s lower_bound/upper_bound implement these.

Divide array into halves recursively until single elements. Merge combines two sorted halves: use two pointers, compare elements at each pointer, copy smaller to result array, advance that pointer. Continue until one half exhausted, then copy remaining. Key insight: merging two sorted arrays is O(n). Total complexity: T(n) = 2T(n/2) + O(n) = O(n log n) by Master theorem. Space O(n) for merge buffer.

Bellman-Ford handles negative edge weights (Dijkstra cannot) and detects negative cycles. It relaxes all edges V-1 times; if any edge can still be relaxed, negative cycle exists. Time complexity is O(VE), slower than Dijkstra's O((V+E)log V). Use Bellman-Ford when: graph has negative weights (currency arbitrage), need to detect negative cycles, or graph is dense and simple implementation is preferred.

Counting sort is a non-comparison sorting algorithm for integers in a known range [0,k]. Count occurrences of each value, compute cumulative counts (positions), place elements in output array using counts. Time complexity is O(n+k), space is O(n+k). Most efficient when k is O(n) - achieves linear time. Not suitable when range is much larger than n. Serves as subroutine in radix sort. It's stable sort.

Given coins and target amount, find minimum coins needed (or number of ways). For minimum coins: dp[i] = min coins for amount i. Initialize dp[0]=0, others=infinity. For each amount i and each coin c, if c<=i: dp[i] = min(dp[i], dp[i-c]+1). For counting ways: dp[i] += dp[i-c]. Time O(amount * coins), space O(amount). The greedy approach doesn't always work (e.g., [1,3,4] making 6).

Both find MST but differ in approach. Kruskal's: sort all edges, add smallest edge that doesn't form cycle (using Union-Find). Time O(E log E). Better for sparse graphs and when edges are already sorted. Prim's: grow tree from arbitrary vertex, always add minimum edge connecting tree to non-tree vertex. Time O(E log V) with binary heap. Better for dense graphs. Both are greedy algorithms guaranteed to find MST.

Edit distance measures minimum operations (insert, delete, substitute) to transform one string to another. DP solution: dp[i][j] = distance between first i chars of s1 and first j chars of s2. If chars match, dp[i][j] = dp[i-1][j-1]. Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) for delete, insert, substitute respectively. Time and space O(mn). Used in spell checkers and DNA sequence alignment.

Backtracking is a refined brute force that abandons partial solutions as soon as they're determined invalid, avoiding exploration of entire subtrees. Build solutions incrementally, at each step check constraints; if violated, backtrack (undo) and try next option. Unlike brute force that generates all possibilities then filters, backtracking prunes early. Used in N-Queens, Sudoku, permutations/combinations. Time can vary from O(n!) worst case to much better with good pruning.

Radix sort sorts integers digit by digit from least significant to most significant (LSD) or vice versa (MSD). Each digit pass uses stable counting sort. For n numbers with d digits and base b (typically 10 or 256), time is O(d*(n+b)), space is O(n+b). When d is constant, achieves O(n) - faster than comparison sorts' O(n log n) lower bound. Best for fixed-length integers or strings.

Basic DP: dp[i] = LIS ending at index i. For each i, dp[i] = 1 + max(dp[j]) for j < i where arr[j] < arr[i]. O(n^2) time. Optimized O(n log n): maintain array of smallest tail elements for LIS of each length. For each element, binary search to find position (extends existing or replaces tail). Length of array is LIS length. Reconstruction requires additional bookkeeping.

Flood fill starts from a seed point and fills connected regions with a new color. Implementation uses BFS or DFS: check if current cell matches target color, if yes change to new color and recursively/iteratively process neighbors (4-directional or 8-directional). Time O(m*n) for m*n grid. Applications: paint bucket tool in image editors, solving maze, finding connected components, region labeling in image processing.

Huffman coding creates optimal prefix-free codes for lossless compression. Greedy approach: build binary tree bottom-up by repeatedly combining two lowest-frequency nodes. Frequent characters get shorter codes, rare characters get longer codes. Use min-heap to efficiently find minimum nodes. Time O(n log n). Guarantees optimal prefix code where no code is prefix of another. Used in ZIP, JPEG, MP3 compression.

Two-pointer technique uses two indices to traverse data structure, typically moving toward each other or in same direction. Applications: Finding pair with target sum in sorted array (pointers at both ends, move based on current sum), Removing duplicates in-place (slow and fast pointers), Palindrome check, Merging sorted arrays, Sliding window problems. Reduces O(n^2) brute force to O(n) in many cases.

NP-complete problems are the hardest problems in NP (verifiable in polynomial time) - if any NP-complete problem has polynomial solution, all NP problems do (P=NP). Examples: SAT, Traveling Salesman, Graph Coloring, Knapsack (decision version). Proven NP-complete via reduction from known NP-complete problem. Significance: no known polynomial algorithms exist, likely impossible, so we use approximation algorithms, heuristics, or solve restricted cases.

Floyd-Warshall finds shortest paths between all pairs of vertices, handling negative edges (but not negative cycles). Uses DP: dist[i][j][k] = shortest path from i to j using only first k vertices as intermediates. Recurrence: min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]). Time O(V^3), space O(V^2). Detects negative cycles when diagonal becomes negative. Used in network routing, transitive closure.

Knuth-Morris-Pratt achieves O(n+m) string matching by preprocessing pattern to build failure function (LPS array) - longest proper prefix which is also suffix. During search, when mismatch occurs, use LPS to skip characters already matched instead of restarting. LPS construction is O(m), matching is O(n). Key insight: we never need to backtrack in the text, only in the pattern using precomputed information.

A* combines Dijkstra's shortest path with heuristic guidance. Uses f(n) = g(n) + h(n) where g is actual cost from start, h is heuristic estimate to goal. Priority queue processes nodes by lowest f-value. Heuristic must be admissible (never overestimate) for optimal path, and consistent for efficiency. Common heuristics: Manhattan distance (grid), Euclidean distance. More efficient than Dijkstra when good heuristic exists. Used in games, robotics, navigation.

Minimize scalar multiplications for multiplying chain of matrices A1*A2*...*An. Different parenthesizations yield different costs. DP solution: dp[i][j] = minimum cost to multiply matrices i to j. For each possible split point k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]). Solve for increasing chain lengths. Time O(n^3), space O(n^2). Classic example of DP with optimal substructure.

Ford-Fulkerson finds maximum flow in a network by repeatedly finding augmenting paths from source to sink in residual graph and pushing flow along them. Residual graph contains remaining capacities and reverse edges for flow cancellation. Path finding strategy matters: DFS gives O(EF) where F is max flow (can be slow), BFS (Edmonds-Karp) gives O(VE^2). Applications: bipartite matching, network routing, image segmentation.

TSP is NP-hard; exact solutions are O(n!). DP with bitmask achieves O(n^2 * 2^n) - dp[mask][i] = min distance visiting cities in mask, ending at i. Approximation algorithms: Christofides (1.5x optimal for metric TSP), MST-based (2x optimal). Heuristics: Nearest neighbor, 2-opt improvement, simulated annealing, genetic algorithms. Branch and bound with good bounds can solve instances with ~50-100 cities. Choice depends on size and accuracy requirements.

Suffix trees are compressed tries of all suffixes of a string, built in O(n) time with Ukkonen's algorithm. Applications: O(m) pattern matching, O(n) longest repeated substring, longest common substring of multiple strings, finding all occurrences of pattern, text compression (LZ77). Space is O(n) but with large constants (~20 bytes per character). Suffix arrays are more space-efficient alternatives for many applications.

Amortized analysis averages time over a sequence of operations, showing that expensive operations are rare enough that average cost is low. Methods: Aggregate (total time / operations), Accounting (assign artificial costs, save credits), Potential (define potential function measuring 'saved work'). Examples: Dynamic array resizing - individual push may be O(n), but amortized O(1). Splay tree operations - worst case O(n), amortized O(log n). Union-Find with optimizations - amortized O(alpha(n)).

Convex hull is smallest convex polygon containing all points. Graham scan: sort by polar angle from lowest point, process in order keeping only left turns. O(n log n). Jarvis march (gift wrapping): start from leftmost, repeatedly find point making smallest angle. O(nh) where h is hull points. Chan's algorithm: optimal O(n log h) combining both. QuickHull: divide-and-conquer, average O(n log n), worst O(n^2). Choice depends on expected output size.

Randomized algorithms use random choices during execution. Las Vegas algorithms always give correct result with random runtime (e.g., randomized quicksort - expected O(n log n)). Monte Carlo algorithms may give incorrect result with bounded probability (e.g., primality testing). Analysis uses expected value and probability bounds. Benefits: simpler, avoid worst cases, resist adversarial inputs. Examples: randomized selection, skip lists, Bloom filters, Min-Cut algorithm.

Approximation algorithms find near-optimal solutions to NP-hard problems in polynomial time with guaranteed quality. Approximation ratio r means solution is within factor r of optimal. Examples: Vertex Cover has 2-approximation (take both endpoints of each edge). Set Cover has O(log n)-approximation (greedy). TSP metric has 1.5-approximation (Christofides). PTAS (Polynomial Time Approximation Scheme) achieves (1+epsilon) ratio for any epsilon. Inapproximability results show limits.

Parallel algorithms divide work across multiple processors. Key measures: work (total operations), span/depth (longest dependency chain), parallelism (work/span). Amdahl's Law limits speedup based on sequential fraction. PRAM models: EREW, CREW, CRCW for memory access. Examples: parallel prefix sum O(n) work O(log n) span, parallel merge sort, matrix multiplication. Practical considerations: communication cost, load balancing, memory hierarchy. GPUs enable massive parallelism for suitable problems.

Online algorithms make decisions without knowing future input, unlike offline algorithms with complete information. Competitive ratio compares online algorithm's cost to optimal offline solution. Examples: Paging/caching - LRU is k-competitive; Ski rental - rent vs buy is 2-competitive; Load balancing - greedy is 2-competitive. Lower bounds prove limits. Randomization can improve competitive ratios. Real applications: caching, scheduling, financial trading, resource allocation.

Bitmask DP uses integer bits to represent subsets, solving problems like TSP, assignment, and subset optimization in O(2^n * poly(n)). Digit DP counts numbers with certain properties by processing digits, tracking tight bound and state (e.g., count numbers with digit sum S). Tree DP solves tree problems by computing values bottom-up: subtree aggregation, rerooting for all-roots answers. These techniques extend DP applicability to complex combinatorial and structural problems.