Amazon Software Engineer Entry-Level Interview Preparation Guide

Direct answer. Idempotency means calling an operation N times has the same effect as calling it once. A read (GET) is naturally idempotent: reading a balance ten times does not change it. A state-changing operation matters more: charging a credit card must not happen twice just because the client retried after a timeout. The technique that makes a POST idempotent under retry is a client-supplied idempotency key.

How the key design works. The client generates a unique key (typically a UUID) once, before the first attempt, and sends it in an Idempotency-Key header on every attempt of that logical operation, including retries. The server:

1. On first sight of a key, records that the key is in progress (inside the same transaction or lock that reserves it, to close the race where two near-simultaneous retries both think they are first) and then does the real work.
2. Once the real work completes, stores the result (the exact response body and status code) against that key, not just a "done" marker.
3. On any later request with the same key, does not re-run the work at all: it looks up the stored result and replays it verbatim.
4. If a request with the same key arrives while the first one is still in flight, it returns a distinct signal (commonly 409 Conflict) rather than either re-running the work or blocking indefinitely, since the client should simply wait and retry, not assume the operation failed.

Storage and TTL. Store the key with the resulting resource id, the response body, and response status, keyed uniquely (a unique index on the idempotency key in the same database as the resource, so the check-and-create is atomic). Expire keys after a bounded window, commonly 24 hours, long enough to cover realistic retry storms (a client that gives up on retrying after a few minutes, or a batch job that retries hours later after being paged) without keeping every idempotency key forever.

Read-only example. GET /orders/123 is naturally idempotent: calling it a hundred times in a row just returns the current state, with no design work required, because nothing changes as a side effect of reading.

State-changing example. POST /orders with an Idempotency-Key: retrying after a dropped connection returns the same order id and body as the original successful attempt, instead of creating a second order.

Trade-offs and pitfalls. The single most common mistake is checking whether the key has been seen and creating the resource as two separate, non-atomic steps; a race between two near-simultaneous retries can then both pass the check before either has stored the key, creating two resources anyway. The check-and-reserve step must be atomic (a unique constraint violation on insert is a reliable way to get this for free from the database).

Direct answer

Build both functions on a level-order traversal, a breadth-first search (BFS) that visits nodes queue-first, one level at a time, and write an explicit null marker for every missing child slot, not just at leaves. That pairing is what makes reconstruction unambiguous: because every real node always contributes exactly two child slots (present or null) to the next level, the deserializer can walk the same queue-driven process and know exactly which token belongs to which parent's left or right slot, without storing any indices.

Structured elaboration

Why explicit nulls, and why for every missing child

A traversal that only records the values it visits (skipping null children silently) cannot be reversed: two different shapes can share the same sequence of present values. Recording a placeholder ('#' below) for every missing child slot removes that ambiguity, because it lets the deserializer track, level by level, exactly how many real nodes exist to enqueue next.

BFS vs. depth-first search (DFS) as the traversal choice

BFS (level-order) naturally maps to a flat array where each node's two children are the next two not-yet-consumed tokens, which is convenient to stream level-by-level and easy to reason about. A preorder depth-first search (DFS, visiting root then left subtree then right subtree) with the same null-marker convention works just as well and tends to produce a shorter string for skewed or sparse trees, since it never has to emit placeholders for an entire unexplored level, only along the path actually walked. The two are interchangeable in principle; BFS is used here because it composes naturally with only trimming trailing nulls (once the queue drains, nothing after it can matter).

What must be encoded about missing children

For every dequeued real node, both potential child slots must be represented, either a value token or the null marker, in a fixed, agreed order (left before right). Skipping this for anything but a genuinely empty subtree (where the marker sequence would just never be examined) breaks the correspondence between "the next unread token" and "the next child slot to fill."

Worked example

Approach

Serialize by BFS: push nodes onto a queue, emit each node's value or '#' for None, and enqueue both children (as None placeholders too) so the null markers land at the right position. Trailing '#' tokens can be trimmed since the deserializer's queue empties before it would ever need them. Deserialize by replaying the same queue discipline: read children two at a time for the next node pulled off the queue.

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    if root is None:
        return ''
    out = []
    q = deque([root])
    while q:
        node = q.popleft()
        if node is None:
            out.append('#')
            continue
        out.append(str(node.val))
        q.append(node.left)
        q.append(node.right)
    while out and out[-1] == '#':
        out.pop()
    return ','.join(out)

