Search
30 results for “algorithms”
Search results
Rate Limiting Algorithms
How the token bucket algorithm AWS API Gateway actually uses separates a steady-state rate from a burst allowance, and why a request only fails once the bucket is genuinely empty, not the instant the average rate is exceeded.
Sorting Algorithms & Stability
Why a "stable" sort guarantees equal-key elements keep their original relative order, and how Python's Timsort exploits already-sorted runs in real data to hit O(n) on the best case instead of always paying O(n log n).
What are the three join algorithms PostgreSQL's planner can choose between, and what does each one actually do?
A nested loop join takes each row from one table (the outer side) and scans the other table (the inner side) for matches, the simplest algorithm, and cheap specifically when the inner side is small or has a usable index so that scan is fast per outer row. A hash join builds an in-memory hash table from one input keyed on the join column, then probes it with rows from the other input, efficient for large inputs with no useful sort order or index. A merge join requires both inputs already sorted on the join key (or sorts them first) and then walks both sorted streams in lockstep, efficient specifically when that sorted order already exists or is useful for something else in the query anyway.
Big O Notation
How to read and reason about Big O time and space complexity, with the common growth rates ranked and worked examples for each.
Binary Search
Why bisect_left and bisect_right return different insertion points for the exact same value, and why binary search silently returns a wrong answer, not an error, the moment the input isn't actually sorted.
Dynamic Programming
Why caching subproblem solutions turns an exponential naive recursive Fibonacci into a linear one, and what "overlapping subproblems" actually has to be true about a problem before memoization can help at all.
Graph Traversal: BFS & DFS
Why breadth-first search's queue explores every neighbor before any of their children, guaranteeing the shortest path in an unweighted graph, while depth-first search's stack (or recursion) does the opposite and can't make that guarantee at all.
Recursion & the Call Stack
Why CPython's recursion limit exists to protect the real, platform-dependent C stack rather than being an arbitrary language rule, and why raising it too high can still crash the interpreter instead of just allowing deeper recursion. Verified against CPython 3.12; exact stack behavior, default limit, and crash mode are interpreter- and version-specific, not universal across every Python implementation.
What does O(n) actually mean?
It means the algorithm's work grows linearly with input size n, double the input, roughly double the work. Big O describes the worst-case growth rate as n gets large, ignoring constant factors and lower-order terms: an algorithm that does 3n + 100 operations is still O(n), because for large n the constant 100 and the multiplier 3 stop mattering compared to how n itself grows.
Why does an O(n log n) sort beat an O(n^2) sort for large inputs, even if the O(n^2) one is faster on small inputs?
Constant factors can make an O(n^2) algorithm faster for small n, Big O only describes the asymptotic trend, not the exact runtime. But growth rates diverge fast: at n = 1,000,000, n log n is about 20 million operations while n^2 is a trillion. Past a crossover point the asymptotically better algorithm always wins, which is why production sort implementations (like Timsort) still often special-case small arrays with a simpler O(n^2) sort under the hood.
What is the difference between time complexity and space complexity?
Time complexity describes how the number of operations grows with input size; space complexity describes how additional memory usage grows with input size. An algorithm can trade one for the other, memoization in dynamic programming typically turns exponential time into polynomial time by spending O(n) or more extra space to cache results.
For a sorted list [1, 2, 2, 2, 3], what index does bisect_left(2) return versus bisect_right(2), and why are they different?
`bisect_left` returns 1, the insertion point before every existing 2, so inserting there keeps all 2s together immediately after it. `bisect_right` returns 4, the insertion point after every existing 2, keeping all 2s together immediately before it. They differ because they define the insertion point by a different partition rule, `bisect_left` guarantees everything before the returned index is strictly less than the target, `bisect_right` guarantees everything before the returned index is less than or equal to it, so the choice determines whether a new equal-valued element gets inserted before or after existing equal elements, not just where "some 2" is found.
Why does binary search require the input to already be sorted, and what actually happens if you run it on unsorted data?
Binary search's core logic is comparing the target against a midpoint and eliminating the entire half that can't possibly contain it, an elimination step that's only valid if elements are ordered, so everything below the midpoint really is smaller and everything above really is larger. Run it on unsorted data and there's no error or exception, the algorithm has no way to detect the invariant is broken, it just keeps halving the search space based on comparisons that no longer imply anything real, and returns an insertion point or "not found" result that has no actual relationship to whether or where the target exists in the list.
Why is binary search O(log n) instead of O(n), and what specifically has to be true about the data structure for that to hold?
Each comparison eliminates half of the remaining search space, so after k comparisons only n/2^k elements remain to check, meaning the search terminates once 2^k ≥ n, k ≈ log2(n) comparisons, exponentially fewer than checking every element one at a time. That guarantee depends entirely on being able to jump directly to a midpoint in constant time, which is true for an array or list with O(1) random access, but not for a data structure like a linked list where reaching the "middle" element itself takes O(n) time, on a linked list, binary search's comparison-count advantage is real but gets erased by the cost of just navigating there.
What does NIST's own definition of dynamic programming actually say the technique does, and what problem does it solve?
NIST's Dictionary of Algorithms and Data Structures defines dynamic programming as an algorithmic technique to "solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them." The problem it solves is redundant recomputation: when a naive recursive solution calls itself with the same subproblem arguments repeatedly (matrix-chain multiplication, longest common subsequence, and similar problems are the examples NIST gives), that same subproblem gets solved from scratch every single time it recurs, and caching the first result lets every later occurrence be a lookup instead of a full recomputation.
Why does a naive recursive Fibonacci function run in exponential time, and how does memoization fix that specifically?
Naive recursive `fib(n) = fib(n-1) + fib(n-2)` recomputes the exact same subproblem enormous numbers of times, `fib(n-2)` gets computed once directly and once again inside the `fib(n-1)` call, and this duplication compounds recursively, producing roughly 2^n total calls. Memoization caches each `fib(k)` result the first time it's computed, so every subsequent call with the same `k` becomes an O(1) cache lookup instead of a full recursive recomputation, collapsing the total distinct work down to O(n), one computation per distinct subproblem instead of an exponential number of repeated ones.
What does "overlapping subproblems" mean, and why does dynamic programming provide no benefit for a problem that lacks it?
Overlapping subproblems means the same smaller subproblem genuinely recurs multiple times across different branches of the larger problem's recursive structure, exactly what makes caching valuable, the second and later occurrences become free lookups. A problem like standard mergesort, by contrast, has no overlapping subproblems, every recursive call operates on a genuinely distinct slice of the array that never recurs anywhere else, so there is nothing to cache and memoization adds only overhead (cache storage and lookup cost) with zero reuse to offset it. Recognizing whether a problem's recursive breakdown actually revisits the same subproblems is the real prerequisite for dynamic programming to help at all.
What is the defining structural difference between BFS and DFS, and what data structure does each rely on?
Breadth-first search considers every neighbor of a vertex before considering any of those neighbors' own outgoing edges, per NIST's definition, extremes are searched last, which is implemented with a queue: vertices are processed in the order they were discovered, level by level outward from the start. Depth-first search does the opposite, it considers a vertex's outgoing edges (children) before any of the vertex's siblings, plunging as deep as possible along one path before backtracking, and NIST notes it's "easily implemented with recursion," which uses the call stack implicitly as its ordering structure (or an explicit stack in an iterative version).
Why does BFS guarantee the shortest path in an unweighted graph, while DFS gives no such guarantee at all?
Because BFS processes vertices in strict order of distance from the start (via its queue, level by level), the first time it reaches any given vertex is necessarily via a shortest path to it, there's no way to discover a vertex at distance k before every vertex at distance k-1 has already been discovered. DFS has no such ordering property, it commits to going as deep as possible down one path before backtracking, so it can easily reach a target vertex via a long, winding path long before it would have found a much shorter one, there's nothing in DFS's structure that favors shorter paths over longer ones at all.
For the same graph, why might you choose DFS over BFS even though BFS finds shortest paths and DFS doesn't?
Shortest-path guarantees aren't always the goal, DFS is a natural fit for exhaustively exploring all possibilities along one path before trying another (backtracking problems, detecting cycles, topological sorting, finding connected components), where the actual requirement is "visit everything reachable" or "explore this branch fully before trying the next," not "find the closest thing first." DFS via recursion is also often simpler to implement for these problems, at the cost of consuming call-stack depth proportional to how deep the graph goes, which matters for very deep or very large graphs where an iterative approach (or BFS) avoids the recursion-depth risk entirely.
What does Python's recursion limit actually protect against, and is it just an arbitrary language-level rule?
It protects the real, underlying C stack the Python interpreter itself runs on, each level of recursion consumes real stack memory, and without a limit, sufficiently deep (or infinite) recursion would exhaust that stack and crash the interpreter process entirely, a hard C-level failure, not a clean Python exception. The limit converts that hard crash into a catchable `RecursionError` raised well before the actual stack is exhausted, which is exactly why it exists, a controlled failure mode is far better than an uncontrolled process crash, not an arbitrary restriction on how "should" write code.
Python's own documentation warns that raising the recursion limit "should be done with care, because a too-high limit can lead to a crash." Why doesn't raising the limit simply allow deeper, safe recursion?
The recursion limit is a proxy for the real constraint, actual available C stack space, which is platform-dependent and finite regardless of what the configured limit says. Setting the limit higher than the platform's actual available stack can support doesn't create more stack space, it just removes the early warning that would have raised a clean `RecursionError`, so recursion can now run deep enough to exhaust the real stack and crash the process with a low-level segmentation fault instead, a worse failure mode than the exception the limit was preventing in the first place.
Given the risk of hitting a recursion limit, when would you rewrite a recursive algorithm iteratively, and what does that actually trade away?
Rewrite iteratively when the recursion depth scales with input size in a way that could plausibly exceed the platform's real stack capacity, deep tree traversals, recursive descent over large or adversarial inputs, anything where "how deep" isn't bounded by a small constant. The trade is code clarity: many recursive algorithms (tree traversal, divide-and-conquer, backtracking) read far more naturally as recursion, mirroring the problem's own recursive structure, and converting them to an explicit-stack iterative version, while removing the depth risk entirely, usually costs some of that direct correspondence between code and problem structure.
What does it mean for a sorting algorithm to be "stable," and why does that matter for sorting by multiple keys in separate passes?
A stable sort guarantees that when two elements compare as equal under the current sort key, their original relative order is preserved rather than left unspecified. This matters directly for multi-key sorting done as a series of single-key sorts: sort by a secondary key first, then stably sort by the primary key, and elements sharing the same primary key retain their secondary-key order from the first pass, correctly producing a combined sort by (primary, secondary) without needing a single comparator that handles both keys at once. An unstable sort would silently scramble that secondary ordering among equal-primary-key elements.
Why does Python's sort achieve O(n) in the best case rather than always costing O(n log n) like a textbook mergesort?
Python uses Timsort, which specifically looks for and exploits "runs," contiguous stretches of already-ordered (or reverse-ordered) elements already present in the input, merging those runs rather than treating the data as uniformly random. Fully-sorted input is the extreme case of this: it's already one giant run, so Timsort recognizes it and finishes in linear time instead of doing the full comparison work a naive O(n log n) sort would perform regardless of input order. This is exactly why Timsort performs so well on real-world data, which is very often partially sorted already, not uniformly random.
An O(n^2) sort can be faster than an O(n log n) sort for small inputs. Why, and why doesn't that matter for a general-purpose sort function?
Big O describes asymptotic growth, not actual runtime, and O(n^2) algorithms often have smaller constant factors and simpler inner loops (no recursion or merge-buffer overhead) that make them genuinely faster in wall-clock time for small n, even though the more sophisticated O(n log n) algorithm would eventually win as n grows. This is exactly why production sort implementations, including Timsort, special-case small subarrays with a simple insertion sort internally rather than using the full merge-sort machinery on tiny inputs, getting the best of both regimes instead of picking one algorithm for every input size.
In the token bucket algorithm, what do the "rate" and "burst" settings each actually control?
The rate is how many tokens get added to the bucket per second, the steady-state throughput the API is designed to sustain indefinitely. The burst is the bucket's total capacity, the maximum number of tokens that can accumulate and therefore the largest spike of concurrent requests the API will accept in a single instant before it starts rejecting anything further. A request consumes one token; as long as the bucket has a token available, the request proceeds immediately, rate and burst are two independent numbers, not one combined setting, because sustained throughput and tolerance for short spikes are genuinely different things to configure.
What is an "LLM-graded" eval, and when would you reach for it instead of exact-match or similarity-based grading?
An LLM-graded eval uses a separate model call to judge a subjective quality of the output, tone, empathy, professionalism, on a numeric scale or binary classification, rather than checking it against one fixed correct answer. Exact-match grading only works when there's one right answer (a category label); similarity-based grading (cosine similarity between embeddings) works when wording can vary but meaning should match a reference. LLM-graded evals are the right tool specifically for qualities that are inherently subjective and hard to define with a fixed rule or reference string, at the cost of being noisier and more expensive to run than a simple string comparison.
Why does a real ring hash implementation give each host many positions on the ring instead of just one, and what problem would a single position per host cause?
A host thrown onto the ring at just one point can end up, purely by chance, owning a disproportionately large or small arc of the ring if the hash values happen to land unevenly, since with few points there's no averaging effect smoothing out the randomness. Assigning each host many positions on the ring, scaled by that host's intended weight, so a double-weight host gets roughly twice as many ring entries as a single-weight one, averages out that randomness across many smaller arcs per host, producing a much more even overall traffic distribution than a single coin-flip-like placement per host would.
Why does using a monotonically increasing field (a sequential ID, a timestamp) as a shard key concentrate all new writes onto one shard, even with range-based sharding across many shards?
With range-based sharding, chunks are assigned contiguous ranges of shard-key values, and a monotonically increasing key means every new document's value is higher than every previously inserted one, so all new inserts land in whatever chunk currently owns the highest range, which lives on one specific shard. Every other shard, holding older, lower-valued ranges, receives none of the new write traffic at all, the exact "hot shard" problem, all insert load concentrated on a single shard regardless of how many total shards the cluster has.