Amazon SDE III (Senior Software Engineer) Interview Preparation Guide

Goal: Compare LRU in-process cache vs dedicated Redis layer under realistic workload to decide which yields better latency, cost, reliability, and operational complexity.

Experiment design

• Environment: Staging cluster mirroring prod (same app servers, network, CPU, mem). Deploy two variants behind a load generator: (A) in-process LRU, (B) Redis cluster. Ensure same app logic and cache key/schema.
• Traffic: Replay production traces (preferred) or synthesize using distributions: 70% reads, 30% writes; key popularity follows Zipf (s=0.8); working set size = 2×, 5×, 10× of per-process cache capacity to test eviction.

Metrics (collected per-second, aggregated)

• Hit rate: cache hits / cache lookups (separate for read/write).
• End-to-end latency: p50/p95/p99 of request latency (total) and cache lookup latency (local vs network).
• Tail latency impact: p99/p999.
• Throughput: requests/sec sustained.
• Resource usage: memory per process, Redis memory, CPU, network I/O.
• Cost proxy: Redis instance cost + network egress; operational metrics (failures, reconnections).
• Correctness: stale reads, consistency violations for writes (if applicable).
• JVM/GC pause metrics for in-process.

Test harness

• Load generator that replays traces at configurable concurrency (k6, Gatling, custom).
• Instrumentation: OpenTelemetry + metrics exporter; app logs cache events.
• Automated scenario runner to run multiple repeats, randomize seed, and collect traces.

Warm-up / steady-state

• Warm-up: run traffic until hit rates and latencies stabilize (monitor moving averages) — typically 5-15 minutes depending on system. Exclude warm-up from results.
• Steady-state: collect at least 30 minutes of steady traffic per run; repeat runs (≥3) to get variance.

Failure injection

• Network latency/jitter between app and Redis (tc/netem).
• Redis node failure and recovery (kill primary, simulate failover).
• High GC events in app (allocate memory pressure) to observe in-process degradation.
• Increased load spike (2–5× for short bursts) to test eviction and pipeline saturation.

Analysis & interpretation

• Primary decision axes: tail latency and reliability vs. hit rate and cost.
• If in-process gives significantly lower p95/p99 and acceptable hit rate with tolerable memory use and no major GC impact, prefer LRU for low-latency reads.
• If Redis yields higher effective hit rate across many app instances (global cache), lower total memory footprint, and acceptable tail latency with robust failover, prefer Redis.
• If Redis shows high p99 due to network/failures, but has better consistency and lower overall memory cost, consider hybrid: local LRU with Redis as second-level cache (cache-aside) — tune TTLs and admission policy.
• Use statistical tests (t-test or nonparametric) on p95/p99 and hit rates across runs to ensure differences are significant.
• Operational considerations: adoption cost, monitoring needs, runbook for failover, and SLA alignment.

Actionable outputs

• Recommendation with quantified trade-offs (delta p99, delta cost, hit-rate diff).
• Sensitivity table across working set sizes and failure modes.
• Follow-ups: if hybrid promising, run A/B test in canary traffic; provision dashboards and alerts (cache miss surges, Redis latency, GC pauses).

Direct answer
A post-remediation measurement plan needs a baseline captured BEFORE the work starts, a defined follow-up cadence, a mix of leading indicators (early, faster-to-move) and lagging indicators (slower, more definitive), and a results presentation tailored differently for engineering teams versus business stakeholders.

Structured elaboration

1. Baseline metrics captured before work begins: cycle time, incident rate, and coverage in the affected area, snapshotted at the START of the remediation, not estimated retroactively (retroactive baselines are unreliable and easy to dispute).
2. Follow-up cadence: leading indicators (build time, coverage, PR cycle time) checked at 2 and 6 weeks post-remediation, since they move fast; lagging indicators (incident rate, bug escape rate) checked at 3 and 6 months, since they need more data to be statistically meaningful.
3. Leading vs lagging: leading indicators tell you EARLY whether the remediation is working as intended (did complexity actually drop, did build time actually improve); lagging indicators tell you whether it translated into the outcome that mattered (fewer incidents, less customer impact). Report both, since a leading indicator improving without a corresponding lagging-indicator improvement is itself a useful, actionable finding (the fix addressed a symptom, not the root cause).
4. Presentation: engineering teams get the full metric set with context (what changed, why, and the confidence level); business stakeholders get the 2-3 metrics that map directly to business impact (incident rate, deploy frequency), framed against the original business case that justified the work.