def deserialize(data):
    if not data:
        return None
    parts = data.split(',')
    root = Node(int(parts[0]))
    q = deque([root])
    i = 1
    while q:
        node = q.popleft()
        if i < len(parts) and parts[i] != '#':
            node.left = Node(int(parts[i]))
            q.append(node.left)
        i += 1
        if i < len(parts) and parts[i] != '#':
            node.right = Node(int(parts[i]))
            q.append(node.right)
        i += 1
    return root

def to_tuple(node):
    if node is None:
        return None
    return (node.val, to_tuple(node.left), to_tuple(node.right))

#        1
#       / \
#      2   3
#         / \
#        4   5
#           /
#          6
n6 = Node(6)
n5 = Node(5, n6, None)
n4 = Node(4)
n3 = Node(3, n4, n5)
n2 = Node(2)
n1 = Node(1, n2, n3)

s = serialize(n1)
print("serialized:", s)
print("round-trip matches:", to_tuple(deserialize(s)) == to_tuple(n1))

This prints:

serialized: 1,2,3,#,#,4,5,#,#,6
round-trip matches: True

Key points

• Trimming only trailing '#' tokens is safe: everything after the last real node in level order can never be dequeued and read.
• Casting each token back to int(...) on the way in matters; leaving values as raw strings would silently change the tree's data type on round-trip.
• The same encoding handles duplicate values across nodes without issue, since reconstruction is positional, not value-based.

Complexity

Time: $O(n)$ for both serialize and deserialize, each node is visited once. Space: $O(n)$ for the queue and the output token list (the queue holds at most one level's worth of nodes at a time, bounded by $n$ in the worst case of a very wide tree).

Edge cases

• Empty tree: serialize(None) returns '', and deserialize('') returns None.
• Single node: no children tokens are emitted at all after trimming.
• Fully left-skewed (or right-skewed) tree: verified above with a 3-node left chain, serializing to 1,2,#,3 and round-tripping correctly, the intermediate '#' for each node's missing right child is essential here and is not trimmed because it is not trailing.

Trade-offs & pitfalls

If node values can themselves contain the delimiter character (a comma) or collide with the null marker's own text, the format breaks; production code should length-prefix each token or escape delimiters rather than assume values are delimiter-safe. A common wrong turn is marking nulls only for leaf children, or only at the very end of the traversal, either under-specifies the shape and produces silently wrong reconstructions for anything other than a perfect binary tree. For very large trees that cannot fit in memory as a single string, chunked, level-by-level I/O (write and read one level's tokens at a time) preserves the same logic while bounding memory to one level's width rather than the whole tree.

Approach summary:
Use digit-DP over the decimal digits of X to count numbers <= X that satisfy: no two consecutive equal digits and digit sum % s == 0. Then answer for [A,B] = f(B) - f(A-1). State includes position, tight flag, previous digit, sum_mod, and leading_zero flag. Memoize only when tight==0 to allow reuse.

Code (Python):

from functools import lru_cache

def count_upto(X, s):
    digits = list(map(int, str(X)))
    n = len(digits)

    @lru_cache(None)
    def dfs(pos, tight, prev, sum_mod, leading_zero):
        # pos: index in digits (0..n). If pos==n, check sum_mod==0 and not all leading zeros? treat 0 allowed if needed.
        if pos == n:
            return 1 if sum_mod % s == 0 and not (leading_zero and X!=0 and s!=1) else (1 if sum_mod % s == 0 else 0)
            # simpler: allow 0 as valid if its sum_mod matches; adjust per problem spec.
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit+1):
            ntight = tight and (d == limit)
            nleading = leading_zero and (d == 0)
            # if previous digit exists and both are non-leading zeros, forbid equal consecutive
            if not nleading and not leading_zero:
                if d == prev:
                    continue
            # update sum only when not leading zeros or if you treat leading zeros as digits 0: here include d always
            nsum = (sum_mod + d) % s
            nprev = d if not nleading else -1
            total += dfs(pos+1, ntight, nprev, nsum, nleading)
        return total

    # start: pos=0, tight=1, prev=-1, sum_mod=0, leading_zero=True
    return dfs(0, True, -1, 0, True)

def count_range(A, B, s):
    return count_upto(B, s) - (count_upto(A-1, s) if A>0 else 0)

