Google Backend Developer (Junior Level) Interview Preparation Guide

Direct answer

Since Java 8, HashMap stores entries in an array of buckets, each normally a linked list of
Node<K,V> objects; it resizes (doubles capacity) once the entry count exceeds capacity times the
load factor (default 0.75), and, as a worst-case safety net, converts ("treeifies") any single
bucket's chain into a small balanced red-black tree once that one bucket grows past 8 entries in a
sufficiently large table.

Structured elaboration

From hashCode to bucket index. HashMap doesn't use a key's raw hashCode() directly as the
index. It first applies a supplemental "hash spreading" step (XOR-ing the hash with itself shifted
right by 16 bits) specifically to mix higher bits into the lower bits, since the actual index
computation is hash & (capacity - 1) (capacity is always a power of two, so this bitmask is
equivalent to, but much cheaper than, a modulo), which only ever looks at the LOW bits of the hash;
without the spreading step, two keys whose hashCodes only differ in high bits would collide on every
capacity that happens to be smaller than that difference.

Load factor and resize. Default loadFactor = 0.75 and default initial capacity 16 means a
resize (doubling capacity, then rehashing every entry) fires once the 13th entry is inserted (16 * 0.75
= 12, so the map resizes on exceeding that threshold). This is the same load-factor/resize mechanism any hash table needs generically; HashMap's specific default is 0.75 with
doubling.

Treeification. Once a single bucket's chain length exceeds TREEIFY_THRESHOLD (8 entries), AND
the table's total capacity is at least MIN_TREEIFY_CAPACITY (64), that one bucket converts from a
linked list to a small red-black tree, bounding THAT bucket's worst-case lookup at O(log n) instead of
O(n). Below capacity 64, HashMap prefers to resize the whole table first (since a small table with one
long bucket is more likely just needing more buckets overall, not a genuinely pathological
distribution), only treeifying once the table is already reasonably large and a bucket is STILL long
after that.

Why hashCode/equals correctness matters more here than almost anywhere else. Every one of the
mechanisms above (bucket index selection, chain traversal, treeified-tree comparison) depends on
hashCode() being consistent with equals() for every key ever inserted; violating that contract doesn't just risk a collision, it can make an entry
permanently unfindable.

Worked example

Inserting keys whose hashCode() values are 0x0000FFFF and 0xFFFF0000 into a HashMap of capacity
16 (capacity - 1 = 0x0000000F): a naive hash & (capacity-1) on the RAW hashCode gives
0x0000FFFF & 0xF = 0xF for the first and 0xFFFF0000 & 0xF = 0x0 for the second, no collision, by
coincidence. But two keys with hashCodes 0x00010000 and 0x00020000 (differing only in bits far
above the low 4 bits actually used by a capacity-16 mask) BOTH give hash & 0xF = 0x0, an unnecessary
collision a wider mask would have avoided if it could see those higher bits at all; the supplemental
hash ^ (hash >>> 16) spreading step exists specifically to fold higher-order bit differences down
into the low bits the mask actually inspects, reducing exactly this class of avoidable collision.

Trade-offs and pitfalls

A common shallow answer describes ONLY the chaining/collision behavior without mentioning the
capacity-must-be-a-power-of-two design (and the resulting bitmask-instead-of-modulo optimization),
or without mentioning that treeification requires BOTH a long chain AND a sufficiently large table,
stating it as if any 8-entry chain treeifies regardless of table size overstates the mechanism and
is a common, checkable inaccuracy.

Direct answer

Use a read/write two-pointer: walk the array once with a read index, and every time you see a value that isn't val, copy it into the next open slot tracked by a write index. The write index at the end is the new length. Whether order must be preserved decides which of two variants you use: the read/write copy above preserves the original relative order in O(n) writes; if order doesn't matter, you can instead swap a matching element with the current last element and shrink the array, which does fewer writes when val is rare.

Approach

1. Order-preserving (read/write two-pointer): write starts at 0. For each read index in order, if nums[read] != val, copy it to nums[write] and advance write. Every kept element lands in its original relative order, one slot earlier than or at its original position.
2. Order-not-preserved (swap-with-last): keep a shrinking logical length n. When nums[i] == val, overwrite it with nums[n-1] (the current last element) and shrink n by one, without advancing i (the swapped-in element still needs to be checked). When nums[i] != val, advance i. This does one write per removal instead of potentially shifting every later element, which is cheaper when matches are rare and scattered.
3. Both mutate nums in place and return the new length; elements at or past the returned length are not meaningfully defined afterward.

