FAANG-Standard Backend Developer (Mid-Level) Interview Preparation Guide

Direct answer

Atomic multi-service reconciliation over a dependency graph needs the SAME "all succeed or safe rollback" guarantee a database transaction provides, but GitOps has no equivalent of a database's native transaction mechanism, each service's manifests apply independently through the underlying Kubernetes API, so the operator has to construct that guarantee itself: track each service's individual reconciliation status against the dependency graph's required ORDER, and on ANY service's failure, actively COMPENSATE (roll back) every service that had already succeeded in this same multi-service change, rather than leaving a partially-applied graph in an inconsistent state.

Structured elaboration

Data model. A MultiServiceChange custom resource capturing: the SET of services involved in this specific coordinated change, their DEPENDENCY ORDER (a directed acyclic graph, service B cannot reconcile until service A, which it depends on, has succeeded), each service's OWN manifest reference (a Git commit/digest), and, critically, each service's PRIOR successful state (the last known-good manifest reference for that service, needed as the compensation target if a rollback becomes necessary).

Reconciliation loop. Processes services in DEPENDENCY ORDER (a topological sort of the graph), reconciling each only once its dependencies have themselves reached a succeeded state; this is the mechanism that gives ordering guarantees a plain, independent per-service reconciliation loop does not provide on its own.

Handling of partial failures. If a service in the middle of the ordered sequence FAILS to reconcile (after its own bounded retry), the operator does NOT continue reconciling the REMAINING, not-yet-processed services in the graph (since they may depend on the failed one, and even if they don't directly, the overall multi-service change is now incomplete); it transitions the MultiServiceChange to a compensating state and begins rollback.

Rollback/compensation semantics. Roll back every service that ALREADY succeeded in THIS multi-service change, in REVERSE dependency order (a service's dependents must be rolled back before the service itself, mirroring the forward order's own logic), reverting each to its recorded PRIOR successful state (not simply "delete," since the prior state may itself be a specific, meaningful configuration, not merely "nothing"); the never-reconciled remaining services in the graph need no compensation at all, since they were never actually changed.

Worked example

A MultiServiceChange spanning three services with dependency order network-policy before auth-service before checkout-service (checkout depends on auth, auth depends on the network policy being in place first):

1. network-policy reconciles successfully first (no dependencies).
2. auth-service reconciles successfully second (its dependency, network-policy, already succeeded).
3. checkout-service FAILS to reconcile (its new manifest references a config value that does not exist yet).
4. The operator transitions to compensating: rolls back auth-service to its PRIOR successful manifest first (checkout, the failed one, was never actually applied, so it needs no rollback, just needs to stop being retried), then rolls back network-policy to its prior state.
5. Final state: all three services back at their PRE-CHANGE configuration, a clean, fully-compensated failure, rather than network-policy and auth-service left on their NEW configuration while checkout alone failed, which would have been a genuinely inconsistent, partially-migrated state.

Trade-offs and pitfalls

• Common mistake: rolling back services in the SAME order they were applied, rather than REVERSE dependency order. Per the worked example, rolling back network-policy (which auth-service depends on) WHILE auth-service is still running its new configuration risks auth-service operating against a network policy that no longer matches what it expects, briefly recreating the exact kind of inconsistency the whole compensation mechanism exists to avoid; reverse-order rollback (dependents first, dependencies last) is what keeps every INTERMEDIATE state during the rollback itself consistent too, not just the final state.
• "Roll back to the prior successful state" requires that prior state to have actually been RECORDED before the new change began, an operator that only tracks the CURRENT desired state, with no memory of what preceded it, cannot perform this rollback at all; this is a real, easy-to-omit data-model requirement, not an implementation detail.
• A service that was never reached in the forward pass (because an earlier dependency failed first) needs NO compensation, per the worked example's checkout-service, attempting to "roll back" a service that was never actually changed is at best a wasted no-op and at worst risks touching a resource the operator has no legitimate reason to be modifying right now.
• This entire mechanism assumes the dependency graph itself is ACCURATE and complete: a graph missing a real dependency risks reconciling (or worse, considering "successful") a service whose actual prerequisite was never satisfied, defeating the ordering guarantee the whole design exists to provide.

Direct answer. A standard B-tree index stores values in sorted order, which lets it efficiently find a matching PREFIX of a string; a wildcard at the START of a LIKE pattern means there's no fixed prefix to search for, so the index can't narrow the search at all and the engine falls back to checking every row's text against the pattern directly.

Structured elaboration. LIKE 'foo%' (wildcard only at the end) can use a standard B-tree index efficiently, because every string matching that pattern shares the same prefix, 'foo', which the index's sorted order can jump straight to. LIKE '%foo%' or LIKE '%foo' (wildcard at the start) has no such fixed prefix: a match could be any string CONTAINING or ENDING WITH 'foo' anywhere, which the sorted order of a standard index gives no leverage on at all, so the engine has no better option than scanning and checking every row.

Realistic options: a specialized full-text search index (built for token or substring matching rather than prefix matching) is the most direct fix if your engine supports one and the matching semantics fit; a trigram or n-gram index (where supported) can accelerate substring matches specifically, including leading-wildcard patterns, by indexing small overlapping fragments of the text rather than the whole string; and, if the real requirement is closer to "search," moving that specific workload to a dedicated search engine designed for it is often the more durable long-term answer once a standard relational index genuinely can't help.

Worked example. A dashboard filter doing WHERE comments LIKE '%refund%' against a large text column is the exact shape that defeats a plain B-tree index; if the underlying database supports a trigram index, adding one on that column can make this specific kind of substring search dramatically faster without changing the query at all, since the trigram structure is built specifically to handle "the pattern could start anywhere" searches that a standard index can't.

Trade-offs and pitfalls. Specialized indexes for this kind of search (trigram or full-text) cost more storage and more write-time maintenance than a standard B-tree, and aren't a good fit for every use case (very short strings, or a genuinely rare query pattern that doesn't justify the ongoing cost); weigh how often this kind of search actually runs, and how latency-sensitive it is, against that ongoing cost before reaching for a specialized index.