Key design points:

• State: (pos, tight, prev_digit_or_-1, sum_mod, leading_zero).
• tight carried in recursion; only memoize when tight==False (lru_cache does full memo but correctness relies on passing tight; for memory reduction convert cache to dict keyed without tight or only store when tight==0).
• prev stores -1 for "no previous digit" or while still leading zeros.
• leading_zero avoids treating initial zeros as digits for consecutive-equal constraint.

Complexity:

• Digit length D (~log10(X)). States ≈ D * 2(tight) * (s) * (11 prev values: -1..9) * 2(leading_zero) but effective memoized states dominated when tight=0: O(D * s * 11 * 2) = O(D * s).
• Transitions: up to 10 digits each → Time O(D * s * 10) per query; memory O(D * s).

Edge cases:

• A=0 handling, whether 0 allowed (sum 0).
• s = 0 invalid (assume s>=1).
• Large s increases complexity linearly.
• If using lru_cache with tight included, memo growth is larger but safe; to optimize store memo only when tight==False.

Direct answer

Maintaining connected components under insertions alone is a solved, cheap problem: Union-Find handles it in amortized $O(\alpha(n))$ per insertion. Deletions are the genuinely hard part, because Union-Find's tree-merging structure has no efficient inverse: once two sets are merged, there is no cheap way to ask "if I remove this one edge, does the merged set need to split back into two." The practical engineering answer is almost never "support arbitrary deletions with full generality," it is to constrain the problem: batch deletions and periodically rebuild, or accept an offline model where the full sequence of operations is known in advance, or reach for a genuinely dynamic data structure (Euler tour trees, link-cut trees) only when the deletion rate and latency requirements truly demand it.

Structured elaboration

Why insertions are easy. Each new edge is one union call. Amortized cost per operation is $O(\alpha(n))$, and the structure never needs to "undo" anything to support more insertions, so an insert-heavy or insert-only workload is a non-issue for Union-Find.

Why deletions are hard. When an edge is removed, the two nodes it connected might still be connected through some OTHER path (so nothing changes), or that edge might have been the only path between two halves of what is now two separate components (so the structure must split). Union-Find's tree shape after path compression has discarded the information needed to tell these two cases apart cheaply: it only remembers "these nodes ended up under the same root at some point," not "here is the specific set of edges that currently justifies that." Determining which case applies in general requires re-deriving connectivity from the remaining edges, which is exactly the expensive operation Union-Find was built to avoid.

Three practical strategies, in order of increasing sophistication:

1. Full rebuild on every batch of deletions. Accumulate deletions for some time window or count threshold, then rebuild the entire Union-Find structure from the current live edge set. Cost: $O(E)$ per rebuild, amortized over however many deletions triggered it. This is the simplest strategy and is often sufficient when connectivity queries can tolerate being slightly stale (answered against the last completed rebuild) rather than reflecting every deletion instantly.
2. Offline divide-and-conquer with rollback, when the full sequence of insertions, deletions, and queries is known ahead of time (a genuinely offline setting, common in batch analytics jobs). Each edge's active time interval is computed in advance, and a Union-Find variant that supports undoing unions (by NOT using path compression, only union by size, and keeping an explicit undo stack) processes the timeline via a segment tree over time, applying and rolling back unions as it recurses. This achieves $O((V + E + Q) \log T)$ total for $T$ time steps and $Q$ queries, at the cost of needing the full operation sequence upfront, which rules it out for a genuinely live, open-ended stream.
3. Fully dynamic connectivity structures (Euler tour trees, or the Holm-de Lichtenberg-Thorup structure), which support both insertion and deletion in $O(\log^2 n)$ amortized time without needing the future operation sequence in advance. These exist and are the theoretically correct answer to "support both directions online," but they carry real implementation complexity (multiple levels of spanning-forest bookkeeping) well beyond what most production systems justify building or maintaining in-house.

Amortized complexity summary:

Worked example

