Amazon Data Scientist Interview Preparation Guide (Mid-Level)

Direct answer

Walk the array once while maintaining a hash map from value to the index where you first saw it. For each element x at index i, check whether target - x is already a key in the map before inserting x itself; if it is, you've found the pair in that same pass. That gives $O(n)$ average time using $O(n)$ extra space for the map, which is the best achievable without assuming the array is sorted, since you need to have looked at the data at least once to guarantee you haven't missed a valid pair; what you trade for that speed is the extra memory the map uses.

Approach

• Keep a dictionary seen mapping each value to the first index it appeared at.
• For each index i and value x, compute need = target - x and check seen for need before adding x to seen; checking first is what prevents pairing an element with itself when target == 2 * x.
• Return the pair of indices the moment a match is found; a single pass suffices.

from typing import List, Optional


def two_sum(nums: List[int], target: int) -> Optional[List[int]]:
    """Returns indices [i, j] such that nums[i] + nums[j] == target.
    Average O(n) time, O(n) space."""
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        if x not in seen:
            seen[x] = i
    return None


if __name__ == "__main__":
    print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
    print(two_sum([3, 3], 6))            # [0, 1]
    print(two_sum([1, 2, 3], 100))       # None

Running this prints [0, 1], [0, 1], and None. In the second case, target 6 with nums = [3, 3]: at i=0, need=3 isn't in seen yet, so 3 is stored at index 0; at i=1, need=3 is now in seen, giving [0, 1], correctly using two distinct indices for the same value rather than pairing index 0 with itself.

Key points

• Checking for the complement before inserting the current value is what stops the algorithm from matching an element with itself when target equals twice that element's value.
• "Average" $O(n)$, not worst-case, is the honest label: each hash map operation is $O(1)$ on average given a reasonably distributed hash, but an input engineered to collide against the hash function could in principle degrade individual lookups, which is a real (if unusual) concern in adversarial settings.
• The streaming variant, where you can't store the whole array up front, still needs $O(n)$ auxiliary memory for values seen so far, since you must remember what's already been scanned; there's no way around that memory cost unless an additional constraint (like a bounded value range) lets you swap the hash map for a fixed-size bitset.

Complexity

Time: $O(n)$ average (n hash map operations, each $O(1)$ average). Space: $O(n)$ for the seen map.

Edge cases

• No valid pair exists: the function should signal that clearly (returning None here, or raising, depending on the calling convention) rather than silently returning a wrong pair.
• Duplicate values that sum to the target: handled correctly by storing the first occurrence and checking the complement before inserting the current value.
• Negative numbers: work without special-casing, since dictionary keys and arithmetic on target - x don't assume non-negative values.
• An empty array or an array with fewer than two elements: no valid pair is possible.

Quick answer

With a Beta(1,1) (uniform) prior on the success rate and Binomial data, the Beta family is conjugate to the Binomial likelihood: this means combining a Beta prior with Binomial data always produces another Beta distribution as the posterior, so no numerical integration is needed, the posterior parameters are just the prior's parameters plus the observed successes and failures. With 30 successes out of 100 trials, that gives a posterior mean of about 0.304 and a 95% credible interval of roughly [0.219, 0.396], computed below.

Framework: Beta-Binomial conjugacy

For a Beta$(\alpha, \beta)$ prior and $k$ successes in $n$ trials:

The 95% credible interval is the interval between the 2.5th and 97.5th percentiles of that posterior Beta distribution.

Worked example

$k = 30$, $n = 100$, prior Beta(1,1):

from scipy import stats

k, n = 30, 100
a0, b0 = 1, 1  # Beta(1,1) prior
a_post, b_post = a0 + k, b0 + (n - k)
post_mean = a_post / (a_post + b_post)
ci_lo, ci_hi = stats.beta.ppf([0.025, 0.975], a_post, b_post)
print(f"posterior Beta({a_post},{b_post}), mean={post_mean:.4f}, 95% CI=({ci_lo:.4f}, {ci_hi:.4f})")
# posterior Beta(31,71), mean=0.3039, 95% CI=(0.2190, 0.3961)

Posterior mean $\approx 0.3039$, 95% credible interval $\approx [0.2190, 0.3961]$.

Shifting to an informative prior, Beta(2,2):

from scipy import stats