Direct answer

A monolith is a single deployable unit; microservices split a system into independently deployable services that communicate over the network. The monolith wins on development velocity and simplicity while the team and codebase are small; microservices win on independent scaling, fault isolation, and team autonomy once the organization and traffic have grown enough to need them, but they add real operational cost that a small team pays for even before it needs the benefits.

Structured elaboration

Worked example

A five-person startup with 200 daily active users splits its checkout flow into a separate payments service, an inventory service, and a notifications service on day one. In practice: three CI/CD pipelines to maintain instead of one, a network call, with its own latency and failure modes, added to every checkout in place of a function call, and the same five engineers now also debugging cross-service request tracing for a system with barely any real traffic. None of the microservices benefits, independent team ownership or independent scaling under real load, apply yet, because there is one team and no bottleneck to isolate. A modular monolith, meaning a single deployable codebase with clean internal module boundaries and clear ownership per module, gets the same code-organization benefit without the network and operational cost, and it can be decomposed later once an actual bottleneck, not a hypothetical future one, justifies the split.

flowchart TB
  subgraph MONO["Monolith: one deployable unit"]
    direction TB
    W[Web layer]
    B[Business logic]
    D[Data access]
  end
  subgraph MICRO["Microservices: independently deployable, network-connected"]
    direction TB
    PaySvc[Payments service]
    InvSvc[Inventory service]
    NotifSvc[Notifications service]
    PaySvc <--> InvSvc
    InvSvc <--> NotifSvc
  end

Trade-offs & pitfalls