For a near-real-time dashboard showing which servers are currently mutually reachable (an operational monitoring use case), a reasonable strategy is strategy 1, tuned: rebuild the Union-Find structure on a fixed cadence (say, once per minute, driven by the dashboard's own refresh interval, not by a fixed edge count) from the live edge set as of that moment, and serve all connectivity queries against the most recent rebuild in between. If a specific incident-response workflow needs connectivity reflecting deletions within seconds rather than up to a minute of staleness, that workflow can additionally maintain its OWN small Union-Find rebuilt just over the specific subgraph relevant to the incident, rather than paying the cost of low-latency full dynamic connectivity across the entire graph. The batching threshold (time-based vs count-based) is a product/operational decision, not a purely algorithmic one: a time-based cadence gives predictable staleness bounds, while a count-based cadence (rebuild after every $B$ deletions) gives a predictable amortized cost per deletion but an unpredictable staleness bound if deletions arrive in bursts.

Trade-offs and pitfalls

• Common mistake: reaching for a fully dynamic connectivity structure by default. These are real, correct, and asymptotically strong, but the implementation complexity is high enough that most production systems are better served by batching plus a staleness bound the business can actually tolerate; reserve the fully dynamic structure for cases where sub-second correctness after every single deletion is a hard requirement, not a nice-to-have.
• Common mistake: conflating "offline" (full operation sequence known in advance) with "batched" (deletions grouped into windows, but the future is still unknown). The divide-and-conquer-with-rollback technique needs the FULL timeline upfront; it cannot be run incrementally against a live, open-ended stream, which makes it a poor fit for a live dashboard and a good fit for a nightly batch-analytics reprocessing job over a day's worth of logged topology changes.
• A rebuild-based strategy's staleness bound is a first-class design parameter, not an afterthought: it must be stated and monitored (rebuild latency drifting up as the graph grows is a real operational risk), not left as an implicit assumption that "the rebuild is fast enough."
• Query semantics need to be explicit about what "connected" means during a batching window: does a query answered mid-batch reflect the edges as of the LAST completed rebuild, or does it block until the next rebuild finishes? Silently mixing the two within one system produces confusing, non-reproducible answers to the same query asked moments apart.

Situation: We need to store telemetry every 10 seconds per IoT device — a classic time-series workload (append-heavy, time-ordered, high-cardinality tags, frequent range/aggregation queries). A purpose-built time-series database (TSDB) is often preferable to a general relational DB for this use case.

Why TSDB is preferable:

• Optimized for high-write throughput and efficient time-ordered ingestion (bulk/append patterns common in IoT).
• Much better storage efficiency for numeric time-series (chunking + delta/TS-specific compression) which reduces cost.
• Query engines tuned for time-windowed aggregations (rollups, rate, percentile) and fast range scans over time.

Three TSDB-specific features that help:

1. Time-partitioning & compression: data stored in time-chunks (chunks/blocks) enabling fast range reads and high compression ratios for consecutive numeric samples.
2. Retention policies + downsampling/continuous queries: automatic TTLs and background rollups let you keep high-resolution recent data and aggregated older data without manual ETL.
3. Tag-based indexing and high-cardinality optimizations: flexible, indexed metadata (tags) for filtering by device/region, with query plans optimized for many series.

Limitations of TSDBs for other workloads:

• Not ideal for transactional workloads or complex multi-table joins/ACID operations (use RDBMS for OLTP).
• Less mature support for arbitrary relational queries, ad-hoc reporting, or wide non-time-based indexes.
• Some TSDBs trade consistency/feature richness for write/read performance and may lack advanced analytics (use a data warehouse or OLAP engine for complex analytics).

Direct answer

Start with the component diagram. It establishes what pieces exist and who owns each one, before anything about behavior or payloads makes sense; architects can't reason about "what happens when" until they know "what's here."

Structured elaboration

1. Component diagram (what exists). Purpose: boundaries and ownership. Show: application services, cache cluster nodes, the source-of-truth database, an invalidation service, and a message broker. Leave off: exact protocol, message schema, and timing, those belong later.

2. Sequence diagram (what happens, in order). Purpose: the actual interaction for one invalidation event. Show: a write to the database, the database acknowledging it, an event published to the invalidation service, that service publishing an evict message on the broker, the broker fanning out to cache nodes, and one failure path (broker unavailable: what serves stale data, and for how long). Leave off: byte-level payload detail and retention settings, that's the next diagram's job.

3. Data-flow diagram (what exactly, and how stale). Purpose: payloads and guarantees. Show: the invalidation message's schema (key, version, timestamp), time-to-live, message size, and the one metric architects will actually watch, invalidation latency or staleness window. Leave off: anything already covered by the component-level framing.

Why this order helps comprehension: each diagram answers the question the previous one raised. Component diagram: "what is the invalidation service." Sequence diagram: "how does it know to fire." Data-flow diagram: "how stale can a read get before this evicts it." Reversing the order, starting with the sequence diagram, forces you to define every box mid-sentence instead of pointing at one the audience has already seen.

Worked example

The component diagram you'd draw first:

flowchart LR
    App[Application] -->|write| DB[(Database)]
    App -->|read| Cache[(Cache Cluster)]
    DB -->|change event| Invalidator[Invalidation Service]
    Invalidator -->|publish evict msg| Broker[[Message Broker]]
    Broker -->|fan out| Cache
    Cache -->|miss, reload| DB

Narrated: "The application writes to the database. That write triggers a change event to the invalidation service, which publishes an evict message on the broker. The broker fans that message out to every cache node, and the next read that misses reloads from the database."

Translating the core idea for the architects: the jargon term is "cache coherence." Plain version: "keeping the cache from serving an answer that's gone stale since the database changed." Analogy: it's like a library's card catalog. When a book gets re-shelved, someone has to walk over and update the card, or the next person who checks the card gets sent to the wrong shelf. Where the analogy breaks: no single librarian updates every card at once across a building, the fan-out to many cache nodes in parallel, possibly across regions, is exactly what makes this hard in practice, and that's the detail worth naming once the audience has the basic picture.

Trade-offs & pitfalls

The common wrong turn is leading with the sequence diagram because it feels more "technical," which forces you to define the invalidation service, the broker, and the cache cluster mid-sentence instead of pointing at boxes the audience already recognizes. A second pitfall: putting the failure path (broker down) in the component diagram instead of the sequence diagram, error paths are behavior over time and belong where the audience is already reasoning about timing. A third: overloading the data-flow diagram with architectural detail that duplicates the first diagram instead of adding new information (payload size, TTL, staleness), which makes the customer conversation feel repetitive rather than cumulative.

I coach engineers to translate technical trade-offs into clear business decisions using a repeatable conversation template I call ALIGN: Audience, Level, Inputs, Goals, Options, Next steps. It keeps discussions concise and stakeholder-focused.

1. Audience & Level — Ask who’s in the room and their tolerance for detail. Tailor language (high-level impacts vs. technical details).
2. Inputs — State assumptions, constraints, data (load, budget, deadlines). “Assuming X users/month and no extra budget...”
3. Goals — Tie to business outcomes: revenue, time-to-market, reliability, user retention.
4. Options (3-max) — Present short options: “Quick win: implement A (2 weeks), Trade-off: higher tech debt. Robust: implement B (8 weeks), Trade-off: delayed launch but lower maintenance.”
5. Risks & Mitigations — For each option list top 2 risks and how you’ll reduce them (feature flags, experiments, rollback plan).
6. Timeline & Metrics — Provide clear milestones and success metrics (KPIs) to judge the decision.
7. Recommendation & Ask — Close with your recommended option and the specific decision or resource you need.

Sample phrasing:

• “Two viable paths: ship v1 in 2 weeks with known debt (technical debt $X) or invest 6 weeks to avoid rework. If we pick v1, I suggest a mitigation: feature flag + dedicated refactor in Q3.”
• End with a one-line decision summary and next step.

I practice role-plays with engineers to rehearse this script, focusing on plain-language impact statements and one-slide visuals (timeline + pros/cons) so stakeholders can decide quickly.

Direct answer

With n elements, the best case is that the array holds exactly {1, 2, ..., n}, which makes the answer n + 1; otherwise the missing value lies somewhere in [1, n]. That collapses the search space enough to turn the array into its own presence table: place each value v (when 1 <= v <= n) at index v - 1 using swaps, then scan for the first index whose value doesn't match index + 1. That index (plus one) is the smallest missing positive integer, and the whole thing runs in O(n) time using O(1) extra space because no second array or hash set is ever allocated.

Structured elaboration

Why the search space collapses to [1, n+1]. Any value outside [1, n] (negative, zero, or greater than n) cannot possibly be the smallest missing positive integer for an n-element array, so it can be ignored or safely overwritten. This is what makes the array itself a viable substitute for a hash set: only n "slots" are needed to track presence of the n candidate values that matter.

The index-mapping (cyclic placement) pass. For each index i, while nums[i] is a valid candidate (1 <= nums[i] <= n) and it is not already sitting in its home slot (nums[nums[i] - 1] != nums[i]), swap nums[i] with nums[nums[i] - 1]. This pushes the value toward the index it "claims." A value equal to i + 1 is already home and the while loop stops immediately; a value outside [1, n] also stops the loop, since it can never claim a valid slot.

Why this stays O(n) despite the nested loop. Each swap places at least one element into its permanent correct home (once an element lands at its target index, the loop condition for that index becomes false and it never moves again). Since there are only n positions to permanently fill, the total number of swaps across the entire outer loop is bounded by n, so the nested while does not make this quadratic; it is a classic amortized-O(n) argument, the same one that justifies calling cyclic-sort-style placement linear.

The read-out pass. After placement, scan left to right for the first i where nums[i] != i + 1. That mismatch means value i + 1 never found a home, i.e. it was missing from the input, so the answer is i + 1. If no mismatch is found, every slot holds its expected value and the answer is n + 1.

Worked example

Trace on [3, 4, -1, 1] (n = 4), printing every swap exactly as executed:

start: [3, 4, -1, 1]
  swap nums[0] with nums[2] -> [-1, 4, 3, 1]
  swap nums[1] with nums[3] -> [-1, 1, 3, 4]
  swap nums[1] with nums[0] -> [1, -1, 3, 4]
after placement pass: [1, -1, 3, 4]
first mismatch at index 1: nums[1]=-1 != 2
answer = 2

Full runnable code (Python 3, no external dependencies) with pinned test cases:

def first_missing_positive(nums):
    """Return the smallest missing positive integer.
    O(n) time, O(1) extra space (beyond the input list, mutated in place).
    """
    n = len(nums)

    # Step 1: place each value v (1 <= v <= n) at index v-1 by swapping,
    # so that on a "perfect" array nums[i] == i+1 for all i.
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            target = nums[i] - 1
            nums[i], nums[target] = nums[target], nums[i]

    # Step 2: the first index i where nums[i] != i+1 reveals the answer.
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1


if __name__ == "__main__":
    tests = [
        ([3, 4, -1, 1], 2),
        ([1, 2, 0], 3),
        ([7, 8, 9, 11, 12], 1),
        ([1, 2, 3], 4),
        ([], 1),
        ([1], 2),
        ([2], 1),
    ]
    for arr, expected in tests:
        arr_copy = list(arr)
        result = first_missing_positive(arr_copy)
        print(f"input={arr!r:25} -> {result} (expected {expected})")

Output (actual run):

input=[3, 4, -1, 1]             -> 2 (expected 2)
input=[1, 2, 0]                 -> 3 (expected 3)
input=[7, 8, 9, 11, 12]         -> 1 (expected 1)
input=[1, 2, 3]                 -> 4 (expected 4)
input=[]                        -> 1 (expected 1)
input=[1]                       -> 2 (expected 2)
input=[2]                       -> 1 (expected 1)

Trade-offs and pitfalls

• The most common wrong turn is sorting first: it works, but costs O(n log n) time and fails the question's stated time bound. Naming it as a correct-but-non-optimal baseline before presenting the index-mapping trick shows the interviewer you understand why the O(n) approach is needed, not just that it exists.
• A hash set of seen values gets O(n) time but O(n) extra space, missing the O(1) space constraint. It is worth naming this trade-off explicitly rather than jumping straight to the in-place trick, since it demonstrates the same reasoning under a relaxed constraint.
• An easy implementation bug: omitting the "not already home" guard (nums[nums[i]-1] != nums[i]) causes an infinite loop whenever a value already equals its own target, which happens with duplicates like [1, 1], since the code would keep swapping a value with itself forever.
• The input array is mutated in place. If the array must be preserved, say so and either copy it first (paying O(n) space to keep O(n) time) or confirm in-place mutation is acceptable for the exercise.
• Duplicates and out-of-range values (negatives, zero, values greater than n) are both handled by the same guard condition, so no separate cleanup pass is required; stating this explicitly heads off the follow-up question before it's asked.

To solve this in O(n) time we use a monotonic decreasing stack that holds indices of elements for which we haven't found the next greater element yet. As we scan left→right, whenever current value > value at stack.top(), we pop and set result[index] = current value. This handles duplicates by using strict greater (>) — equal values do not pop earlier indices, preserving the "first greater to the right". The stack maintains indices of a strictly decreasing sequence of values.

#include <vector>
#include <stack>

using namespace std;

vector<int> next_greater_elements(const vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st; // store indices; nums[st.top()] is decreasing

    for (int i = 0; i < n; ++i) {
        // while current element is greater than element at index on top of stack,
        // we've found the next greater element for that index
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    // remaining indices in stack have no greater element to their right -> stay -1
    return res;
}

Key points:

• Monotonic stack stores indices of elements in strictly decreasing order of values.
• Duplicates: equal values do not pop each other because we require '>' to find a greater element; thus the first strictly greater to the right is found correctly.
  Time complexity: O(n) — each index pushed and popped at most once.
  Space complexity: O(n) worst-case for the stack and result array.
  Edge cases: empty array (returns []), all increasing (each element resolved quickly), all equal or decreasing (many -1s). Alternative: can also solve with right-to-left scan using same monotonic principle.

Direct answer

A hash table safe for many concurrent readers and writers avoids putting one lock around the whole
structure, since that would serialize every operation across every thread. Instead, it either splits
the table into independently-lockable pieces so unrelated operations never contend, or replaces
locks with atomic compare-and-swap (CAS) operations on individual buckets, and it must handle
resizing without ever forcing every thread to stop.

Structured elaboration

Why a single global lock defeats the purpose. Wrapping every get/put in one lock makes the
table correct but removes essentially all the concurrency benefit multiple threads were supposed to
provide, threads doing completely unrelated work (different keys, different buckets) still wait on
each other.

Splitting the lock (striping/segmenting). Divide the table into many independent segments (each
with its own lock, or its own set of buckets), so two threads touching keys that land in different
segments never block each other at all. Only two threads whose keys happen to land in the SAME
segment actually contend, a big improvement, and this was the design early versions of Java's
ConcurrentHashMap used (a fixed set of segments, each independently locked).

Finer-grained: per-bucket, then lock-free. Locking at the level of a single bucket (rather than a
whole segment of many buckets) narrows contention further. Later designs go further still and avoid
locks for the common case entirely: reads can proceed without any lock at all if writes are published
using safe memory-visibility techniques (so a reader either sees the old state or the fully-completed
new state, never a half-written one), and writes to an individual bucket use CAS, "update this slot
only if it still holds the value I last read; if another thread changed it first, retry", rather than
blocking.

Resizing without a global stop. The naive approach (stop all threads, rebuild the whole table,
resume) reintroduces exactly the serialization point the rest of the design was trying to avoid.
Concurrent hash maps instead let resizing proceed incrementally and cooperatively: threads that
notice a resize in progress can HELP migrate a portion of the old table into the new one as part of
their own operation, rather than blocking until some other thread finishes the whole job, and reads
can be served from whichever of the old/new table currently holds the answer during the transition.

Bounding worst-case bucket cost. Regardless of locking strategy, a pathologically long chain in
one bucket is still slow to scan under a lock (or to CAS-retry against). Java 8+ addresses this
specifically by converting ("treeifying") a sufficiently long bucket chain into a small balanced tree,
capping that one bucket's cost at O(log n) instead of O(n), independent of the concurrency mechanism.

Worked example

Picture 16 threads each doing a mix of gets and puts against a table with 64 independently-locked
segments: with keys spread roughly uniformly, the probability any two specific threads' operations
land in the same segment at the same instant is low, most of the 16 threads proceed with essentially
no contention at all, compared to a single global lock, where all 16 threads would serialize onto one
queue regardless of which keys they're touching, throughput scales roughly with the number of
segments (up to the point where thread count exceeds segment count and collisions become likely
again), which is exactly why real designs pick a segment/stripe count based on expected concurrency
level, not an arbitrarily small fixed number.

Trade-offs and pitfalls

More segments (or per-bucket granularity) means more concurrency, but also more memory overhead
(each segment or bucket needs its own lock or CAS-coordination state) and, for segment-based designs
specifically, operations that need to touch the WHOLE table (like size()) become more expensive
to compute exactly, since no single lock guards the whole structure anymore, this is precisely why
ConcurrentHashMap.size() historically returns an approximate, "weakly consistent" count under
concurrent modification rather than a value guaranteed frozen at one instant, a deliberate,
documented trade-off, not an oversight.