k, n = 30, 100
a0b, b0b = 2, 2  # Beta(2,2) prior
a_post_b, b_post_b = a0b + k, b0b + (n - k)
post_mean_b = a_post_b / (a_post_b + b_post_b)
ci_lo_b, ci_hi_b = stats.beta.ppf([0.025, 0.975], a_post_b, b_post_b)
print(f"posterior Beta({a_post_b},{b_post_b}), mean={post_mean_b:.4f}, 95% CI=({ci_lo_b:.4f}, {ci_hi_b:.4f})")
# posterior Beta(32,72), mean=0.3077, 95% CI=(0.2231, 0.3992)

Beta(2,2) is still centered at 0.5 but has slightly more concentrated mass than Beta(1,1), so it pulls the posterior mean up very slightly (0.3039 to 0.3077) and narrows the interval marginally. With $n=100$ observed trials, the data dominates either weak prior; the shift is small because both priors are only worth 2-4 pseudo-observations against 100 real ones.

Credible interval vs. confidence interval

The Wald interval, computed from $\hat p = 0.30$, $SE = \sqrt{0.30 \times 0.70 / 100} \approx 0.0458$, gives $[0.210, 0.390]$, close to the Beta(1,1) credible interval because a flat prior contributes almost no information beyond what the data already says. This convergence is the general pattern: with weak priors and reasonably large $n$, credible and confidence intervals often land close together numerically, even though what they claim to mean is fundamentally different.

Trade-offs and pitfalls

• The 95%-probability statement is only valid for the credible interval, not the confidence interval. Interviewers often listen for whether a candidate slips and says "95% probability the true rate is in this range" about a frequentist CI; that statement is only correct for the Bayesian interval.
• A subjective prior invites scrutiny. Beta(2,2) here was picked as illustratively "a bit more informative than uniform"; in practice, an informative prior needs to be justified from prior data (e.g. rates observed on similar features historically), not chosen to nudge the result.
• With very little data, prior choice dominates and this distinction matters a lot; with $n=100$ here it barely moves the estimate, but the same exercise with $n=10$ would show Beta(2,2) and Beta(1,1) diverging noticeably.
• The Beta-Binomial conjugacy is a special case. It makes this calculation closed-form; most real posteriors (non-conjugate priors, hierarchical models) require MCMC or variational inference to get a credible interval numerically.

Direct answer: Permutation importance measures how much a model's held-out performance drops when a single feature's values are randomly shuffled (breaking its relationship with the target while leaving everything else intact), and the size of that performance drop, not any internal model statistic, is the importance score; grouped shuffling extends this to measure the joint importance of a set of correlated features together.

Structured elaboration:
The implementation shuffles one feature (or a named group of features together) across the validation set, re-scores the model on the shuffled data, and records the drop from the model's baseline (unshuffled) score; repeating the shuffle multiple times and averaging gives a stable estimate along with a measure of its variability, since a single shuffle is itself a random draw and can be noisy.

Whether to retrain the model per permutation is a real design choice: the standard and much cheaper approach REUSES the already-fitted model and only permutes the validation data, which measures "how much does the model currently rely on this feature," not "how much predictive signal does this feature contain in principle" (retraining without the feature entirely, called drop-column importance, answers a related but distinct question and is far more expensive since it requires a full refit per feature).

Worked example: Verified on a synthetic dataset with a known ground truth (feature 0 with a strong true coefficient, feature 2 with a moderate one, features 1 and 3 pure noise): permutation importance with 20 repeats correctly ranked feature 0's importance (mean score drop ≈ 1.72) well above feature 2's (≈ 0.28), with both pure-noise features scoring statistically indistinguishable from zero (≈ 0.0001), exactly recovering the known relative signal strength of each feature. This kind of ground-truth-recovery check, not just "the code runs," is what actually validates a permutation-importance implementation.

Trade-offs and pitfalls: Permutation importance's well-known limitation is with correlated features: shuffling one feature of a correlated pair produces a data point the model has never really seen in that combination during training (an implausible combination of other, unshuffled correlated features), which can understate the shuffled feature's true importance since the model may still partially "recover" the lost signal from its correlated partner. This is exactly why grouped shuffling (permuting a whole correlated cluster together) is offered as an option, since it avoids creating that implausible combination.

Direct answer

The nested loop is quadratic because for every one of the $n$ records on the left, it scans all $m$ records on the right looking for a key match, doing $n \times m$ comparisons total regardless of how many actually match. Building a dictionary keyed on the join key from one side first turns each lookup into an expected $O(1)$ hash-table probe instead of an $O(m)$ scan, bringing the whole join down to expected $O(n + m)$: build the index once, then probe it once per record on the other side.