Complexity

Both variants: O(n) time (single pass), O(1) extra space. The order-preserving version always does one write per surviving element; the swap variant does one write per removed element, which is fewer when val is rare.

Edge cases

• val not present at all: every element is kept, new length equals original length, zero writes beyond the initial pass.
• All elements equal val: new length is 0.
• Empty input: returns 0 immediately.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    del nums[write:]
    return write


def remove_element_unordered(nums, val):
    i = 0
    n = len(nums)
    while i < n:
        if nums[i] == val:
            n -= 1
            nums[i] = nums[n]
        else:
            i += 1
    del nums[n:]
    return n


payload = [4, 2, 5, 2, 7, 2, 9]
k = remove_element(payload, 2)
print(k, payload)

payload2 = [4, 2, 5, 2, 7, 2, 9]
k2 = remove_element_unordered(payload2, 2)
print(k2, payload2)

Output:

4 [4, 5, 7, 9]
4 [4, 9, 5, 7]

Both agree on the count (4 surviving elements), but the surviving values land in different positions: [4, 5, 7, 9] keeps the original left-to-right order, while [4, 9, 5, 7] does not (9 moved from the end into an earlier slot during a swap), which is exactly the trade-off the question is asking about.

Trade-offs and pitfalls

• A common bug: using list.remove(val) or deleting elements from the middle of the array inside a loop, which is O(n) per removal (everything after the deletion point shifts down), making the whole operation O(n^2) in the worst case, and it also skips the next element if you don't adjust the loop index after a deletion. The two-pointer approaches here avoid both problems.
• The same read/write two-pointer technique applies directly to low-level, fixed-size buffers, not just Python lists. In C, given a null-terminated char *s, removing all space characters in place is the identical idea: a write index and a read index both walk the buffer, the write index only advances when the current character should be kept, and a null terminator is placed at the final write position. There's no list-resize step (del nums[write:]) because a C string doesn't carry a separate length field the way a Python list does; the null terminator is the length.
• Backend-cleanup framing from the question: "compacting payload arrays before storage" is exactly the order-preserving case if the array represents an ordered sequence (e.g. a time-ordered log) where reordering would corrupt meaning, or the order-not-preserved case if it's an unordered set of records where minimizing writes matters more than position.

Direct answer

The core move isn't picking a clever analogy, it's figuring out what decision or worry the stakeholder actually has before you start explaining, then building the explanation to answer that, and checking as you go whether it landed. Below is a caching example: what I chose to include, the analogy I used, how I confirmed it landed, and what happened.

Adapting depth without condescension

• Find out what they need to DECIDE, not just what they need to KNOW. A stakeholder rarely needs to understand caching itself, they need to decide whether to approve a change, a budget, or a timeline; build the explanation around that decision.
• Pick one analogy tied to something they already manage, inventory, a filing system, a pantry, and use it consistently rather than switching metaphors mid-conversation, which confuses even when each individual metaphor is fine on its own.
• Check understanding by asking them to restate the trade-off in their own words or apply it to a hypothetical ("if we changed X, what do you think happens to Y"), never by asking "does that make sense," which invites a polite yes regardless of whether it landed.
• Build the explanation step by step from what they already know rather than reaching for a named technique or framework to describe what you're doing; naming the technique adds nothing for the listener and mostly serves the explainer.

Worked example

Situation: our product team wanted faster page loads, and I needed the VP of Product and a finance manager, neither with an engineering background, to approve adding a caching layer.

Task: get them to understand the trade-off, faster pages, at the cost of occasionally showing slightly outdated data, well enough to make an informed approval decision, not just rubber-stamp it.

Action: I opened with the decision they needed to make, not the technology: "we can make pages load faster by keeping a copy of frequently requested information close by; the trade-off is that copy can be a few seconds out of date." I used a pantry analogy, keeping snacks nearby instead of driving to the store every time, and periodically checking the pantry is still fresh, consistently through the conversation. I sketched a two-box diagram on the whiteboard: browser, then a fast local cache, then the slower database behind it, and pointed at where the freshness delay would show up. For the finance manager, I connected the trade-off to their actual concern: fewer requests hitting the expensive database tier means lower infrastructure spend, which is why this was worth their budget attention. I checked understanding by asking each of them to describe, in their own words, what a customer might see if we set the freshness window too long; both correctly identified stale data as the risk, which told me the analogy had landed.