• Adopting microservices for resume-driven or "best practice" reasons rather than a named bottleneck.
• Splitting along technical layers (a services layer, a database layer) instead of business capability boundaries, which just moves tight coupling onto the network instead of removing it; this is the organizational mirror named Conway's Law (a system's structure tends to mirror the communication structure of the organization that built it, so splitting along technical layers just recreates the same coordination problems on the network instead of removing them), worth knowing by name without needing to re-derive it here.
• Treating "the codebase feels big" as the signal a split is overdue, instead of a concrete one: one team's deploy regularly breaks or is blocked by another team's unrelated changes.

Direct answer: Break the project into its major components or workstreams, and for each say plainly whether you owned it, contributed to it, or reviewed it, backed by something concrete you can point to rather than blanket language like "we" or "helped."

Why interviewers ask this

They're checking whether you can isolate your individual contribution inside a team effort, and whether your language ("I" versus "we") tracks something real rather than blending your work with everyone else's.

A simple ownership vocabulary

How to structure the answer

1. Break the project into 3-5 components (for example: scope and requirements, the core build, testing, rollout, monitoring).
2. Label your involvement per component using the vocabulary above.
3. Pick one component you owned and be ready to go deep on it, since that's what actually proves the claim rather than just asserting it.

Worked example (illustrative skeleton)

