Microsoft AI Engineer (Entry Level) - Comprehensive Interview Preparation Guide

Direct answer
try marks a block whose exceptions you want to intercept; except runs only if a matching exception is raised inside the try; finally always runs, whether or not an exception occurred and whether or not it was caught, and it runs even if the exception propagates past this block entirely.

Structured elaboration

• No exception: the try block runs to completion, every except clause is skipped, then finally runs. Nothing unusual happens.
• Exception raised and caught: execution jumps out of the try block the instant the exception is raised (any code after the raising line in try does NOT run), the first matching except clause runs, then finally runs.
• Exception raised and NOT caught (no except clause matches its type): the matching-except search fails, finally still runs (this is the part people get wrong: finally is not conditional on being caught), and only after finally completes does the exception continue propagating up to the caller.
• The consequence that matters in practice: finally is the correct place for resource cleanup that must happen unconditionally, closing a file handle, releasing a lock, rolling back a partially-started operation, precisely because it is the one block guaranteed to run on every exit path from the try.

Worked example

def no_exception():
    order = []
    try:
        order.append('try')
    except ValueError:
        order.append('except')
    finally:
        order.append('finally')
    return order

def caught_exception():
    order = []
    try:
        order.append('try')
        raise ValueError('boom')
    except ValueError:
        order.append('except')
    finally:
        order.append('finally')
    return order

Running both (verified): no_exception() returns ['try', 'finally'] (the except clause never runs), caught_exception() returns ['try', 'except', 'finally']. A third case with a TypeError raised where only ValueError is caught confirms finally still runs before the TypeError propagates out to the caller, exactly as described above.

For the file-I/O case, opening a file and guaranteeing it closes even on a mid-read failure:

def read_lines(path):
    f = open(path, 'r')
    try:
        return f.readlines()
    finally:
        f.close()   # runs whether readlines() succeeds, raises, or the caller's except re-raises