Result: they approved a staged rollout, and the finance manager specifically asked for the freshness window to start conservative and widen over time, which showed they'd internalized the actual trade-off rather than just agreeing. I learned to lead with the decision, not the mechanism, and that asking someone to apply the idea to a hypothetical is a much better comprehension check than asking if it makes sense.

Trade-offs and pitfalls

The pantry analogy is easy to over-extend; someone will eventually ask "what if two people put different snacks in at the same time," and a caching layer's real answer (a specific write and invalidation rule) doesn't have a clean pantry equivalent, so know where you'll stop extending it before someone finds the gap for you. The other common failure mode is treating a nod as confirmation, a stakeholder will often not admit they're lost mid-meeting, which is why an explicit restate-it-back check matters more than reading the room.

Approach (brief)
Use a lock-free singly-linked list with two-phase removal: logical delete by marking a next pointer, then physical unlink with CAS. Use tagged (versioned) pointers to avoid ABA and hazard pointers (or epoch-based reclamation) for safe memory reclamation.

Key ideas

• Node { value, atomic<MarkedPtr> next } where MarkedPtr = (ptr | tag | mark-bit)
• Insert: find window (pred, curr) with hazard pointers, CAS pred->next to new node
• Delete: mark curr->next (logical delete) via CAS; then CAS pred->next to skip curr (physical)
• ABA: include a 16-bit tag/version in atomic pointer; increment on each CAS
• Memory reclamation: use hazard pointers: threads announce nodes they access; only reclaim when no hazard pointer references node. Alternatively use epoch GC.

Pseudocode (simplified)

// C++-style pseudocode
struct MarkedPtr { Node* ptr; uint64_t tag; bool mark; };
atomic<MarkedPtr> head;

bool insert(value) {
  while (true) {
    pred = head; hazard.protect(pred);
    curr = pred->next.load();
    // find position
    while (curr && curr->value < value) {
      hazard.protect(curr);
      pred = curr; curr = curr->next.load();
    }
    if (curr && curr->value == value) return false; // optional duplicate rule
    newNode->next.store({curr,0,false});
    MarkedPtr expected = {curr, expectedTag(pred), false};
    if (pred->next.compare_exchange_strong(expected, {newNode, expected.tag+1, false})) {
      return true;
    }
    // CAS failed -> retry (tags avoid ABA)
  }
}

bool remove(value) {
  while (true) {
    pred = head; hazard.protect(pred);
    curr = pred->next.load(); hazard.protect(curr);
    while (curr && curr->value < value) {
      pred = curr; curr = curr->next.load(); hazard.protect(curr);
    }
    if (!curr || curr->value != value) return false;
    MarkedPtr succ = curr->next.load();
    // logical delete: set mark bit
    if (!curr->next.compare_exchange_strong(succ, {succ.ptr, succ.tag+1, true})) continue;
    // physical removal
    MarkedPtr expected = {curr, expectedTag(pred), false};
    if (!pred->next.compare_exchange_strong(expected, {succ.ptr, expected.tag+1, false})) {
      // someone else will help unlink; continue
    }
    // safe reclaim: retire curr via hazard pointers; reclaim when no hazard references
    retire_node(curr);
    return true;
  }
}

Complexity & notes

• Lock-free progress: insert/delete are O(n) expected time (traversal)
• Tags avoid ABA by changing tag on each CAS; hazard pointers prevent reclaiming nodes still in use.
• Alternatives: epoch-based reclamation (simpler but higher memory) or RCU-style for read-heavy workloads.
• Test for concurrency: stress tests, linearizability checks, and verify reclamation correctness.

Direct answer

A high-level architecture shows the system's scope: the major building blocks (client, API layer, service tier, datastore, cache, external dependencies), how they relate, and the non-functional constraints (scale, availability) that shaped them. A component-level design zooms into one of those blocks and specifies its interfaces, request/response schemas, data flows, and sequencing. You show the high-level view to stakeholders who need to understand what the system is and what it costs or risks; you show component-level design to the people who have to build, test, or integrate against one specific piece.

Structured elaboration

The reason both layers matter: the high-level view sets the strategy and the constraints everyone else has to work inside; the component-level view is what actually gets implemented, tested, and integrated. A good design doc keeps an explicit mapping from each high-level block down to its component-level detail, so a reviewer can move between the two without re-deriving context.