A cross-functional launch project broken into four components: requirements and scope (contributed: shaped 2 of 6 requirements after running user interviews), the core feature build (owned: built and shipped it end to end), rollout communication (supported: wrote the release notes, didn't own the go/no-go decision), and post-launch monitoring (owned: set up the alert that caught a regression). The rollout itself was staged from 10% of users to 100% over three weeks; the monitoring alert flagged the regression during the first week, while the remaining 90% of users hadn't yet been exposed to the change.

Trade-offs and pitfalls

• Overclaiming ("I built the whole thing") when you contributed one piece invites a follow-up you can't sustain once the interviewer asks for detail.
• Underclaiming ("we did everything together") reads as no real individual ownership at all.
• Not having one component ready to go deep on undermines the whole answer.
• Being honest about where you were a contributor rather than the owner builds credibility; it doesn't weaken the answer.

Direct answer

Sponsorship means spending your own credibility to open a door someone couldn't open for themselves, which is different from mentoring, which is advice given directly to the person. The core act is advocating for them by name in a room they aren't in, backed by specific, evidence-based reasons they deserve the opportunity.

What sponsorship requires

Political capital and timing, not just advice. Mentoring can happen anywhere, anytime, one on one. Sponsorship requires actually being present, or having enough standing, in the room where a real decision gets made: a promotion committee, a staffing decision, an assignment to a high-visibility project.

An evidence-backed case, not a vague endorsement. "They're great" doesn't move a room. Specific, concrete contributions you can vouch for personally do. Building this case ahead of time, before the opportunity comes up, is part of the work.

Deciding when it's warranted. The right moment is when someone is already delivering at the target level but lacks the visibility or exposure to be considered for it, there's a real decision window open, and you have enough credibility in that specific room for your advocacy to actually carry weight.

Making the specific ask. Vouching in general terms is weaker than naming the specific opportunity and asking for the specific outcome: this person, for this role, on this team, now.

Aftercare. Sponsorship only compounds if the person knows it happened. Telling them what you did lets them lean into the opportunity and know someone is actively in their corner, not just quietly hoping things work out. Following up on the outcome, win or not, matters too.

Worked example

Someone you work closely with does excellent work but has almost no visibility outside their immediate team. A high-visibility opportunity, or a promotion cycle, comes up in a room they aren't part of. You go in with specific, concrete contributions you can personally back, not general praise, and explicitly vouch for their readiness for that specific opportunity. Afterward, they're included in the opportunity or the promotion conversation, and you tell them directly what you did and why, rather than letting them find out secondhand or not at all.

Trade-offs and pitfalls

Sponsoring someone whose work you can't concretely back with specifics spends your credibility on hope rather than evidence, and if it doesn't pan out, it costs you standing in that room for the next person you'd want to sponsor.

Sponsoring quietly and never telling the person defeats much of the point. They don't know to lean into the opportunity, and they don't know someone is actively advocating for them, which is often as valuable as the opportunity itself.

Sponsorship is finite. You have a limited amount of credibility to spend across your whole network, which means you genuinely cannot sponsor everyone equally, and who you choose to spend it on is a real, sometimes uncomfortable decision worth being honest with yourself about.

A common confusion is treating a glowing performance review comment as sponsorship. Real sponsorship requires actually being in the room, advocating for a specific decision, not just praising someone in the abstract where it doesn't reach the decision-maker.

Definition & role
TTL (time-to-live) is an expiry attached to a cached item that tells the cache when the entry is invalid. TTL controls freshness, memory reclamation, and how often the backend must be hit for updates.

Short vs Long TTL — trade-offs

• Short TTL (e.g., seconds–minutes)
  • Pros: fresher data, less staleness risk
  • Cons: lower cache hit rate, higher backend load and possible thundering-herd spikes
• Long TTL (e.g., hours–days)
  • Pros: high hit rate, low backend load, lower latency
  • Cons: higher staleness; larger memory use if many keys

Effect summary:

• Short TTL → lower hit rate, higher backend requests
• Long TTL → higher hit rate, lower backend load, more staleness

Sliding TTL vs Fixed TTL

• Fixed TTL: expiry is set once when the item is written. Use when data validity is time-based or when strict TTL semantics required (e.g., ephemeral auth tokens).
• Sliding TTL (refresh on access): extend TTL each read. Use for session-like data or hot objects where you want to keep frequently-accessed items cached and evict cold ones.

Example Redis / Memcached usage

• Redis fixed TTL:

SETEX user:123 300 '{"name":"A"}'   # expires in 300s

• Redis sliding TTL (pseudo):

# get value, then reset expire to extend TTL
val = GET user:123
EXPIRE user:123 300

• Memcached set with TTL:

set session:abc 0 1800 60\r\n<value>\r\n  # expires in 1800s

When to choose

• Use short TTL for highly dynamic data or when correctness > performance.
• Use long TTL for read-heavy immutable data (product catalogs).
• Use sliding TTL for session caches or to retain “hot” items without backend hits.

Always monitor hit rate, backend latency, memory, and consider rate-limiting or request coalescing to mitigate stampedes.

Direct answer

For a nested, partially-optional JSON payload, validate outside-in: confirm the overall shape first (is the body an object, is user an object), then validate required leaf fields, then optional nested fields only if their parent is present, returning 400 with a field-path-specific error the first layer that fails rather than attempting to validate deeper structure that depends on an already-broken parent.

Structured elaboration

Order of checks. (1) The request body itself must be a JSON object, not an array or a scalar; reject otherwise with a generic "malformed request body" 400. (2) The required top-level object user must exist and be an object; if user is missing entirely, there is no point validating user.name next, since the path doesn't exist. (3) Required leaf fields inside user (name, email) are checked next, each independently, collecting every failure rather than stopping at the first, since that gives the client one round-trip to fix everything instead of one field per round-trip. (4) Optional nested fields (preferences.newsletter, items) are validated only if present: an absent optional field is not an error, but a present one with the wrong type is. (5) Array elements (items[]) are validated per-element, with the index included in the error path (items[2].qty) so the client can find the exact bad entry in a list.

Status codes. Malformed body shape or any failed validation: 400, with a body listing every failing field path and a short reason (never the raw submitted value for anything that might be sensitive). If the request is otherwise well-formed but conflicts with existing state (for example this is actually an upsert and the referenced item does not exist), that's a distinct code such as 404 or 409, not 400, so the client's retry logic can tell "you sent something malformed" apart from "you sent something valid that doesn't apply here".

Logging. Log the validation failure with the field paths and reasons (not the raw payload, which may contain PII in fields like email), tagged with a request/correlation ID so the failure can be traced without storing the sensitive body long-term.

Worked example

Given { user: { name: "", email: "not-an-email", preferences: { newsletter: "yes" } }, items: [ { id: 1, qty: -3 }, { id: 2 } ] }: the body is an object and user is an object, so validation proceeds to leaf fields. It collects: user.name is empty (required, non-empty string expected), user.email fails a format check, user.preferences.newsletter is present but not a boolean ("yes" instead of true), items[0].qty is negative (must be >= 0), and items[1] is missing the required qty field entirely. All five are returned together in one 400 response rather than one at a time, and the response never echoes back the invalid email value verbatim in case it was copy-pasted from something sensitive, it only names the field and the rule it broke.

Trade-offs and pitfalls

Validating every failure at once (rather than stopping at the first) is friendlier to the client but costs slightly more code, since you cannot just throw on the first bad field, you have to accumulate. It is worth it for anything a human fills out through a form. The most common mistake here is validating a nested optional field even when its parent object is entirely absent, which produces a confusing error like "preferences.newsletter must be a boolean" for a request that never sent preferences at all: always check presence of the parent first. A second common mistake is echoing the raw invalid value back in every error message without thinking about which fields might carry sensitive data.

Direct answer

Robin Hood hashing is a refinement of open addressing with linear probing. On insertion, whichever entry has probed farther from its own ideal ("home") bucket wins the slot: if the entry currently being inserted has a larger probe distance than the entry sitting in the slot being examined, they swap, and the displaced entry keeps walking forward carrying its own probe count. Applied consistently, this "steal from the entry that has probed less, hand the slot to the entry that has probed more" rule does not change the total number of probes summed across all keys (that total is fixed by the load factor); it redistributes them, so probe lengths cluster tightly around the average instead of a few unlucky keys absorbing very long chains. That is the sense in which it reduces variance and tightens the worst case.

How it works: insertion and the stealing rule

Define the probe distance of an entry as how many slots past its home bucket $h(k) \bmod \text{tableSize}$ it currently sits. On insert:

1. Start at the home bucket for the new key, with probe distance 0.
2. Walk forward slot by slot. At each occupied slot, compare the incoming entry's current probe distance to the resident entry's stored probe distance.
   • If the incoming entry's distance is strictly greater, swap: the incoming entry takes the slot, and whoever used to live there becomes the new "incoming" entry, continuing the walk with its own probe distance incrementing from there.
   • Otherwise, leave the resident alone and keep walking with the incoming entry, incrementing its own probe distance by one each step.
3. Place at the first empty slot found.

This is the "Robin Hood" framing: an entry that has already probed far (it has paid a high cost) takes priority over an entry that has probed little, by force if necessary.

Deletion: backward-shift, not tombstones

Vanilla linear probing usually deletes by leaving a tombstone marker behind, because a plain empty slot would wrongly terminate the probe sequence for keys inserted afterward that hashed to an earlier position. Robin Hood tables instead use backward-shift deletion: remove the target entry, then walk forward from the vacated slot, and as long as the next entry has a probe distance greater than 0, shift it back into the gap and decrement its stored probe distance; stop at the first empty slot or the first entry already at probe distance 0 (it is already at its own home bucket, so it cannot move back). Because probe distances stay tight to begin with, and there is no tombstone buildup, lookups after many deletions don't degrade the way they do in tombstone-based tables.

Expected probe length is unchanged; variance is what drops

For uniform hashing under linear probing with load factor $\alpha = n / \text{tableSize}$, the classic expected-probe-count results are:

$E[\text{probes}_{\text{success}}] \approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$

$E[\text{probes}_{\text{fail}}] \approx \frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$

Robin Hood's swaps don't change WHICH slots end up occupied, only which key occupies which slot within a cluster, so the average probe length across all keys is identical to vanilla linear probing at the same load factor. What changes is the spread: instead of a handful of keys landing at the tail of a long clustering run (paying far above the mean), Robin Hood keeps every key in a cluster close to that cluster's average probe distance. Lower variance directly caps the worst observed probe length, which is what drives your slowest lookups, not the mean.

Worked example

import random
import zlib


def stable_hash(key, table_size):
    return zlib.crc32(key.encode("utf-8")) % table_size


class VanillaLinearProbe:
    def __init__(self, size):
        self.size = size
        self.slots = [None] * size

    def insert(self, key, value):
        i = stable_hash(key, self.size)
        dist = 0
        while self.slots[i] is not None and self.slots[i][0] != key:
            i = (i + 1) % self.size
            dist += 1
        self.slots[i] = [key, value, dist]

    def probe_distances(self):
        return [s[2] for s in self.slots if s is not None]


class RobinHood:
    def __init__(self, size):
        self.size = size
        self.slots = [None] * size  # each slot: [key, value, probe_distance]

    def insert(self, key, value):
        i = stable_hash(key, self.size)
        entry = [key, value, 0]
        while True:
            if self.slots[i] is None:
                self.slots[i] = entry
                return
            if self.slots[i][0] == key:
                self.slots[i][1] = value
                return
            if entry[2] > self.slots[i][2]:   # incoming probed farther: steal the slot
                self.slots[i], entry = entry, self.slots[i]
            i = (i + 1) % self.size
            entry[2] += 1

    def probe_distances(self):
        return [s[2] for s in self.slots if s is not None]


def summarize(dists):
    mean = sum(dists) / len(dists)
    variance = sum((d - mean) ** 2 for d in dists) / len(dists)
    return max(dists), round(mean, 3), round(variance, 3)


if __name__ == "__main__":
    random.seed(42)
    SIZE = 1000
    keys = [f"user:{random.randint(0, 10_000_000)}" for _ in range(900)]  # load factor 0.9

    vanilla = VanillaLinearProbe(SIZE)
    for k in keys:
        vanilla.insert(k, 1)
    v_max, v_mean, v_var = summarize(vanilla.probe_distances())

    rh = RobinHood(SIZE)
    for k in keys:
        rh.insert(k, 1)
    r_max, r_mean, r_var = summarize(rh.probe_distances())

    print(f"vanilla linear probing: max={v_max} mean={v_mean} variance={v_var}")
    print(f"Robin Hood hashing:     max={r_max} mean={r_mean} variance={r_var}")

Output:

vanilla linear probing: max=103 mean=4.549 variance=136.27
Robin Hood hashing:     max=15 mean=4.549 variance=14.903

At 90% load factor (900 keys in a 1000-slot table), both variants land on the identical mean probe distance (4.549), confirming the average is unaffected by the stealing rule. Robin Hood's variance is roughly 9x smaller (14.9 versus 136.3), and its worst single probe distance drops from 103 to 15: no key gets stranded far from home, which is the practical payoff.

Trade-offs and pitfalls

• Extra bookkeeping per entry (the stored probe distance costs a few bits per slot) and a marginally more complex insert path (a loop with a conditional swap instead of a plain forward scan).
• Still bound by the same load-factor blowup as any open-addressing scheme: as $\alpha \to 1$, both the mean and the (now smaller, but nonzero) variance still explode, so you still need to resize well before the table gets too full, typically in the 0.7 to 0.8 range rather than pushing toward 0.9 or above.
• A common mistake is assuming Robin Hood also fixes clustering caused by a weak hash function; it only redistributes probe distance within whatever clustering the hash function produces. If keys collide heavily because the hash itself is poorly distributed, Robin Hood smooths the symptom, it does not fix the cause.
• Deletion correctness is easy to get subtly wrong: shifting back an entry that is already at probe distance 0 would move it before its own home bucket, corrupting future lookups; the backward-shift loop must stop there.

Direct answer

Assign each arriving task to whichever machine currently has the smallest total load (the "least-loaded machine" greedy rule, also called list scheduling). This online rule is never worse than twice the optimal offline makespan, and a short exchange-style argument tightens that to a factor of $\left(2 - \frac{1}{m}\right)$, where m is the number of identical machines. This is the classical Graham's bound (1966). If tasks additionally carry hard deadlines, a single machine's feasibility is best handled separately by Earliest Deadline First (EDF); no online multi-machine rule offers a comparable constant-factor guarantee once deadlines are layered on top of load balancing.

Structured elaboration

Setup: m identical machines, tasks arrive one at a time with processing time $p_i$, no knowledge of future arrivals, goal is to minimize the makespan (the finish time of the last task to complete).

Greedy rule: on each arrival, place the task on the machine with the current minimum cumulative load.

The exchange/potential argument for the bound. Let job j be the one that finishes last in the greedy schedule, running on machine i, starting at time t. Because greedy always routes work to whichever machine has the least load at that instant, every OTHER machine's load at time t must already be at least t (otherwise greedy would have picked one of them instead). Summing that lower bound across all m machines: the total work already placed before job j arrived, $P - p_j$ (where P is the sum of all processing times), is at least $m \cdot t$. That gives:

using two separate lower bounds on any optimal schedule's makespan: the average load $P/m \le OPT$, and the single largest job $p_j \le OPT$ (any schedule must place job j somewhere, taking at least $p_j$ time there). The "exchange" insight is that at the exact moment job j was placed, no machine could have been idler than machine i, so every machine had already absorbed unavoidable work, not that two individual schedule decisions are swapped directly.

Deadline extension: on a single machine, preemptive EDF is optimal for feasibility (it schedules any instance that has a feasible schedule at all). Once you combine online arrival, multiple machines, AND hard deadlines, no algorithm achieves a constant competitive ratio in the worst case; production systems fall back to a fast per-machine EDF feasibility check (admission control) layered on top of the same least-loaded routing, rather than chasing a provably-optimal global schedule.

import itertools

def greedy_list_scheduling(processing_times, m):
    """Assign each task, in arrival order, to whichever of the m machines
    currently has the smallest total load."""
    loads = [0] * m
    for p in processing_times:
        i = min(range(m), key=lambda k: loads[k])
        loads[i] += p
    return max(loads), loads

def optimal_makespan_bruteforce(processing_times, m):
    """Brute-force optimal offline makespan (small n only)."""
    n = len(processing_times)
    best = float("inf")
    for assignment in itertools.product(range(m), repeat=n):
        loads = [0] * m
        for idx, machine in enumerate(assignment):
            loads[machine] += processing_times[idx]
        best = min(best, max(loads))
    return best

m = 3
processing_times = [1, 1, 1, 1, 1, 1, 3]  # m*(m-1) unit tasks, then one size-m task
greedy_makespan, loads = greedy_list_scheduling(processing_times, m)
opt = optimal_makespan_bruteforce(processing_times, m)
print(f"greedy loads: {loads}, makespan: {greedy_makespan}")
print(f"optimal makespan: {opt}")
print(f"ratio: {greedy_makespan / opt:.4f}, bound (2 - 1/m): {2 - 1/m:.4f}")

Output:

greedy loads: [5, 2, 2], makespan: 5
optimal makespan: 3
ratio: 1.6667, bound (2 - 1/m): 1.6667

Worked example

With m = 3 machines, six unit-size tasks arrive first, then one size-3 task. Greedy spreads the six units evenly (2 per machine), then the size-3 task lands on whichever machine is currently tied for least-loaded, giving loads [5, 2, 2] and a makespan of 5. The optimal offline schedule instead puts the size-3 task alone on one machine (load 3) and splits the six unit tasks 3-and-3 across the other two (loads 3, 3), for an optimal makespan of 3. The ratio, 5/3 = 1.667, exactly matches $2 - \frac{1}{3}$: this is the standard tight instance showing the bound isn't just a proof artifact, an adversary really can force it.

Trade-offs & pitfalls

• The bound assumes identical machines with no migration; allowing tasks to migrate after the fact often does much better in practice, at the cost of moved-task overhead and more bookkeeping.
• The proof needs BOTH lower bounds ($P/m$ and $p_j$); relying on $P/m$ alone fails the moment one job is very large, since a single huge job forces a bigger optimal makespan than "average load" alone would suggest.
• Tie-breaking among equally-loaded machines does not affect the worst-case ratio, but a naive deterministic tie-break (always lowest index) can create structural correlation with adversarial arrival patterns; some implementations break ties randomly to avoid that.
• If tasks carry deadlines, "least-loaded" optimizes makespan, not deadline feasibility; the least-loaded machine at arrival time is not necessarily the one where this specific task's deadline is still reachable, so admission control needs its own per-machine feasibility check rather than trusting the load-balancing rule alone.
• The (2 - 1/m) bound does NOT generalize to machines with different speeds (unrelated or uniform machines): "current load" stops being the right proxy for "expected finish time" once machines process work at different rates, and a different assignment rule is needed.

Direct answer

This uses the same core technique as any in-place, sorted-array deduplication: a write pointer k tracks the end of the deduplicated prefix, a read pointer scans forward, and each element is copied forward only when it differs from the last kept value. For the array [1, 1, 2], this produces new length 2, with the array's first two positions becoming [1, 2].

Structured elaboration

The algorithm

Keep k = 1 to start (the first element is always kept). Scan i from 1 onward. Whenever nums[i] != nums[k - 1], write nums[i] into position k and increment k; otherwise, skip it. Because the input is sorted, every duplicate of a value sits immediately next to it, so this single backward-looking comparison is enough to catch every duplicate, without a hash set or any extra storage.

Tracing the given example precisely

For [1, 1, 2]: start k = 1. At i = 1, nums[1] = 1 equals nums[k-1] = nums[0] = 1, so it is skipped, k stays at 1. At i = 2, nums[2] = 2 differs from nums[0] = 1, so it is written to position k = 1, giving nums = [1, 2, 2], and k becomes 2. The loop ends, k = 2 is the new length, and the first two positions, [1, 2], are exactly the deduplicated result the question asks for. The value still sitting at index 2 (the original last 2, now stale) is irrelevant, since the contract only guarantees positions before the returned length are meaningful.

Edge cases

An empty array must return length 0 immediately, without ever touching an index, since there is no element to seed the write pointer with. An all-duplicates array (say, three copies of the same value) collapses to length 1: the first occurrence is kept, and every later occurrence matches nums[k-1] and is skipped, so k never advances past 1.

Worked example

def remove_duplicates(nums):
    if not nums:
        return 0
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return k

b = [1, 1, 2]
k = remove_duplicates(b)
print(k, b[:k])

empty = []
print(remove_duplicates(empty))

all_dupes = [7, 7, 7]
k2 = remove_duplicates(all_dupes)
print(k2, all_dupes[:k2])

Output:

2 [1, 2]
0
1 [7]

The exact example from the question, [1, 1, 2], produces length 2 with the array beginning [1, 2], matching the question's stated expectation precisely. Both named edge cases behave as described: empty input returns 0, and an all-duplicates array of three sevens collapses to length 1.

Trade-offs and pitfalls

The most common bug here is comparing against nums[i-1] rather than nums[k-1]. For this exact short example the two happen to coincide (no run is longer than two), which is precisely why this bug can pass a small hand-traced example and still be wrong in general: always verify against a duplicate run of length three or more before trusting the comparison target. A second pitfall is treating "new length" and "final array length" as the same thing; the array keeps its original size, only the prefix up to the returned length is meaningful. A third is over-engineering with a hash set or a fresh output list, which works but spends O(n) extra space the problem does not need and explicitly asks you to avoid.