This is exactly what a with open(path) as f: block (or Java's try-with-resources) does under the hood, they are sugar over a try/finally that closes the resource. In this pattern, whether to re-raise the error after logging it or return a sentinel value to the caller depends on whether the caller can meaningfully continue: propagate (let the exception continue, possibly after logging) when the caller cannot proceed without the data; return a sentinel only when the caller has a genuine, documented fallback.

Trade-offs & pitfalls
The most common mechanical mistake is assuming finally only runs when an exception was caught, when in fact it runs on every exit from try (normal completion, caught exception, uncaught exception, even a return inside the try block). The second most common mistake is putting cleanup code after the try/except instead of in finally, which silently skips cleanup on any path that doesn't hit that exact line, exactly the bug that finally exists to prevent.

Direct answer

Scan the expression once left to right, accumulating the current number and, on hitting an operator (or the string's end), resolving the previous operator against a value stack rather than a running total directly. Addition and subtraction push a signed value onto the stack to be settled later; multiplication and division pop the stack's top, combine it with the current number immediately, and push the result back, because those two operators must bind tighter than whatever addition or subtraction comes before or after them. The stack is what lets the scan defer every addition and subtraction until the very end, once every higher-precedence operation touching a given operand has already been folded in, summing the stack at that point gives the correct, precedence-respecting result.

Structured elaboration

Why a single accumulator is not enough

Evaluating left to right with one running total works for pure addition and subtraction, but multiplication and division must apply to their immediate neighbors before anything else touches those values. A single accumulator has no way to "undo" a value it already folded into the total in order to multiply it by something appearing later.

What the stack defers, specifically

Each time a complete number is read, look at the operator that preceded it:

• +: push the number as-is; it will be added in at the end.
• -: push the number negated; subtraction is addition of a negative.
• * or /: pop the stack's current top, combine with the new number right now, and push the combined result back, this is what "deferring lower-precedence operations" really means in reverse: it is addition and subtraction that get deferred, while multiplication and division are resolved immediately because their operands are already fully known.
  At the very end, summing the whole stack applies every deferred addition and subtraction in one shot, correctly, because every *// touching any of those values has already been folded in before it ever reached the stack.

Handling division sign and formatting

Division must truncate toward zero (not Python's default floor division, which rounds toward negative infinity for negative operands), so int(a / b) rather than a // b is used to match the conventional integer-arithmetic contract.

Worked example

def calculate(s: str) -> int:
    s = s.strip()
    stack = []
    num = 0
    op = '+'
    n = len(s)
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != ' ') or i == n - 1:
            if op == '+':
                stack.append(num)
            elif op == '-':
                stack.append(-num)
            elif op == '*':
                stack.append(stack.pop() * num)
            elif op == '/':
                prev = stack.pop()
                stack.append(int(prev / num))
            op = ch
            num = 0
    return sum(stack)

print(calculate("3+2*2"))
print(calculate(" 3/2 "))
print(calculate(" 3+5 / 2 "))
print(calculate("14-3/2"))
print(calculate("1*2-3/4+5*6-7*8+9/10"))

This prints:

7
1
5
13
-24

Tracing "3+2*2": read 3, hit +, push 3 (stack [3]), op becomes +. Read 2, hit *, push 2 (stack [3, 2]), op becomes *. Read the final 2 (end of string triggers resolution with op = '*'): pop 2, multiply by the new 2, push 4 (stack [3, 4]). Sum is 7, matching the printed output. "14-3/2" similarly resolves 3/2 to 1 via truncating division before the pending subtraction is ever applied, giving 14 - 1 = 13.

Key points

• The stack holds fully-resolved, precedence-correct terms; the final sum() is the only place addition and subtraction actually happen across terms.
• * and / never get their own stack entries, they immediately combine with whatever the stack's top already holds.
• Multi-digit numbers accumulate via num = num * 10 + int(ch) before any operator triggers resolution.

Complexity

Time: $O(n)$, a single pass over the string. Space: $O(n)$ in the worst case for the stack (an expression that is entirely additions and subtractions of single terms pushes one entry per term), though it can be reduced to $O(1)$ extra space by tracking only the running total and the most recent term instead of a full stack, at the cost of a less direct mapping to "what the stack is doing" pedagogically.

Edge cases

• Leading, trailing, or embedded spaces: skipped by the ch != ' ' check, which does not trigger a resolution and does not get added into the accumulating number.
• Multi-digit numbers: accumulated digit by digit before any operator resolves them.
• Expression ending exactly on a number (no trailing operator): the i == n - 1 condition forces one final resolution using whatever operator preceded that last number.
• Division truncating toward zero for negative results: using int(prev / num) rather than prev // num avoids Python's floor-toward-negative-infinity behavior on mixed-sign division.

Trade-offs & pitfalls

The most common bug is using // for division and getting a different (floored, not truncated) result on negative operands; int(a / b) sidesteps this by truncating through the int() conversion itself. A frequent design question is whether to extend this to full recursive-descent parsing to support parentheses and unary operators (Basic Calculator III-style): the single-pass stack approach generalizes naturally to nested parentheses by recursing into a sub-expression whenever ( is seen and returning the sub-result to the outer scan, whereas true operator-precedence parsing with a formal grammar is a more general (and more code-heavy) solution better suited to expressions with many operator types or user-defined precedence rules.

Direct answer
Cutting a document in half without losing the point means removing words and sentences that restate, hedge, or elaborate past the level of detail the reader needs, not removing content the reader actually needs. Start by identifying the load-bearing sentences, then cut everything else, then tighten what's left.

Structured elaboration

1. Identify the load-bearing sentences first. For each paragraph, ask: if this sentence disappeared, would the reader miss information they need to act? Mark the ones that survive that test.
2. Cut whole sentences before trimming words. Removing a redundant sentence saves more length, with less risk of losing meaning, than trying to shave words from every sentence.
3. Common categories to cut entirely: sentences that restate a point already made in different words; hedging phrases ("it is worth noting that," "we believe that," "in our opinion") that add no information; background the reader already has; and process narration ("first we looked at X, then we considered Y") when only the conclusion of that process matters.
4. Convert paragraphs to lists where the content is genuinely parallel (a set of options, a set of risks); a list of five short items reads faster than one paragraph saying the same five things in prose.
5. Tighten individual sentences last: replace multi-word phrases with single words ("in order to" to "to", "due to the fact that" to "because"), and cut adjectives and adverbs that don't change the meaning.

Worked example
Before (47 words): "It is worth noting that, due to the fact that the vendor contract renewal date is rapidly approaching, we believe that it would probably be a good idea for us to schedule a review meeting sometime in the next two weeks in order to discuss next steps."

After (17 words): "The vendor contract renews soon. Let's schedule a review meeting within two weeks to decide next steps."

That's a 64% cut (47 words to 17) on this one sentence, achieved by removing three hedges ("it is worth noting," "we believe," "probably") and one restated phrase ("in order to" to "to"), not by removing any fact.

Trade-offs and pitfalls

• The risk in aggressive cutting is losing a caveat or edge case that genuinely mattered; after cutting, reread once specifically asking "did I just delete a risk or exception, not just a restatement?"
• Cutting to a target percentage (half the length) as a goal in itself can tempt you to remove real content once the easy hedges are gone; if you run out of filler before you hit the target, the document may have been genuinely that dense, and the honest move is to say so rather than cut substance to hit a number.
• Lists are faster to scan but can flatten genuine nuance between items; use them for parallel content, not for things that need qualification relative to each other.

Direct answer

I ran a six-week test of a new onboarding email sequence, hypothesizing that adding a short personalized video would raise activation, and by week four the data was inconclusive rather than clearly negative, which is the harder call: deciding whether to keep running for a real signal or stop because the result had stopped being informative. I stopped at week five, explained the decision and the reasoning to the two stakeholders who had sunk real time into producing the videos, and made sure what we'd learned about the underlying segment behavior carried into the next attempt instead of being lost with the failed one.

The hypothesis, design, and timeline

The hypothesis was that a short, personalized video early in onboarding would raise activation among users who had signed up but not completed setup, based on a pattern we'd seen in a smaller pilot. I designed a six-week A/B test with a defined minimum sample size calculated up front, specifically so I wouldn't be tempted to call it early or late based on how the numbers happened to be trending on a given day.

How I made the stop-or-continue call

By week four, the treatment group's activation rate wasn't meaningfully different from control, but the sample was also smaller than planned because a tracking issue had silently dropped a portion of the treatment group's data for the first ten days, which meant the result was underpowered (we didn't have enough clean data left to trust a negative result either way, not that the result was actually bad), not simply negative. I spent part of week four determining whether that was an environmental problem, the tracking gap, rather than a genuine sign the video didn't work. Extending the test to compensate was one option; I decided against it, because even a clean extension wouldn't have told us anything about the actual hypothesis with confidence by a reasonable date, and continuing mainly to avoid calling it a failure would have been the wrong reason to keep going.

What I did with what I'd learned

I stopped at week five and told the two people who had built the videos directly: the specific reason, an underpowered and contaminated dataset rather than a clear negative result, and that the honest conclusion was "inconclusive," not "the idea doesn't work." Rather than letting the attempt just end there, I salvaged what was usable: the clean portion of the data still showed a real behavioral pattern in how users engaged with onboarding content at all, which fed directly into redesigning the next attempt's tracking and targeting before we tried a similar idea again.

Trade-offs and pitfalls

The trade-off in a stop-or-continue call like this is sunk cost against real signal: the video work represented real time from real people, and there's pressure to keep going just to justify that investment rather than to actually learn something. The pitfall I watch for is treating "inconclusive" and "failed" as the same thing when explaining the decision, since conflating them either overstates how wrong the idea was or understates how little the test actually proved either way.

Direct answer: LoRA (Low-Rank Adaptation) freezes the pretrained weight matrix and instead learns a small, low-rank update on top of it, so fine-tuning trains far fewer parameters than updating the full matrix while still adapting the model's behavior.

Structured elaboration: For a weight matrix $W$ of shape $(d_{out}, d_{in})$, LoRA replaces the usual full-matrix update with two much smaller trainable matrices $A$ (shape $r \times d_{in}$) and $B$ (shape $d_{out} \times r$), where the effective weight used at inference is:

$W' = W + \frac{\alpha}{r} \, B A$

Here $r \ll \min(d_{out}, d_{in})$ is the rank, a hyperparameter controlling how expressive the update can be (typical values are 4 to 64 for large language models). $\alpha$ is a scaling factor that controls the effective magnitude of the update relative to the rank; dividing by $r$ keeps the update's scale roughly comparable across different rank choices, so you can change $r$ without having to re-tune $\alpha$ from scratch. $B$ is typically initialized to all zeros and $A$ to small random values, so the adapted model starts out numerically identical to the original pretrained model and then diverges as training updates $A$ and $B$. LoRA adapters are most commonly applied to the attention query and value projection matrices (and sometimes the feed-forward layers), since those dominate a transformer's parameter count and strongly shape its behavior. Per-task adapters are stored as just the pair $(A, B)$ for each layer they are applied to, which is typically megabytes rather than the gigabytes a full fine-tuned checkpoint would need, so serving many task-specific variants of one base model becomes practical.

Worked example: For a single attention projection of shape $(12288, 12288)$ (a dimension similar to a large transformer's hidden size), full fine-tuning of that one projection would train $12288 \times 12288 = 150{,}994{,}944$ parameters. With LoRA at rank $r=8$, the trainable parameter count is $r \times (d_{in} + d_{out}) = 8 \times (12288 + 12288) = 196{,}608$ parameters, about $0.13\%$ of the full count, a roughly 768x reduction for that single projection. This is why LoRA cuts training memory so much: gradients and optimizer state (which for Adam-family optimizers are often 2-3x the raw parameter count) only need to be stored for $A$ and $B$, not for the frozen $12288 \times 12288$ matrix.

Trade-offs and pitfalls: LoRA reduces trainable parameters, but at inference the unmerged form ($W$ plus a separate low-rank multiply) adds a small amount of extra compute; in production this is almost always avoided by merging $BA$ into $W$ once training is done, which restores exactly the same inference cost as the original model with zero runtime overhead, at the cost of losing the ability to instantly swap adapters without reloading weights. Choosing $r$ too small can under-fit a task that genuinely needs a higher-rank update (complex domain shifts, multi-task mixtures), while choosing it unnecessarily large gives up most of LoRA's memory savings without a clear accuracy benefit, so rank is usually tuned empirically starting from a small value like 8.

Linear models: Advantage — fast, interpretable, easy to serve; Limitation — can't capture complex non-linear relationships. Decision trees: Advantage — interpretable and handle mixed feature types; Limitation — single trees can overfit and be unstable; need ensembles for robustness. k-NN: Advantage — simple, no training phase; Limitation — prediction is slow and memory-heavy at inference, problematic at scale. Feedforward neural networks: Advantage — can model complex non-linear patterns; Limitation — higher compute and maintenance cost, harder to interpret and tune in production.

Direct answer

Once you know a partner function is measured on something different from you (speed versus quality or risk, for example), you scope your asks to be small and cheap under their metric, and you change what "status" means when you talk to them: short, action-oriented signals instead of the detailed risk narrative you'd give your own stakeholders. You're not changing what you need, you're changing how you package it so it doesn't read as a tax on the thing they're rewarded for.

Structured elaboration

1. Diagnose the incentive, don't assume it. Confirm what the partner function is actually measured on (deploy velocity, ticket close time, uptime, cost) rather than inferring it from how they push back. Different sub-teams within the "same" function can be measured differently.
2. Scope the ask to the smallest unit that gets you what you need. If they're speed-measured, don't ask for a broad, standing review of everything; ask for a narrow, well-bounded check on the specific surface that carries the risk you actually care about, and let everything else pass without friction.
3. Translate the ask into their currency. Instead of framing a request around your risk language, frame it around what it costs (or saves) them in their terms: incident response hours avoided, rework avoided, a compliance gate they'd otherwise hit later and more expensively.
4. Change the shape of status, not just the ask. For a speed-measured partner, give a compact signal (blocked/not blocked, a count, a single risk flag) they can act on in seconds. Save the fuller narrative for your own stakeholders who need the detail. Sharing the same long-form update with both audiences under-serves the partner who needs to move fast.
5. Keep a floor. Adapting your ask to their incentive has a limit: there's a minimum you can't compromise below without failing your own mandate. Know that floor before the conversation so "scoping down" doesn't quietly become "giving up the requirement."
6. Revisit as trust builds. Early asks are necessarily narrow and low-trust. As the partner sees your asks are well-scoped and your status updates are reliable, you can often widen the ask (a slightly broader review surface, more lead time) because they've learned you're not going to slow them down for nothing.

Worked example

A platform team is measured on release velocity; a security-minded partner function is measured on defect and incident rates. Rather than asking the platform team to route every change through manual security review (a direct tax on their velocity metric), the ask is scoped to only changes that touch a named risk surface, such as authentication or payment code. Everything else ships without added friction. Status to the platform team is a single weekly line: "2 changes in the review queue, 0 blocking, both cleared by Thursday." The fuller write-up, with rationale and residual risk, goes to the security function's own leadership, not to the platform team, because that's not the audience that needs it to act.

Trade-offs & pitfalls

• Pitfall: scoping the ask down so far it stops actually managing the risk it exists to manage. Know your floor before you negotiate.
• Pitfall: assuming the incentive instead of confirming it. Guessing wrong (e.g., treating a team as purely speed-driven when they're also on the hook for a compliance metric) leads to asks that miss what would actually land.
• Pitfall: sending the same status update to every audience. It either over-informs the speed-measured partner (who tunes it out) or under-informs your own stakeholders (who need the detail to make decisions).
• Senior differentiator: treating the ask size and the status format as things you design deliberately around the incentive gap, and revisiting that design as trust changes, rather than a fixed communication style you use with everyone.

Direct answer

is_bipartite(graph) runs a BFS two-coloring pass from every not-yet-colored node (handling disconnected input), assigning each newly discovered node the opposite color of the node that discovered it, and returns False the instant an edge connects two nodes already colored the same. If the BFS completes with no such conflict, the graph is bipartite and the accumulated coloring is a valid 2-coloring, returned alongside True.

Structured elaboration

Why BFS coloring works. In a bipartite graph, every edge must connect the two groups, never two nodes within the same group, so any correct 2-coloring must alternate colors across every edge. BFS naturally colors nodes by their distance parity from the component's start node (all nodes at even distance get one color, all nodes at odd distance get the other), and this is EXACTLY a valid bipartition whenever one exists, because two nodes connected by a direct edge always differ in BFS distance by exactly 1 in a correctly-behaving coloring, guaranteeing opposite colors. A conflict (an edge whose endpoints end up the same color) can only arise when the graph structure forces two nodes at the same distance-parity from the start to also be directly connected, which happens precisely when an odd-length cycle exists.

Handling disconnection. Nodes with no path to the component the algorithm happened to start with have no BFS-derived color yet; the outer loop over every node index ensures each such component gets its OWN independent coloring pass, since disconnected components impose no constraint on each other's color choice.

Complexity. $O(V+E)$: every node is colored exactly once, and every edge is examined at most twice (once from each endpoint) across the whole run, the same bound as any BFS/DFS traversal over the full graph.

Worked example

from collections import deque
from typing import List, Optional, Tuple

def is_bipartite(graph: List[List[int]]) -> Tuple[bool, Optional[List[int]]]:
    n = len(graph)
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False, None
    return True, color

if __name__ == "__main__":
    # Case 1: bipartite (square, 0-1-2-3-0)
    graph1 = [[1, 3], [0, 2], [1, 3], [2, 0]]
    ok1, coloring1 = is_bipartite(graph1)
    print("graph1:", graph1)
    print("is_bipartite:", ok1, "coloring:", coloring1)

    # Case 2: NOT bipartite (triangle, 0-1-2-0)
    graph2 = [[1, 2], [0, 2], [0, 1]]
    ok2, coloring2 = is_bipartite(graph2)
    print("\ngraph2:", graph2)
    print("is_bipartite:", ok2, "coloring:", coloring2)

    # Case 3: disconnected, mix of a bipartite path and an isolated node
    graph3 = [[1], [0, 2], [1], []]
    ok3, coloring3 = is_bipartite(graph3)
    print("\ngraph3:", graph3)
    print("is_bipartite:", ok3, "coloring:", coloring3)

Output:

graph1: [[1, 3], [0, 2], [1, 3], [2, 0]]
is_bipartite: True coloring: [0, 1, 0, 1]

graph2: [[1, 2], [0, 2], [0, 1]]
is_bipartite: False coloring: None

graph3: [[1], [0, 2], [1], []]
is_bipartite: True coloring: [0, 1, 0, 0]

Graph 1 (a 4-node cycle) two-colors cleanly ([0,1,0,1], alternating perfectly around the cycle). Graph 2 (a 3-node cycle, a triangle, the smallest possible odd cycle) fails, correctly returning None for the coloring rather than a partial or misleading result. Graph 3 (a disconnected graph: a 3-node bipartite path 0-1-2 plus an isolated node 3) succeeds, and node 3, having no edges, keeps whatever color the outer loop happens to assign it (color 0 here, since it starts its own trivial single-node component); an isolated node can never itself cause a conflict, since it has no edges to check.

Trade-offs and pitfalls

• Common mistake: returning False but still returning a PARTIAL, invalid coloring array instead of None (or otherwise clearly signaling invalidity). A caller that does not carefully check the boolean first could mistake a partial, contradiction-containing coloring for a genuine 2-coloring; returning None for the coloring on the False path makes this class of bug impossible rather than merely unlikely.
• Common mistake: only starting BFS once, from node 0. On a graph with disconnected components, this leaves later components entirely uncolored and unchecked; the fix is looping the outer for start in range(n) over every node, which this implementation does correctly.
• An isolated node is trivially bipartite on its own (it has no edges to violate the bipartition condition), and this implementation handles it for free: it becomes its own singleton component, gets colored, and the while-loop body (which only runs on an edge) never executes for it.
• This early-returns on the FIRST conflict found, which is efficient (no wasted work continuing to color a graph already known non-bipartite) but means the specific coloring state at the moment of the return is an implementation artifact of traversal order, not something a caller should read any meaning into beyond "a conflict exists somewhere."

Direct answer

Convert the condition into a 0/1 indicator (1 if $arr[i] \le k$, else 0), and notice the total count of 1s, call it $m$, never changes since swaps only move values around. The minimum swaps is $m$ minus the largest number of 1s already sitting inside any window of length $m$: slide a fixed-size window of length $m$ across the array once, track how many 1s are in it, and subtract the best count from $m$.

Structured elaboration

Why this reduces to a fixed-size sliding window:

1. Reduce the value condition to a binary property. Whether an element "counts" only depends on arr[i] <= k, so think of the array as a sequence of 1s (qualifying elements) and 0s (non-qualifying). The actual values stop mattering once you've made this reduction; only positions matter from here on.
2. The target size is fixed and known up front. If there are $m$ qualifying elements total, any valid final arrangement must place all $m$ of them into some contiguous block of length exactly $m$. You are choosing where that block ends up, not how many elements are in it.
3. Correctness of the swap count for one candidate window. Fix a candidate window of length $m$ and say it currently contains $x$ qualifying elements (so $m - x$ non-qualifying elements sit inside it). Since there are $m$ qualifying elements in total and $x$ of them are already inside, exactly $m - x$ qualifying elements sit outside the window. That gives a perfect one-to-one pairing: each non-qualifying element inside the window can be swapped directly with a qualifying element outside it, in exactly $m - x$ swaps, and no arrangement can do it in fewer (every one of those $m-x$ misplaced elements inside the window has to leave, and each swap moves at most one qualifying element in).

4. Minimize over all candidate windows. Since swaps required $= m - x$, minimizing swaps is the same as maximizing $x$, the count of qualifying elements already inside the window. Slide a window of fixed length $m$ across the array once (classic fixed-size sliding window: add the incoming element's contribution, drop the outgoing element's contribution), track the maximum $x$ seen, and the answer is $m - x_{\max}$.

Complexity: one pass to count $m$, one pass to slide the window: $O(n)$ time. The window count is maintained as a running integer, no auxiliary array is needed, so this runs in $O(1)$ extra space beyond the input.

Worked example

Using the array from the question: arr = [2, 7, 9, 5, 8, 7, 4], k = 5.

def min_swaps_to_group(arr, k):
    n = len(arr)
    total = sum(1 for x in arr if x <= k)
    if total == 0 or total == n:
        return 0
    window_count = sum(1 for x in arr[:total] if x <= k)
    best = window_count
    for i in range(total, n):
        if arr[i] <= k:
            window_count += 1
        if arr[i - total] <= k:
            window_count -= 1
        best = max(best, window_count)
    return total - best

arr = [2, 7, 9, 5, 8, 7, 4]
k = 5
print(f"arr={arr}, k={k}")
print(f"elements <= k: {[x for x in arr if x <= k]}")
result = min_swaps_to_group(arr, k)
print(f"min swaps = {result}")
assert result == 2

def min_swaps_auxiliary_array(arr, k):
    n = len(arr)
    indicator = [1 if x <= k else 0 for x in arr]
    total = sum(indicator)
    if total == 0 or total == n:
        return 0
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + indicator[i]
    best = 0
    for i in range(n - total + 1):
        best = max(best, prefix[i + total] - prefix[i])
    return total - best

def brute_min_swaps(arr, k):
    n = len(arr)
    total = sum(1 for x in arr if x <= k)
    if total == 0 or total == n:
        return 0
    best = 0
    for i in range(n - total + 1):
        window = arr[i:i+total]
        cnt = sum(1 for x in window if x <= k)
        best = max(best, cnt)
    return total - best

import random
random.seed(5)
mismatches = 0
for _ in range(200):
    n = random.randint(1, 10)
    a = [random.randint(0, 10) for _ in range(n)]
    kk = random.randint(0, 10)
    r1, r2, r3 = min_swaps_to_group(a, kk), min_swaps_auxiliary_array(a, kk), brute_min_swaps(a, kk)
    if not (r1 == r2 == r3):
        mismatches += 1
print(f"200 randomized trials (seed 5): O(1)-space window, auxiliary-array, and brute force all agreed, mismatches={mismatches}")

Output:

arr=[2, 7, 9, 5, 8, 7, 4], k=5
elements <= k: [2, 5, 4]
min swaps = 2
200 randomized trials (seed 5): O(1)-space window, auxiliary-array, and brute force all agreed, mismatches=0

Trace: the qualifying indicator is [1,0,0,1,0,0,1], so $m = 3$. Every one of the five possible length-3 windows ([1,0,0], [0,0,1], [0,1,0], [1,0,0], [0,0,1]) contains exactly one qualifying element, so $x_{\max} = 1$ and the answer is $3 - 1 = 2$, matching the question's stated result. This was cross-checked against the brute-force reference and the auxiliary-array version shown above, over 200 randomized trials (seed 5); all three agreed in every trial, as the printed line confirms.

Trade-offs & pitfalls

• The "swap" here is a free swap between any two positions, not an adjacent swap. If the problem instead restricted swaps to adjacent elements only, the count would be a different (and generally larger) quantity related to counting inversions, not this window-based formula. Always confirm which swap model is meant before applying this technique.
• A common wrong turn is trying to simulate actual swaps rather than reasoning about a target window. The technique works precisely because you never need to decide an order of swaps: you only need to pick the best final window position, and the count follows algebraically.
• Watch the two boundary cases: if every element already qualifies ($m = n$) or none do ($m = 0$), the answer is trivially 0 and the sliding window should short-circuit rather than run (attempting a window of size 0 or size $n$ needs no scan).
• Keeping a running window count (add incoming, subtract outgoing) instead of re-summing the window from scratch each time is what keeps this $O(n)$ instead of $O(n \cdot m)$; re-summing per position is the most common efficiency regression candidates introduce under pressure.

Direct answer

A discriminative model learns the conditional distribution $P(y \mid x)$ directly: it maps an input straight to a label or decision boundary. A generative model learns (explicitly or implicitly) how the data itself was produced, either the joint $P(x, y)$ or the marginal $P(x)$. Because it models how data is generated, a generative model can also sample new data, something a discriminative model cannot do at all.

Structured elaboration

What each optimizes. A discriminative classifier like logistic regression or an SVM fits a boundary that separates classes as well as possible, using only the conditional likelihood of the label given the input. A generative model like a naive Bayes classifier, an autoregressive language model, a GAN, or a VAE instead tries to capture the full data-generating process, then derives $P(y\mid x)$ (if it needs to classify at all) via Bayes' rule from $P(x\mid y)$ and $P(y)$.

Concrete examples.

• Discriminative: logistic regression for spam detection, an SVM for image classification, a discriminative fine-tuned BERT for sentiment classification.
• Generative: an autoregressive LLM producing text token by token, a GAN or diffusion model producing images, a VAE reconstructing and sampling from a learned latent space.

Three practical implications of the choice.

1. Only a generative model can produce new content. If the product need is "write an email" or "draw an image," you need a generative model; a classifier cannot do this by construction.
2. Discriminative models are usually more sample-efficient and accurate for pure classification. They spend their entire capacity on the decision boundary instead of also modeling the full input distribution, so with a fixed dataset size a discriminative model typically classifies better.
3. Generative models carry model-misspecification risk that discriminative models mostly avoid. If your assumptions about how the data is generated are wrong (e.g., a bad choice of prior or emission distribution), a generative model's classification accuracy degrades along with its generative quality. A discriminative model that never modeled the generative process has no such assumption to get wrong.

Worked example

Take spam detection. A discriminative logistic regression sees an email's features (word counts, sender domain, links) and directly outputs $P(\text{spam}\mid \text{features})$; it has no notion of what a "typical" spam email looks like beyond the boundary it fit. A generative naive Bayes classifier instead estimates $P(\text{word}\mid \text{spam})$ and $P(\text{word}\mid \text{not spam})$ for every word, then combines them with Bayes' rule to classify a new email. Because it explicitly modeled $P(x\mid y)$, that same naive Bayes model could (crudely) generate a plausible spam-sounding word distribution, while the logistic regression has no way to do so; it only ever learned where the boundary sits.

Trade-offs & pitfalls

The two are not always in tension: a generative classifier CAN outperform a discriminative one when labeled data is scarce, because it borrows statistical strength from modeling the unlabeled input distribution too. But when you have plenty of labeled data and only need a decision, the extra generative modeling is often wasted compute and can hurt calibration if the generative assumptions are even slightly wrong. The common pitfall is picking a generative model "because it's more powerful" for a task that is purely classification; if the product only ever needs a label, a well-tuned discriminative model is usually cheaper to train, faster to serve, and more accurate.