Worked example
A refactor targeting a high-complexity billing module: baseline (captured at kickoff) shows cyclomatic complexity (a count of the independent decision paths through a piece of code, roughly how many branches and loops it has; higher means more ways a change can break something) at 28, build time at 9 minutes, incident rate at 3/month. At 2 weeks post-remediation, complexity has dropped to 14 and build time to 5 minutes (leading indicators moving as expected). At 3 months, incident rate has dropped to 1/month (lagging indicator confirming the leading indicators translated into real impact). Presented to engineering: the full trend with the specific architectural changes that drove each metric. Presented to leadership: "incident rate in billing down two-thirds since the Q2 remediation, consistent with the reduced complexity we measured immediately after the work."

Trade-offs & pitfalls
Measuring only immediately after the work (leading indicators) and declaring victory skips the harder, more important lagging-indicator confirmation; a remediation that improves complexity and coverage numbers but shows no corresponding drop in incidents over the following quarter is a finding worth reporting honestly, not one to omit because it complicates the success narrative.

User-space networking stacks like DPDK reduce syscall and copy overhead by removing the kernel from the fast path: the application polls NIC rings directly in user space (poll-mode drivers) instead of relying on interrupt-driven, context-switching packet delivery through the kernel networking stack. This avoids expensive syscalls (recvmsg/sendmsg), reduces context switches, and eliminates kernel/user data copies by mapping huge contiguous physical pages into user space so DMA can write directly into application buffers (enabling zero-copy).

Requirements and effects:

• Hugepages: DPDK uses hugepages (2MB/1GB) to allocate physically contiguous memory for huge RX/TX mempools and to reduce TLB pressure — necessary for DMA and predictable latency.
• NIC driver support: The NIC must support a DPDK-compatible PMD (poll-mode driver) or SR-IOV/VF passthrough. Some features (RSS, checksum offload, HW timestamping) should be supported in the PMD to preserve function and offload CPU.
• Zero-copy: True zero-copy requires the NIC and driver to place packet payloads into application-owned buffers. DPDK's rte_mbuf and mempool design let apps reuse buffers without copies; when bridging to kernel stacks or other apps you often need copy or shared memory glue.
• Batching: DPDK favors batch RX/TX to amortize per-packet overhead. Pulling N packets per poll and processing in bulk improves throughput and CPU efficiency, but increases per-packet tail latency jitter if batches wait too long.
• Packet ordering: Poll-mode drivers preserve per-queue ordering; to maintain global ordering you must keep flows on same RX/TX queue (RSS or flow steering) and avoid parallel reordering in multi-threaded processing. Reordering can also occur when enabling multiple TX queues without careful synchronization.

Integration approach with an existing application:

1. Evaluate function split: isolate the packet I/O layer and decide whether the app will be fully DPDK-native or hybrid (DPDK user-space datapath + kernel control plane).
2. Add a DPDK initialization path: EAL init, reserve hugepages, bind NIC VF/PCI to DPDK PMD (or use AF_XDP for lighter-weight kernel-bypass).
3. Replace socket I/O with a wrapper layer exposing the same interface but using rte_eth_rx_burst / rte_eth_tx_burst and rte_mbuf lifecycle (rx, process, tx, rte_pktmbuf_free).
4. Implement batching and poll loop with optional busy-poll sleep backoff to control CPU usage vs latency.
5. Handle configuration and fallbacks: keep a kernel socket fallback for control plane or management traffic, and provide memory/threading config to avoid interference.
6. Test correctness: validate ordering, offloads, VLANs, MTU, zero-copy behavior, and measure p95/p99 latency. Profile CPU/cache/TLB pressure and adjust hugepage sizes, core pinning, and NIC queue counts.