Structured elaboration

Why the nested loop is quadratic: for each of the $n$ left records, the inner loop walks the entire right list looking for l[key] == r[key], whether or not it finds a match early. That is $n$ full passes over a list of size $m$, i.e. $O(n \times m)$ comparisons, degenerating to $O(n^2)$ when the two sides are similar in size.

The hash-based fix: build a dictionary once, mapping each join key to the list of records on the smaller side that carry that key (a key can map to more than one record, so store a list per key, not a single record). Then iterate the other side once, and for each record, look up its key in the dictionary directly instead of scanning. Dictionary lookup is expected $O(1)$ (amortized, assuming a reasonable key-hash distribution), so the whole pass over the second side is expected $O(m)$, and building the index was $O(n)$, giving expected $O(n + m)$ overall. This is the same idea a database's hash-join operator uses internally.

Which side to build the index on: build the hash table from the smaller of the two inputs and probe with the larger one. The index costs memory proportional to the side you build it from, so building on the smaller side minimizes peak memory; which side you probe with does not change the time complexity, only which side pays the memory cost.

Worked example

Verified on CPython 3.12, confirming the hash-based join produces the identical row set as the nested-loop version:

from collections import defaultdict

def nested_join(left, right, key):
    result = []
    for l in left:
        for r in right:
            if l[key] == r[key]:
                result.append({**l, **r})
    return result

def hash_join(left, right, key):
    if len(left) <= len(right):
        build, probe, build_is_left = left, right, True
    else:
        build, probe, build_is_left = right, left, False

    table = defaultdict(list)
    for b in build:
        table[b[key]].append(b)

    result = []
    for p in probe:
        for m in table.get(p[key], ()):
            combined = {**m, **p} if build_is_left else {**p, **m}
            result.append(combined)
    return result

left = [{"id": i, "l": f"l{i}"} for i in range(200)]
right = [{"id": i, "r": f"r{i}"} for i in range(100, 300)]

r1 = sorted(nested_join(left, right, "id"), key=lambda d: d["id"])
r2 = sorted(hash_join(left, right, "id"), key=lambda d: d["id"])
print("row counts equal:", len(r1) == len(r2), len(r1))
print("same content:", r1 == r2)

Output: row counts equal: True 100 and same content: True, confirming both approaches return the same 100 matched rows for this overlapping-range test data.

Trade-offs & pitfalls

• Complexity: nested loop is $O(n \times m)$ time, $O(1)$ extra space; hash join is expected $O(n + m)$ time, $O(b)$ extra space where $b$ is the size of whichever side you build the index from.
• Edge case: many-to-many joins (a key repeated on both sides) need every match emitted, storing a list per key (not overwriting a single slot per key) handles this correctly; a common bug is using a plain dict mapping key to one record, which silently drops all but the last record for a repeated key.
• Edge case: composite keys (joining on more than one column) work the same way as long as the key you hash on is itself hashable, typically a tuple of the individual field values rather than a single field.
• A related antipattern worth recognizing, even outside a join: building a dict of lists to group records by key, and then aggregating (summing, counting) by scanning each list afterward, pays the memory cost of holding every raw record in memory per key and then pays an extra full pass to aggregate. If you only need an aggregate (a count, a sum) and not the individual grouped records, aggregate incrementally as you go (defaultdict(int) with += on each record) instead of collecting a defaultdict(list) first and reducing it afterward; the collect-then-reduce version uses $O(n)$ memory it does not need to and does the aggregation work twice.
• Hash join assumes the build side fits in memory. If it does not, this degrades to either an external (disk-backed) hash join, partitioning both sides into buckets that each fit in memory, or a sort-merge join, sorting both sides by key and merging in one linear pass, at the cost of the sort itself ($O(n \log n)$).
• If the data is already sorted on the join key (for example, coming from an ordered log or an indexed source), a sort-merge join can beat a hash join outright, since it avoids building any auxiliary index at all; the hash-based approach is the right default only when you cannot assume sorted input.

Situation: I was asked to build an executive dashboard translating complex KPIs into actionable insight for C-level stakeholders with limited data literacy.

Design principles I would apply:

• Clarity first: surface a single top-level metric per card; avoid clutter. Use plain language and consistent units.
• Hierarchy & progressive disclosure: show summary-level KPIs up top, with drill-down links for analysts.
• Actionability: pair each metric with context (target, variance, trend) and recommended next steps.
• Cognitive load reduction: limit colors (2–3), use preattentive attributes (position, length) for comparisons, avoid 3D visuals.
• Reliability & provenance: show data timestamp, data sources, and confidence intervals where relevant.
• Accessibility & responsiveness: readable fonts, contrast, mobile-friendly layouts.

Visualizations by key scenario:

• Overall business health (revenue, margin): KPI tiles + trend sparklines and month-over-month % change.
• Growth vs target: bullet charts (target vs actual vs forecast) — precise comparison in compact space.
• Cohort retention / churn: cohort heatmap for retention patterns and a line chart for overall churn with shaded CI.
• Funnel conversion: stacked funnel chart with conversion rates annotated and hover details.
• Forecasts & uncertainty: line chart with forecasted band (95% CI) and scenario toggles (best/worst).
• Driver analysis (what’s moving revenue): bar chart with sorted contribution, and a Pareto chart for top drivers.
• Alerts & anomalies: indicator list with traffic-light statuses and links to explainers.

Validation with stakeholders:

• Discovery interviews to list decisions executives must make and KPIs they trust.
• Build low-fidelity mockups and run rapid usability tests (5–8 execs) to confirm comprehension and actionability.
• Prototype with real data in a sandbox and run a walkthrough; gather feedback on missing context or confusing visuals.
• Define success metrics: time-to-decision, % of decisions referencing the dashboard, and stakeholder satisfaction (survey).
• Iterate weekly for first month, add logging to measure feature use (drills, filters) and adjust based on usage and qualitative feedback.

This approach ensures the dashboard is simple, trustworthy, and directly tied to executives’ decisions.

Direct answer

Keep a single, easy-to-find decision log tied directly to the work it affects: what was decided, the options considered, the reasoning, and who owns it, updated by whoever is making the decision at the moment it is made, not reconstructed later from memory.

Structured elaboration

What belongs in an entry

A short, consistent structure works better than a long one, because people will actually fill it out: a title, the date, who owns it, the context in one or two sentences, the options considered with their trade-offs, the decision itself, and the reasoning behind it in a few bullet points.

Where it lives

The log needs to be one discoverable place, linked from the tickets, docs, or roadmap items it affects, not scattered across meeting notes and chat threads. A shared doc or wiki page with a simple table works; the tool matters less than the discipline of always linking to it.

Who keeps it current

The person who owns the decision, not a rotating scribe with no stake in it, writes or finalizes the entry, ideally right after the decision is made, while the reasoning is still fresh and easy to state accurately.

How it gets used afterward

In retrospectives, revisit decisions that affected the outcome and check whether the original assumptions held. For onboarding, a short list of the most consequential recent decisions gives a new team member the context that would otherwise take weeks of osmosis to pick up.

Worked example

A team is deciding between two ways to notify users of an event: a push notification versus an in-app banner. The entry, once decided, looks like this: title, "Notification channel for event alerts"; date and owner, the decision owner's name and the date; context, users were missing time-sensitive alerts under the current in-app-only approach; options considered, push notification (faster delivery, requires a new permission prompt), in-app banner only (no new permission needed, slower to be seen), and both channels (best coverage, more engineering and support surface); decision, push notification with an in-app banner as a fallback for users who decline the permission; reasoning, the delay in the in-app-only approach was the specific problem being solved, and the fallback covers users who opt out.

Anyone who later asks why the team does not just use an in-app banner, since it is simpler, can read this entry and see the trade-off was already considered, rather than re-litigating it from scratch.

Trade-offs and pitfalls

A log nobody updates is worse than no log: it creates false confidence that the reasoning is captured somewhere, while actually going stale. The fix is keeping entries short enough that updating one takes minutes, rather than requiring a formal write-up every time.

A log can also be used as a weapon later, such as insisting a past decision still holds in a situation where circumstances genuinely changed and revisiting was the right call. The log should record reasoning, not lock in a decision forever; a review date or a note on when to re-evaluate keeps it a living reference instead of a trap.

Reach for SQL whenever the task needs to run against the full underlying data rather than a manually pasted extract, needs to be exactly reproducible, or needs to combine several tables by a key. A spreadsheet's VLOOKUP and pivot table are fine for a small, single-table slice a person can eyeball once; they degrade badly as the row count, the number of source tables, or the need to repeat the calculation correctly next month all grow.