Worked example

Say you're designing a subscription billing feature. At the high level you'd draw: client apps, an API gateway, a billing service, a payments component, a database, and a message queue for async notifications, with an arrow showing the billing service calls out to a third-party payment processor. The one decision that belongs only at this level: whether billing lives inside the existing monolith or is split into its own service, because that choice affects deployment, on-call ownership, and the blast radius of an incident, not just this one feature.

At the component level, you'd zoom into just the billing service and produce: a sequence diagram for "create subscription" (client → billing service → payments component → processor → database write → event published), the exact request/response schema for the POST /subscriptions endpoint, and an entity-relationship diagram for the subscription and invoice tables. None of that detail belongs on the high-level diagram; it would bury the one decision (monolith vs separate service) that the high-level view exists to surface.

Trade-offs & pitfalls

• Showing component-level detail (full schemas, every retry path) to an executive or product stakeholder buries the one decision they actually need to weigh in on.
• Skipping the high-level view and jumping straight to component design risks locking in a boundary (a shared database, a synchronous call where an event would do) that is expensive to undo later, because it was never surfaced as a decision.
• A common weak answer just says "high-level is the big picture, low-level is the details" without naming a decision that is exclusive to one level; naming that decision is the signal an interviewer is listening for.
• Keep a living link between the two artifacts (a component-level design should reference which high-level block it belongs to) so the documentation doesn't drift apart as the system evolves.

Direct answer

For 1,000,000 nodes, a dense adjacency matrix needs $N^2 = 10^{12}$ entries. At one byte per entry that is about 1 TB (0.91 TiB); at one bit per entry it drops to about 125 GB (116.4 GiB). Neither is a normal working set for a service that mostly deals with sparse connections, so the practical answer is not "which unit fits" but "do not use a dense matrix here at all": switch to a representation whose size scales with the number of actual edges, not with $V^2$.

Structured elaboration

Byte-per-entry calculation. $N = 1{,}000{,}000 \Rightarrow N^2 = 10^{12}$ entries. At 1 byte each: $10^{12}$ bytes $= 1{,}000$ GB (decimal) $\approx 1$ TB, or $\approx 931.3$ GiB $\approx 0.91$ TiB in binary units.

Bit-per-entry calculation. The same $10^{12}$ entries at 1 bit each: $10^{12} / 8 = 1.25 \times 10^{11}$ bytes $= 125$ GB (decimal) $\approx 116.4$ GiB (binary).

(A quick note on units, since both appear above: GB here means gigabyte, powers of 1000, the way storage vendors and back-of-envelope math usually count; GiB means gibibyte, powers of 1024, the way memory is actually addressed. The two disagree by about 7% at this scale, which is why both figures are given.)

Feasibility from an SRE (site reliability engineering) standpoint. A single-machine allocation of ~1 TB (byte-packed) is well outside a normal service's memory budget and would need to live on specialized big-memory hardware even before accounting for the rest of the process's working set. The bit-packed version, ~125 GB, is smaller but still large, and worse, a raw bitset is expensive to update: flipping a single bit is cheap, but most service-topology or dependency graphs are sparse (most pairs of nodes are NOT connected), so nearly all of that 125 GB would encode "no relationship," which is pure waste relative to what the data actually contains.

Worked example

Suppose the real graph has on the order of 5,000,000 actual edges (a plausible, decently connected service or social graph at this scale, average degree 10). An adjacency-list-based structure costs $O(N + E) \approx 6{,}000{,}000$ entries, several orders of magnitude smaller than either matrix figure, and the memory cost now tracks the graph's real connectivity instead of the square of its node count. Concretely:

• Sparse adjacency structure (list or hash-map of sets): roughly tens of megabytes at typical pointer/id sizes, versus the matrix's 125+ GB.
• Compressed sparse row (CSR), two flat arrays: an offsets array of size N+1 and a neighbor array of size E: similar $O(N+E)$ space to the list, but contiguous and cache-friendly, a good fit for a monitoring tool that repeatedly re-scans the same graph.
• Roaring bitmaps (a compressed bitmap format that stays small for sparse or clustered bit sets, and only degrades toward the size of a plain bitset when the set is genuinely dense): a good fit if you want per-node neighbor sets with fast set operations (union, intersection) for tasks like "which nodes are reachable from either of these two services," without paying the full bitset cost when most rows are mostly zero.

Trade-offs and pitfalls