Trade-offs: kernel-bypass maximizes raw latency and throughput but increases complexity (memory management, security, OS integration), reduces portability, and requires careful NUMA/core pinning and watchdogs. For many systems, AF_XDP or hybrid designs offer middle-ground with less invasive changes.

Direct answer
A stateless approach (a signed token such as a JWT (JSON Web Token) carrying the session data) scales cleanly across many independently-deployed services and regions because any service instance can validate the token without needing to look anything up, at the cost of harder revocation and a token that, once issued, is difficult to invalidate before it naturally expires; a stateful approach (a shared session store, or sticky sessions at the load balancer) makes revocation and logout instantaneous, at the cost of needing that shared state to be available, fast, and consistent everywhere a request might land.

Structured elaboration
Security and revocation: a self-contained signed token is valid until it expires, no matter what happens on the server side, so immediate logout or a forced revocation (say, after a password change or a detected compromise) is hard to achieve without an additional mechanism, like a short token lifetime combined with a separate, checked-on-every-request revocation list (which reintroduces some of the shared-state lookup a stateless token was meant to avoid). A server-side session store makes logout and revocation trivial (just delete or invalidate the session record), since every service checks the current, authoritative state on each request. Session size and load balancing: a stateless token carries its own data on every request, so a large session payload adds overhead to every call and needs to stay reasonably small; sticky sessions route a given user consistently to the same backend instance holding their in-memory session, which avoids a shared store but makes load balancing less flexible (that instance failing loses the session, and rebalancing traffic away from a hot instance is constrained by which users are stuck to it) and doesn't scale cleanly across regions, since a user's session is now tied to a specific instance's location.

Worked example
For a web application serving 10M monthly active users across multiple regions, a stateless token is generally the better fit for the base authentication case, since it avoids needing a globally-consistent, low-latency session store that every region's services can reach quickly; the revocation gap is managed by keeping token lifetimes short (minutes to a couple of hours) and using refresh tokens (which ARE checked against a server-side store on each refresh) to balance the low-friction stateless validation for most requests against the ability to revoke access within a bounded, acceptable window. A legacy component that genuinely requires sticky sessions during a migration can be bridged with an adapter: a thin layer that translates the stateless token into whatever session format the legacy component expects, or a temporary session-affinity rule scoped only to that component's traffic, while the rest of the system moves to the fully stateless model.