Two concrete examples

1. Joining and deduplicating across multiple sources. Combining a CRM export, a billing export, and a support-ticket export by customer_id into one row per customer. VLOOKUP handles one lookup column against one other sheet; the moment a task needs a three-way join with duplicate keys on either side, VLOOKUP returns only the first match and silently drops or miscounts the rest. A SQL JOIN handles the full match set deterministically, and a GROUP BY handles the deduplication explicitly and visibly.

2. Any calculation someone else needs to reproduce exactly, or that needs to run on a schedule. A pivot table's field configuration lives inside the spreadsheet's UI: it isn't version-controlled, isn't easy to diff, and has to be manually rebuilt correctly by whoever opens the file next. A saved SQL query (or a view) is text: it runs identically every time, can sit in source control, and can be scheduled without a human reopening a workbook.

The reverse direction: SQL's equivalent of a pivot table or VLOOKUP

A GROUP BY with aggregate functions is SQL's version of a pivot table's row-grouping plus value-aggregation. A JOIN on a shared key is SQL's version of VLOOKUP or INDEX-MATCH: instead of "look up this key in that other sheet's range," it's "match every row in table B to the row in table A that shares this key," for as many tables as needed at once.

Worked example

CREATE TABLE orders (
  order_id INTEGER PRIMARY KEY,
  region   TEXT,
  amount   NUMERIC
);

INSERT INTO orders (region, amount) VALUES
  ('East', 400), ('East', 600), ('West', 150),
  ('West', 200), ('West', 250), ('North', 2400);

SELECT
  region,
  SUM(amount) AS region_revenue,
  ROUND(100.0 * SUM(amount) / (SELECT SUM(amount) FROM orders), 1) AS pct_of_total
FROM orders
GROUP BY region
ORDER BY region_revenue DESC;

Result:

┌────────┬────────────────┬──────────────┐
│ region │ region_revenue │ pct_of_total │
├────────┼────────────────┼──────────────┤
│ North  │ 2400           │ 60.0         │
│ East   │ 1000           │ 25.0         │
│ West   │ 600            │ 15.0         │
└────────┴────────────────┴──────────────┘

A pivot table gets the region_revenue column easily. Getting pct_of_total right, as a value that stays correct if a new region is added later, needs either a spreadsheet formula referencing a moving total range (easy to break: forgetting to update the range after adding a row is a classic spreadsheet bug) or exactly this scalar subquery, which recomputes the grand total from the same source rows every time the query runs.

Trade-offs & pitfalls

• SQL is not better at everything. Ad-hoc, throwaway exploration by someone without database access, or the final polished chart for a stakeholder deck, is usually faster and clearer done in a spreadsheet or the BI layer.
• Centralize a calculation once in SQL (a shared view) instead of letting five dashboards each compute "active users" a slightly different way in their own pivot tables. This is one of the most common reasons dashboards disagree with each other.
• Common wrong turn: over-engineering a one-time, 20-row question into a SQL pipeline when a five-minute spreadsheet look would answer it. Match the tool to whether the task repeats or needs to scale, not to which tool seems more technical.

Direct answer
The utility tracks the best metric seen so far, a counter of epochs since that best, and a snapshot of the model's weights at the best epoch; it signals "stop" once the counter reaches the patience, and the caller restores the saved best weights.

Structured elaboration
Key design points: a min_delta threshold so tiny, noise-level improvements don't reset the patience counter; a mode ("min" for loss, "max" for accuracy) so the same class works for either direction of improvement; and capturing a deep copy of the weights at each new best, not just remembering the epoch number, since training continues to mutate the weights after that point.

Worked example (executed)

class EarlyStopping:
    def __init__(self, patience=5, min_delta=0.0, mode="min"):
        self.patience = patience
        self.min_delta = min_delta
        self.mode = mode
        self.best = None
        self.count = 0
        self.best_state = None
        self.should_stop = False

    def step(self, metric, model):
        improved = (self.best is None or
                    (metric < self.best - self.min_delta if self.mode == "min"
                     else metric > self.best + self.min_delta))
        if improved:
            self.best = metric
            self.count = 0
            self.best_state = {k: v.clone() for k, v in model.state_dict().items()}
        else:
            self.count += 1
            if self.count >= self.patience:
                self.should_stop = True
        return self.should_stop