• Graph databases and sharded stores (for example Neo4j, JanusGraph, or a plain key-value store keyed by node id) trade single-machine memory pressure for network/query latency; reasonable once the graph or its query load outgrows one process.
• Retention policies matter as much as the data structure. For a monitoring or observability graph, keeping only a recent window (TTL, time-to-live, meaning entries expire after a fixed duration) and sampling low-signal edges bounds memory growth independent of representation.
• Probabilistic structures (Bloom filters) trade a small false-positive rate for large memory savings on membership questions ("is there any edge between roughly this pair"); not appropriate when you need an exact edge list, only when an occasional false positive is tolerable and always followed by a real check.
• Common mistake: computing memory for the wrong data type (using 4- or 8-byte integers for what should be a single bit or boolean, inflating the estimate 8 to 64x) or, in the other direction, forgetting that a bitset still costs $O(N^2)$ bits even though each cell shrank, which is the trap this question is designed to expose: shrinking the per-entry cost does not fix an architecture whose entry COUNT is quadratic in the first place.

Direct answer. Assemble the feed with a fan-out query keyed on the follower list plus a keyset cursor over (post timestamp, post id), fetching posts in batches per followed author rather than joining the full followers table against the full posts table in one shot, which is what actually causes the N+1-style blowup at this scale.

Avoiding N+1 and full joins. The naive approach (for each follower, query their followed authors, then for each author query their posts) is literally N+1. The fix is not a single giant JOIN either, which forces the database to materialize and sort a huge intermediate result before it can apply the LIMIT; instead, pre-compute or cache the list of authors a user follows once per request, then run ONE keyset-paginated query against a posts table that is indexed by (author_id, created_at, id), using an IN clause over the (bounded) follower list, so the database can use the index to fetch only the rows it actually needs for this page, in the same round trip.