Trade-offs and pitfalls
The common mistake with stateless tokens is putting too much or too sensitive data directly in the token (since anyone who can decode it, even without the signing key, can read its contents unless it's also encrypted), and underestimating how long a compromised token stays valid if the revocation story isn't designed deliberately. The common mistake with sticky sessions is treating them as a permanent architecture rather than what they usually are in a modern system, a legacy bridge or a stopgap, since they fundamentally limit how flexibly you can load-balance, fail over, and scale across regions compared to a genuinely stateless design.

Direct answer

I would stage the reskilling so it rides alongside real shipping work rather than stopping it: a small shared set of learning materials for everyone, pairing rotations that put people who have already ramped up alongside those still learning on real tickets, checkpoints tied to actual delivered work rather than a separate exam, and KPIs that track both team velocity and skill spread so we can see whether the balance is actually working, not just assume it.

Structured elaboration

Balancing shipping and ramp-up: instead of a hard stop-the-world training period, carve out a fixed, protected percentage of time per person per sprint for the new stack, and shift new feature work to the new stack gradually, team by team or component by component, so the whole organization is not blocked waiting for full fluency everywhere at once.

Learning materials: a small, curated internal set rather than "go read the official docs cold." An internal migration guide that maps concepts and idioms from the old stack to the new one specifically, since engineers already know the old stack and a mapping is faster than starting from zero, plus a short list of vetted external resources for deeper gaps.

Pairing rotations: rotate so someone who has ramped up on the new stack pairs with someone who has not, on a real ticket, for a bounded window such as a sprint, then rotate the pairs so tacit knowledge spreads instead of staying with the first few people who happened to learn it first, avoiding a bottleneck where only a couple of people can touch the new codebase.

Checkpoints: tie them to real delivered work rather than a quiz. Baseline competence is whether a person can independently take a small, well-scoped ticket in the new stack through code review with a normal number of review rounds; the next tier is whether they can review someone else's new-stack code.

KPIs: track the percentage of the team that has cleared the baseline checkpoint over time, skill spread; the ratio of new-stack to old-stack work being shipped, migration progress; and whether velocity or cycle time on new-stack tickets is converging toward the old baseline over time rather than staying permanently degraded, the actual signal that ramp-up happened rather than just exposure.

Worked example

A team of eight engineers sunsetting one backend framework for another over a planned two-quarter migration. Each engineer gets one day a week protected for the new stack for the first month, using an internal migration guide mapping the old framework's routing and data-access idioms to the new one's. Two engineers who piloted the new stack early each pair with two others for one sprint on a real, low-risk internal-tools ticket, then rotate to the next two, so by week six most of the team has shipped something real in the new stack with a partner. An engineer is considered baseline-competent once they have taken one ticket through review independently with a normal review-round count, not the extra rounds typical of very first attempts. KPI tracking over the quarter shows skill spread climbing toward full coverage, new-stack ticket share climbing as planned, and new-stack cycle time converging toward the old-stack baseline by around week eight, the point the team decides it is safe to stop protecting dedicated ramp-up time and treat the new stack as the default.

Trade-offs and pitfalls

If the protected ramp-up time is the first thing cut when a deadline gets tight, the whole program quietly dies, so it needs to be a real, visible commitment rather than an informal aspiration. Pairing rotations can bottleneck if too few people ramp up early, since they become the only pairing partners available and burn out, so the initial pilot group needs to be large enough to rotate. And checkpoints based on review-round count alone can be gamed by an overly lenient reviewer, so a second signal, whether the person can competently review someone else's code, matters as a check on the first.

Direct answer

The 0/1 knapsack DP state is dp[c] meaning "maximum total value achievable using a budget of exactly (or up to) c," updated per item by dp[c] = max(dp[c], dp[c - weight] + value), iterating capacities in descending order so each item is only used once. If the question changes from "maximize value" to "is some exact target sum achievable at all," the state becomes a boolean reachable[s] instead of a running maximum, using the identical recurrence shape (reachable[s] = reachable[s] or reachable[s - weight]) but tracking reachability instead of an optimum. This exact-sum variant is the same shape as the well-known Partition Equal Subset Sum problem, which asks whether a set of numbers can be split into two subsets with equal totals.

Structured elaboration

Value-maximization DP.

def knapsack_max_value(weights, values, capacity):
    """
    0/1 knapsack: maximum total value without exceeding capacity, each item
    at most once. dp[c] = best value achievable with budget c.
    Time O(n * capacity), Space O(capacity) (rolling 1D array).
    """
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # descending: each item used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

Feasibility (exact-sum) DP. Change the table's meaning from "best value so far" to "is this sum reachable," and change the update from a max to a boolean OR:

def subset_sum_feasible(weights, target):
    """
    Can some subset of weights sum to exactly target?
    reachable[s] = True if sum s is achievable using a subset of items seen
    so far. Same 0/1 recurrence as knapsack, but the DP value is a boolean
    "reachable" flag instead of a running maximum.
    Time O(n * target), Space O(target).
    """
    reachable = [False] * (target + 1)
    reachable[0] = True
    for w in weights:
        for s in range(target, w - 1, -1):
            if reachable[s - w]:
                reachable[s] = True
    return reachable[target]

Partition Equal Subset Sum is exactly this feasibility check with target set to half the total sum of the input numbers (if the total is odd, an equal split is impossible immediately, no DP needed). The same feasibility shape also applies to budget-constrained subset-selection outside pure combinatorics: for example, choosing dashboard KPIs or metrics under a display-cost budget, where each metric has a fixed "screen cost" and you want to know whether some subset exactly fills an allotted display budget (or, with the max-value version, which subset of metrics maximizes total business value within that budget).

Worked example

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_max_value(weights, values, 5))