Tested against the validation-loss sequence [1.0, 0.8, 0.65, 0.64, 0.645, 0.646, 0.647] with patience=3, min_delta=1e-3: the true best is 0.64 at epoch 3, and the routine correctly fires should_stop at epoch 6, exactly 3 non-improving epochs later, having captured a full weight snapshot at epoch 3 to restore. Confirmed es.best_state is not None and the stop epoch matches the expected patience arithmetic exactly.

Trade-offs & pitfalls
Cloning the full model state dict on every improvement is memory-cheap for small models but can be expensive for large ones (billions of parameters); at that scale, teams typically checkpoint to disk on improvement instead of holding a second copy in memory.

Direct answer

Beyond the primary conversion metric, I would monitor six guardrails on a checkout redesign: cart abandonment rate, average order value, payment failure rate, checkout completion time, support-contact rate for checkout, and refund or chargeback rate. Each one catches a different way the redesign could look like a conversion win while quietly making something else worse.

Structured elaboration

Stratification and sequential stopping rules

Stratify every guardrail check by segment (device, region, new versus returning user, traffic source), because a guardrail regression can be isolated to one stratum, such as mobile checkout, while the blended average still looks flat. Pre-register a stopping rule for each guardrail before launch: define the maximum acceptable regression (for example, no more than a 1 percentage-point rise in payment failure rate) and a fixed set of interim looks (day 3, day 7, day 14) using a sequential-testing correction rather than checking continuously and stopping the moment a guardrail dips, which inflates the false-positive rate.

Worked example

Suppose payment failure rate is the guardrail under scrutiny at an interim look: control shows 100 failures out of 5,000 orders, treatment shows 140 failures out of 5,000 orders.

Since 2.61 exceeds the 1.96 threshold for a two-sided 95% test, the payment-failure regression is statistically significant at this interim look, even though the primary conversion metric may look favorable. That is the guardrail doing its job: pause and investigate before shipping.

Trade-offs & pitfalls

• Too many guardrails (beyond roughly eight to ten) create alert fatigue and a multiple-comparisons problem; prioritize by blast radius and reversibility, not by "nice to have."
• Checking guardrails continuously without a pre-registered stopping rule inflates false alarms through repeated peeking; agree on the look schedule and correction method before launch.
• A guardrail that only exists as an aggregate can hide a segment-level regression; always stratify the check before declaring a guardrail clean.
• Guardrails should be set against a pre-registered non-inferiority margin, not "any negative movement," or nearly every experiment will trip one on noise alone.

Direct answer. Nested loop is cheapest when the outer side is small and the inner side has a cheap way to be probed (typically an index); hash join is the workhorse for large, unsorted inputs where one side comfortably fits in memory to build a hash table from; sort-merge join wins when both inputs are already sorted (or cheaply sortable) on the join key, since it can then walk both in a single linear pass with no random lookups and no hash table at all.

Structured elaboration. Nested loop's cost is roughly (outer rows) times (cost per inner probe); it degrades badly the moment the outer side is larger than expected, since every extra outer row multiplies the total work. Hash join's cost is roughly (build side rows, to construct the hash table) plus (probe side rows, each a cheap in-memory lookup); its main risk is memory: if the build side is bigger than the memory budget allotted, the hash table spills to disk in partitions, which is far slower than an in-memory hash join but still usually better than a nested loop over the same volumes. Sort-merge needs both inputs sorted; if an index already provides that order, the "sort" part is free and the join itself is a fast linear merge, but if neither input is sorted and both are large, the up-front sort cost can make this the worst of the three options.

Worked example. Joining a 50-million-row fact table to a 200-row lookup table: a nested loop with an index on the fact table's join key (probing the fact table once per lookup row) does roughly 200 cheap index probes, which is far cheaper than building a hash table from 50 million rows. Flip the sizes, joining two roughly-equal, unsorted multi-million-row tables, and a hash join (build from the smaller of the two, probe with the larger) beats a nested loop by orders of magnitude, since nested loop would need tens of millions of probes instead of one hash table build plus one linear probe pass.

Trade-offs and pitfalls. None of the three algorithms is universally best; the right one is a function of the relative sizes of the two inputs, whether either side is already sorted or indexed on the join key, and how much memory is available for a hash table. A senior red flag is seeing a nested loop join over two large, unindexed inputs (that's the shape most likely to be a genuine planner mistake, usually traced back to a cardinality misestimate) versus seeing it over one genuinely small input joined to a large indexed one (that's usually correct and fast).