Keeping the cursor compact and opaque. Encode the cursor as the last returned (post timestamp, post id) pair only, not the full state of which authors have been exhausted; base64-encode it (optionally with an HMAC signature: HMAC, Hash-based Message Authentication Code, is a keyed checksum, meaning the server computes it over the cursor's bytes using a secret only it knows, and if a client changes even one byte, recomputing the checksum on the next request won't match, so tampering is caught rather than silently trusted; this is what keeps a client from tampering with it to page into another user's private feed) so it travels as one short opaque string in the response, not a structured object the client could inspect or manipulate.

Worked example. Suppose the last row on page 1 is (created_at = 2026-07-20T14:02:00Z, id = 9821). The server builds the payload {"id":9821,"ts":"2026-07-20T14:02:00Z","v":1}, base64-encodes it to eyJpZCI6OTgyMSwidHMiOiIyMDI2LTA3LTIwVDE0OjAyOjAwWiIsInYiOjF9 (verified: this is exactly what base64.b64encode() produces for that exact payload string), then computes an HMAC-SHA256 signature over that base64 string using the server's signing key. Illustrated here with a demo key, b"demo-server-signing-key" (in production this is a real secret held only by the server and never shown to the client), the signature truncated to 12 hex characters is b84145a14d15 (verified: hmac.new(key, b64_string.encode(), hashlib.sha256).hexdigest()[:12]). The server ships the two joined by a dot as the opaque cursor: eyJpZCI6OTgyMSwidHMiOiIyMDI2LTA3LTIwVDE0OjAyOjAwWiIsInYiOjF9.b84145a14d15. Page 2's request sends this string back verbatim; the server decodes the payload, recomputes the HMAC over it with the same key, confirms it matches, and only then runs WHERE (created_at, id) > ('2026-07-20T14:02:00Z', 9821) to fetch the next batch. If a client edited the payload's id to 9822 without a valid signature for that new value, recomputing the HMAC over the tampered payload with the same key produces a different signature (edbc982b49ef, not the original b84145a14d15), so the mismatch is caught immediately and the request is rejected rather than silently paging the attacker past their real position.

Correct ordering as new posts arrive. Because the cursor anchors on (timestamp, id) rather than a row count, a new post from a followed author inserted after the client's last-seen cursor position is picked up naturally on the next page request; it does not shift the position of posts the client has already seen, the same correctness property as the general cursor design, just applied across a fan-out of many authors instead of one table.

Signing and versioning the cursor. Sign the cursor payload (HMAC with a server-held key) so a client cannot forge a cursor claiming a later position than they are actually entitled to (which would let them skip content-moderation-relevant posts, or, worse, read into a private list they should not see). Version the cursor's binary format explicitly (a version byte at the front of the payload) so a schema change to what the cursor encodes does not silently misparse cursors a client is still holding from before the change; an unrecognized version returns 400 rather than attempting to decode a token whose fields no longer mean what the server expects.

Trade-offs and pitfalls. The subtlest mistake is signing the cursor but not versioning it: a schema migration that changes what fields the cursor carries will still verify (the HMAC only proves the bytes were not tampered with, not that the server can still interpret them), and a naive decoder can misread a byte offset as a valid but wrong value instead of failing cleanly.

Direct answer

A good framework treats this as testable, not just introspective: define what you'd actually try, a bounded stretch of management-shaped work and a bounded stretch of deeper technical work, define in advance the signal that would tell you it's the wrong fit, and decide before you commit what you'll do if your organization doesn't formally support the track you land on.

Structured elaboration

1. Name the criteria you'd weigh: what kind of work energizes you, what you're better positioned to multiply, what the organization actually needs right now, and what you'd give up either way.
2. Design a real test, not just reflection. Take a bounded stretch of the other track's actual work, run point on a hiring loop or a stretch of people-process, versus leading a genuinely hard cross-team technical design, and see what you learn rather than what you assume.
3. Define the wrong-signal in advance, before running the test: for example, dreading the coaching conversations more than delegation feels rewarding, or missing the hands-on problem more than the leadership win feels satisfying.
4. Handle the org-support gap. If the organization's ladder only formally recognizes a management track, and your test points toward the technical track, name the concrete move: make the case for a parallel technical track with a clear rationale (retention, scarce expertise), rather than assuming you must default into management, or start operating at that scope informally and use it as evidence when you make the case.

Worked example

"When I was weighing this, I ran a deliberate month-long test on each side rather than guessing: took point on a hiring loop and a couple of coaching-style conversations on one side, and led a genuinely hard cross-team technical design on the other. What surprised me was that the coaching stretch felt draining by the end of it, while the technical design was the first time in a while I'd lost track of the clock. That was a clearer signal than reflecting in the abstract would have given me. The complication was that my organization's ladder only formally recognized a management track past a certain level, so landing on the technical side meant I also had to make an explicit case, with real examples of the depth I was bringing, for a parallel track rather than assuming the door was already open."

Trade-offs & pitfalls

• Choosing based on pure introspection without ever testing either track in real, bounded work is the weakest version of this answer.
• Not defining the wrong-signal until after you've already committed means you'll rationalize discomfort instead of noticing it.
• Assuming the organization's existing ladder is the only option and silently defaulting to whichever track it recognizes, instead of actively advocating for a parallel technical track when your test points that way.
• Treating the decision as permanent when many people revisit it. A good framework leaves room to reassess without treating that as failure.

Approach

Wrap the target function in a decorator that retries it on exception up to a configurable number of attempts, sleeping between attempts for a delay that grows by a backoff factor each time, and re-raise the final exception if every attempt fails so the caller still sees the failure. To avoid many independent callers all retrying at the exact same moments (a thundering herd against whatever downstream service is failing), add random jitter to each computed delay so retries from different callers spread out in time instead of synchronizing.

Code (Python 3.12)

import functools
import random
import time


def retry(max_attempts=3, initial_delay=1.0, backoff_factor=2.0,
          jitter=0.5, exceptions=(Exception,)):
    """Retry the wrapped function on exception.

    max_attempts: total attempts, including the first (not just retries).
    initial_delay: seconds to wait before the first retry.
    backoff_factor: multiplier applied to the delay after every failed attempt.
    jitter: fraction of the current delay added as random extra wait,
            e.g. jitter=0.5 adds up to 50% extra, chosen independently
            per caller, so simultaneous retries don't line back up.
    exceptions: exception type(s) that should trigger a retry.
    """
    def decorator(func):
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            delay = initial_delay
            for attempt in range(1, max_attempts + 1):
                try:
                    return func(*args, **kwargs)
                except exceptions:
                    if attempt == max_attempts:
                        raise
                    sleep_for = delay + random.uniform(0, jitter * delay)
                    time.sleep(sleep_for)
                    delay *= backoff_factor
        return wrapper
    return decorator


@retry(max_attempts=3, initial_delay=0.0, jitter=0.0)
def flaky(state={"n": 0}):
    state["n"] += 1
    if state["n"] < 3:
        raise ValueError("boom")
    return "ok"

print(flaky())
# ok
print(flaky.__name__)
# flaky

Key points

• functools.wraps(func) copies func.__name__, __doc__, and other metadata onto wrapper; without it, every decorated function would report its name as "wrapper" and lose its docstring, which breaks introspection, debuggers, and anything that logs a function's name by attribute rather than by the literal source line.
• The delay for attempt $i$ (0-indexed after the first failure) follows $\text{delay}_i = \text{initial\_delay} \times \text{backoff\_factor}^{i}$, before jitter is added; jitter is added on top as an independent random amount, not multiplied in, so it doesn't compound the way the backoff itself does.
• exceptions is a parameter, not hardcoded to bare Exception, so a caller can scope retries to just the failure modes that are actually transient (e.g., a specific network-timeout exception) instead of retrying on programming errors that will never succeed on a second attempt.

Complexity

Not meaningfully characterized by big-O (this decorator's cost is dominated by the wrapped function's own cost plus wait time between attempts, not by any data-structure traversal); the values worth reasoning about instead are: worst-case total wall-clock delay across all retries is roughly $\text{initial\_delay} \times \frac{\text{backoff\_factor}^{\text{max\_attempts}-1} - 1}{\text{backoff\_factor} - 1}$ (a geometric series), and worst-case call count is exactly max_attempts.

Edge cases

• max_attempts=1 means no retries at all; the exception propagates on the first failure, which is a sensible degenerate case rather than a special-cased error.
• Retrying a function with side effects that are not idempotent (e.g., "charge a credit card") can cause the side effect to happen more than once if the failure occurred after the effect but before the caller's exception path was reached; the decorator itself does not know or enforce idempotency, so it should only be applied to operations that are safe to repeat, or paired with an idempotency key at the call site.
• Retrying on too broad an exception type (bare Exception) will also retry on bugs (a TypeError from a programming mistake) that have no chance of succeeding on a second attempt; scope exceptions narrowly to the failure modes you actually expect to be transient.

Avoiding a thundering herd across many callers

Backoff alone does not prevent synchronization: if every caller starts retrying at $t=0$ with the identical initial_delay and backoff_factor, every caller's second attempt lands at the same instant, and every caller's third attempt lands at the same instant after that, which is exactly a thundering herd against the recovering downstream service. The fix implemented above is jitter: adding an independently-random extra delay (random.uniform(0, jitter * delay)) to each caller's wait means different callers' retries land at different times even though they all started at the same nominal delay, spreading load out instead of re-synchronizing it on every attempt. A stricter variant ("full jitter," rather than the "additive jitter" shown here) replaces the base delay entirely with a uniformly random value between zero and the computed backoff delay, which spreads retries out even further at the cost of some retries firing sooner than the nominal backoff would suggest; either is a legitimate choice, and the right one depends on how tightly you need to bound worst-case latency versus how aggressively you need to de-synchronize callers.

Approach (brief)
Use divide-and-conquer: modified merge sort counts inversions while merging. When a left element > right element during merge, it forms inversions with remaining elements in left subarray.

Code (Java)

public class InversionCounter {
  public static long countInversions(int[] arr) {
    if (arr == null || arr.length < 2) return 0L;
    int[] aux = arr.clone();
    return sortCount(arr, aux, 0, arr.length - 1);
  }

  private static long sortCount(int[] a, int[] aux, int lo, int hi) {
    if (lo >= hi) return 0L;
    int mid = lo + (hi - lo) / 2;
    long count = 0;
    count += sortCount(a, aux, lo, mid);
    count += sortCount(a, aux, mid + 1, hi);
    // merge step
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid || j <= hi) {
      if (i > mid) aux[k++] = a[j++];
      else if (j > hi) aux[k++] = a[i++];
      else if (a[i] <= a[j]) aux[k++] = a[i++];
      else { // a[i] > a[j] -> inversions
        aux[k++] = a[j++];
        count += (mid - i + 1);
      }
    }
    System.arraycopy(aux, lo, a, lo, hi - lo + 1);
    return count;
  }
}

Why O(n log n)
Each level of recursion does a linear-time merge across all subarrays (O(n)). There are O(log n) levels, so total time is O(n log n). Space is O(n) for auxiliary array.

Edge cases & notes

• Handles duplicates using <= to avoid counting equal pairs.
• Use long to avoid overflow for large arrays (n up to ~2e9 pairs).