Output: 7 (taking the weight-2/value-3 and weight-3/value-4 items exactly fills the capacity-5 budget for total value 7; no other combination of these items reaches higher value within capacity 5).

nums = [1, 5, 11, 5]
total = sum(nums)
print(total, total % 2 == 0, subset_sum_feasible(nums, total // 2) if total % 2 == 0 else None)

Output: 22 True True. The total is 22 (even), so an equal split needs a subset summing to 11; subset_sum_feasible confirms 11 is reachable (via 5 + 5 + 1), so [1, 5, 11, 5] can be partitioned into two equal-sum halves.

Trade-offs & pitfalls

Key points

• Greedy selection by value-to-weight ratio is optimal for the fractional knapsack (where you can take a fraction of an item) but is not guaranteed optimal for 0/1 knapsack, since taking a high-ratio item can leave awkward leftover capacity that a different combination would have used better.
• The feasibility DP is strictly cheaper to reason about than the value-maximization DP (booleans instead of running maxima), but it answers a narrower question: it tells you whether a target is reachable, not which subset achieves it, unless you also track parent pointers or reconstruct the choice by scanning backward through the table.
• Both DP variants are pseudo-polynomial: their cost scales with the numeric capacity or target value, not just the number of items, so a very large capacity or target (in the millions) can make the DP impractical even though the item count is small; that is where a greedy approximation or a meet-in-the-middle exact method becomes attractive.

Complexity

• Value-maximization: time $O(n \cdot W)$, space $O(W)$, where n is the item count and W is the capacity.
• Feasibility: time $O(n \cdot T)$, space $O(T)$, where T is the target sum.

Edge cases

• Target or capacity of 0: dp[0]/reachable[0] are the trivial base cases (empty selection), both handled directly.
• An item heavier than the remaining capacity: naturally excluded by the descending-range guard (w - 1 lower bound), never considered for smaller capacities.
• Odd total sum in the partition-equal-subset-sum framing: no DP needed at all, an equal-value split is impossible by simple arithmetic before touching the table.

First confirm the lock is the root cause (profiling):

• Reproduce under load with representative traffic and capture metrics: p95/p99 latency, throughput, CPU, syscalls.
• Use sampling profilers and tracing: perf + flamegraph (Linux), eBPF/hotspot, or JVM tools (Java Flight Recorder, async-profiler) to see where time is spent and whether a single mutex shows high wait-time or stack traces.
• Collect lock-specific traces: lockstat, contention tracing, or synchronized/Monitor contention logs (JVM -XX:+PrintLockContention).
• Measure lock wait times and queue lengths, and correlate with latency spikes and GC/IO.
• Run controlled microbenchmarks toggling the critical section to confirm effect size.

Strategies to reduce contention (with trade-offs):

1. Lock splitting / finer-grained locking

• Idea: Replace one global lock with multiple locks protecting disjoint subsets (e.g., per-bucket).
• Pros: Parallelism increases, simple incremental change.
• Cons: More complexity, risk of deadlocks if multiple locks acquired; requires careful partitioning to avoid hotspots.

2. Read-write locks

• Idea: Allow concurrent readers, exclusive writer.
• Pros: Great if reads >> writes.
• Cons: Writer starvation possible, higher overhead for uncontended read-path on some platforms; be cautious if reads do small updates (false sharing).

3. Lock-free / optimistic concurrency (CAS, atomic ops, concurrent data structures)

• Idea: Use atomic primitives and immutable/compare-and-swap patterns or lock-free queues/maps.
• Pros: Avoid blocking, low tail latency under high contention.
• Cons: Harder to implement and reason about, ABA issues, potential CPU spin; may increase retries under heavy write contention.

4. Per-thread caches / sharding + batching

• Idea: Keep per-thread or per-core caches/buffers and flush/merge periodically or in background.
• Pros: Removes shared hot path, excellent throughput; reduces cache-line bouncing.
• Cons: Increased memory, eventual consistency, complexity in eviction or global aggregation, possible staleness.

5. Reduce critical section cost

• Idea: Move non-essential work outside lock, precompute or use double-checked locking.
• Pros: Often simplest and high impact.
• Cons: Requires careful correctness reasoning.

6. Hybrid approaches

• Example: Use per-shard locks + per-thread batching + occasional lock-free merge.
• Pros: Balance simplicity and scalability.
• Cons: Complexity rises, need comprehensive testing.

For each candidate, re-profile after changes, measure p50/p95/p99, throughput, and CPU; add unit and stress tests to ensure correctness. Choose the smallest change that measurably reduces contention while keeping code maintainable.

Approach: compute pattern hash and initial window hash using base=256 and mod=1_000_000_007. Slide window updating hash in O(1) by removing left char contribution and adding right char, multiplying/dividing by base via precomputed power. On hash match, verify by direct substring comparison to detect collisions.

import java.util.*;

public class RabinKarp {
    private static final long BASE = 256;
    private static final long MOD = 1_000_000_007L;

    // Returns list of start indices where pattern occurs in text
    public static List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (pattern == null || text == null) return result;
        int n = text.length(), m = pattern.length();
        if (m == 0 || m > n) return result;

        long patHash = 0, winHash = 0;
        long power = 1; // BASE^(m-1) % MOD

        for (int i = 0; i < m; i++) {
            patHash = (patHash * BASE + pattern.charAt(i)) % MOD;
            winHash = (winHash * BASE + text.charAt(i)) % MOD;
            if (i > 0) power = (power * BASE) % MOD;
        }

        for (int i = 0; i <= n - m; i++) {
            if (patHash == winHash) {
                // verify to handle collision
                if (text.regionMatches(i, pattern, 0, m)) result.add(i);
            }
            if (i < n - m) {
                // remove left char, multiply remaining by BASE, add next char
                long left = (text.charAt(i) * power) % MOD;
                winHash = (winHash - left + MOD) % MOD;        // remove left contribution
                winHash = (winHash * BASE) % MOD;             // shift window
                winHash = (winHash + text.charAt(i + m)) % MOD;// add new char
            }
        }
        return result;
    }

    // Example usage
    public static void main(String[] args) {
        System.out.println(search("abracadabra", "abra")); // [0,7]
    }
}

Key points:

• O(n) average time, O(1) extra space (excluding result). Each slide updates hash in O(1) using precomputed power = BASE^(m-1) % MOD.
• Collisions: detected by explicit substring comparison (regionMatches). This makes correctness deterministic.
• Edge cases: empty pattern, pattern longer than text, negative intermediate hash fixed by adding MOD.

Direct answer
A compact but effective test suite for divide(a, b) needs three cases targeting distinct failure/behavior classes: division by zero (the documented exception path), very large integers (numeric-precision behavior when the result is a float), and negative inputs (sign-handling correctness across all three sign combinations).

Structured elaboration and worked example (executed; the original draft's if/raise/try bodies were flattened to a single indent level and the three def test_...: lines were also missing (), an unconditional SyntaxError that never ran, fixed below)

def divide(a: int, b: int) -> float:
    if b == 0:
        raise ZeroDivisionError("division by zero")
    return a / b

def test_division_by_zero():
    try:
        divide(10, 0)
        assert False, "should have raised"
    except ZeroDivisionError:
        pass

def test_very_large_integers():
    a, b = 10**18, 3
    result = divide(a, b)
    assert abs(result - a/b) < 1e-6

def test_negative_inputs():
    assert divide(-10, 2) == -5.0
    assert divide(10, -2) == -5.0
    assert divide(-10, -2) == 5.0

Running this: ALL divide TESTS PASSED.

Rationale for each test

• test_division_by_zero: pins down the DOCUMENTED contract (raise ZeroDivisionError, not return inf, nan, or crash with a different exception type); this matters because Python's native / operator on ints already raises ZeroDivisionError for integer division by zero, so this test is really confirming the function doesn't ADD a try/except that swallows or converts that exception into something else.
• test_very_large_integers: 10**18 is well beyond what a 64-bit float can represent exactly (float has about 15-17 significant decimal digits of precision, and 10**18 has 19 digits), so the test deliberately uses an approximate comparison (abs(result - a/b) < 1e-6) rather than exact equality, because exact equality would be testing a precision guarantee the function's own float return type cannot actually provide; the test's real purpose is confirming the function doesn't crash or produce a WILDLY wrong result (e.g. from an integer-overflow bug in a hypothetical alternate implementation), not asserting bit-exact precision.
• test_negative_inputs: covers all three sign combinations (negative/positive, positive/negative, negative/negative) specifically because a naive implementation using integer division (//) instead of true division (/) can behave inconsistently for negative operands in some languages (Python's // floors toward negative infinity, which is a real, distinct trap from truncating division); asserting all three combinations against /-based expected values confirms the function is using true division consistently, not accidentally mixing in floor-division semantics anywhere.

Trade-offs & pitfalls
A test suite that only checks divide(10, 0) raises SOME exception, without asserting the SPECIFIC exception type (ZeroDivisionError), would still pass against a buggy implementation that raises a generic Exception or a misleading TypeError, silently breaking any caller that specifically catches ZeroDivisionError; asserting the exact exception type, as done above, is what makes this a meaningful contract test rather than a vague 'it errors somehow' check.

Approach (state definition and transition)

• State: dp[mask][v] = number of Hamiltonian paths that visit exactly the vertices in bitmask mask and end at vertex v. We only count masks where bit 0 is set (paths start at vertex 0).
• Base: dp[1<<0][0] = 1
• Transition: for each mask, for each end v with dp[mask][v] > 0, for each neighbor u of v not in mask:
  dp[mask | (1<<u)][u] += dp[mask][v]

Python implementation (straightforward DP over masks):

def count_hamiltonian_paths(n, adj):
    # adj: list of lists, adjacency list for undirected graph
    N = 1 << n
    dp = [ [0]*n for _ in range(N) ]
    dp[1<<0][0] = 1
    for mask in range(N):
        if not (mask & 1):  # ensure paths start at 0
            continue
        for v in range(n):
            cur = dp[mask][v]
            if cur == 0:
                continue
            for u in adj[v]:
                if (mask >> u) & 1:
                    continue
                dp[mask | (1<<u)][u] += cur
    # sum paths that visited any mask of size k? For full Hamiltonian paths:
    full = (1<<n) - 1
    return sum(dp[full][v] for v in range(n))

Key points / reasoning

• We iterate masks (2^n) and for each vertex v (n) and its neighbors: O(n * 2^n * deg). Worst-case deg ~ n so O(n^2 * 2^n).
• Memory: dp table size O(n * 2^n) integers.

Complexity

• Time: O(n^2 * 2^n) worst-case.
• Space: O(n * 2^n).

Practical limits and optimizations

• For n = 20: states = 20 * 2^20 ≈ 20M integers. In Python this uses lots of memory and is slow (~hundreds of MB to GB). In optimized C++ with uint64 it's feasible.
• Pruning/optimizations:
  • Use adjacency lists and iterate neighbors (reduces factor from n to avg deg).
  • Use integer arrays or numpy for denser memory-efficient storage.
  • Store dp as array of dicts: only keep dp[mask] entries that are nonzero (sparse masks) to save memory on sparse graphs.
  • Use meet-in-the-middle (split vertices into two halves) for counting Hamiltonian paths/cycles to reduce complexity when applicable.
  • Use bit tricks and iterate subsets incrementally; precompute masks that include bit 0 to skip others.
  • If only existence is needed, use DP with boolean and early exit on first true.

Edge cases

• Disconnected graphs → result 0.
• n=1 → returns 1 (single-node path).
• Self-loops ignored; ensure adjacency doesn't include u==v.

This formulation is the standard bitmask DP for Hamiltonian-path counting; implement in C++ for production when n≈20 for performance and memory efficiency.