Lyft Full-Stack Developer Interview Preparation Guide - Mid Level

Direct answer

Use two pointers: a slow "write" pointer k marking the end of the deduplicated prefix built so far, and a fast "read" pointer scanning forward. Because the array is sorted, any duplicate of the last kept value is guaranteed to sit immediately next to it, so you only ever need to compare each new element against the single most recently kept value, not the whole prefix. This does the whole job in one O(n) pass using only two integer indices, O(1) extra space, while modifying the input array in place.

Structured elaboration

Why sortedness makes O(1) space possible

If the array were unsorted, detecting a duplicate would require remembering every distinct value seen so far, typically with a hash set, which costs O(n) extra space. Sortedness collapses that requirement: every occurrence of a given value is contiguous, so "have I already kept this value" reduces to "does it equal the last value I kept", a single comparison against nums[k - 1].

The two-pointer mechanics

Start k = 1 (the first element is always kept, since there is nothing before it to compare against). For each i from 1 to the end, if nums[i] differs from nums[k - 1] (the last kept value), copy nums[i] into nums[k] and increment k. If it matches, skip it: i keeps advancing but k does not. At the end, k is the new length, and nums[0:k] holds the deduplicated values in place; positions from k onward still hold leftover old values and are considered out of bounds by the problem's contract.

Edge cases named in the question

An empty array has nothing to deduplicate; the correct new length is 0, and the loop body never executes since there is no index 1 to start from, so this falls out of the algorithm naturally as long as the initial k = 1 step is guarded by an emptiness check first (index 0 does not exist to keep otherwise). An array that is all duplicates (for example, four copies of the same value) should collapse to length 1, since only the very first occurrence is ever compared against and kept, and every subsequent element matches nums[k-1] and is skipped.

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

a = [0, 0, 1, 1, 1, 2, 3, 3]
k = remove_duplicates(a)
print(a[:k], k)

empty = []
print(remove_duplicates(empty))

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

Output:

[0, 1, 2, 3] 4
0
[5] 1

The general array [0, 0, 1, 1, 1, 2, 3, 3] deduplicates to [0, 1, 2, 3] with new length 4. The empty-array edge case correctly returns length 0 without error. The all-duplicates edge case correctly collapses to length 1, keeping only the single value 5.

Trade-offs and pitfalls

The most common mistake is comparing nums[i] against nums[i - 1] instead of against nums[k - 1], the last KEPT value. Those two only coincide when no elements have been skipped yet, so this bug silently produces wrong results as soon as any duplicate run is longer than two. A second mistake is forgetting the empty-array guard and indexing nums[0] on an assumed non-empty array, which crashes on empty input. A third is allocating a new list or using a hash set out of habit, which passes the O(n) time requirement but violates the O(1) extra space requirement the question explicitly asks for; that approach is the right one for an UNSORTED array, but is unnecessary overhead here. The same two-pointer technique is identical in C, Java, or Kotlin, since it only relies on equality comparison and array indexing, nothing Python-specific.

Direct answer
Coaching a genuine underperformer starts with diagnosing why (skill gap, unclear expectations, motivation, or something outside work like a health or personal issue) before assuming it's a will problem, then moving to a private, honest conversation with specific examples, a written and time-bound improvement plan with objective checkpoints, and a clear, stated understanding of what happens if the bar still isn't met. The hard part isn't the first conversation, it's staying honest and consistent through every checkpoint after it.

Structured elaboration

Diagnose before you coach

Below-the-bar performance has different root causes that call for different responses:

• Skill gap: they don't yet know how to do the thing. Response: targeted teaching, pairing, smaller scoped tasks.
• Unclear expectations: they don't know what "good" looks like here. Response: make the bar explicit and concrete, with examples.
• Motivation or engagement: they can do it but aren't. Response: a more direct conversation about what's changed and why.
• Something outside work: a health issue, a personal crisis, burnout. A private, non-judgmental check-in on wellbeing belongs early in this process, both because it's the right thing to do and because it changes what the right intervention is (support and possibly a formal accommodation, not a performance plan).

Getting this wrong (coaching a skill gap like it's a motivation problem, or the reverse) wastes the improvement window on the wrong intervention.

The conversation and the plan

• Deliver the message privately, plainly, and with specific examples: what's below the bar, what the bar actually is, and why it matters.
• Put the plan in writing: two or three concrete, observable goals, a defined timeframe, and what evidence would count as "met."
• Set a regular check-in cadence shorter than your normal 1:1 rhythm; below-the-bar performance needs tighter feedback loops, not the same cadence as everyone else.

When to involve HR formally

This is a judgment call many candidates get wrong by either never mentioning HR (naive) or looping HR in immediately (overcautious, and it can undermine trust). A reasonable line: loop in HR or your manager as soon as the conversation could plausibly lead to a formal employment outcome (a documented warning, or separation), even if you're optimistic it won't get there, because that's exactly when documentation and process need to be right from the start rather than reconstructed after the fact.

Protecting the team

The rest of the team usually already knows something is off; silence reads as either denial or unfairness. Without disclosing private performance details, it's reasonable to acknowledge you're aware of the gap and are addressing it, and to be transparent about redistributing work if needed, so the team doesn't quietly conclude the issue is being ignored.

Worked example

Situation

An engineer on a team I was supporting had been reliably strong for over a year, then their output quality and delivery reliability dropped off sharply over a couple of months: reviews were taking longer, deadlines were slipping, and the pattern didn't match a normal bad sprint.

Diagnosis

Before assuming a motivation problem, I had a private, low-pressure conversation focused on checking in rather than accusing. That surfaced that part of the issue was a skill gap on a newer part of the codebase they'd been assigned to without much ramp-up, but there was also something going on outside work affecting their focus.

Action

We set a short, explicit improvement plan: two concrete, observable goals tied to real upcoming work, a shorter check-in cadence, and pairing time on the unfamiliar codebase area. I also made sure they knew about the option to talk to HR about support resources for the personal situation, kept separate from the performance conversation so the two didn't get conflated.

Result

Performance recovered within the plan's window once the skill gap closed and the external situation stabilized. Because the conversation started from genuine diagnosis rather than an assumption, the plan addressed the actual cause instead of just adding pressure, and the person stayed on the team and rebuilt trust with the group.

The other branch (when it doesn't turn around)

Not every case ends this way. When someone doesn't meet a documented plan's criteria despite real support, the path is a harder, well-documented conversation, formal HR involvement, and eventually separation if there's no path forward. The mentor's job at that point shifts from "close the gap" to making sure the process is fair, well-documented, and handled with dignity, and to being honest with the rest of the team (without violating privacy) that a change is coming so it doesn't land as a surprise.

Trade-offs & pitfalls

• Treating every case as a motivation problem. The single biggest junior mistake here is skipping diagnosis and going straight to "try harder" messaging, which fails skill-gap and external-cause cases and can be actively harmful if there's something like burnout or a health issue underneath.
• Involving HR too late (or too early). Too late, and you've lost the documentation trail that protects everyone, including the underperformer, if it does become formal. Too early or too visibly, and it can read as punitive before the person's had a real chance, damaging trust unnecessarily.
• Optimizing for the individual at the team's expense, or the reverse. A senior answer holds both: real support for the person, and honesty with the team about workload and timeline impact, rather than pretending nothing's happening.
• No exit criteria stated up front. A plan without a clear "what does not-met look like, and what happens then" isn't actually a plan, it's a delay, and it's unfair to the person because they don't know what they're actually being measured against.

Direct answer

Vertical scaling (scale up) gives one machine more resources: a bigger CPU, more RAM, faster disks. Horizontal scaling (scale out) adds more machines and spreads load across them. Vertical scaling is the faster first move because it needs no application changes; horizontal scaling is the one that actually removes a ceiling, because a single machine's capacity is always finite no matter how large you buy.

Structured elaboration

Vertical scaling: advantages

• Simplicity: resizing an instance or VM (virtual machine) usually requires no code or architecture change.
• Lower operational surface: one system to patch, back up, and monitor instead of a fleet.
• No distributed-systems tax: no partitioning, no cross-node consistency, no coordination overhead, so single-threaded or tightly-coupled workloads keep their natural performance profile.

Vertical scaling: disadvantages

• Hard ceiling: even the largest cloud instance sizes (high-memory or high-CPU tiers) top out, and that ceiling arrives faster than most teams expect.
• Single point of failure: one node down means the service is down, unless it is paired with a passive standby (a high-availability concern, not a scaling one).
• Non-linear cost: the largest instance tiers carry a steep price premium per unit of CPU/RAM versus a few mid-tier instances doing the same aggregate work.

Horizontal scaling: advantages

• No hard ceiling: capacity grows by adding nodes, which is why it is the pattern behind "web-scale" systems.
• Failure isolation: losing one node out of many degrades capacity slightly rather than taking the service down.
• Elastic cost matching: nodes can be added and removed to track demand, so spend tracks load instead of being sized for peak year-round.

Horizontal scaling: disadvantages

• Requires statelessness or externalized state: a node must be replaceable, which usually means a rewrite if the service was built assuming local state.
• Coordination overhead: partitioning, request routing, and (for data) replication or sharding all add moving parts that a single node never needed.
• Operational complexity: more instances to deploy, patch, and observe, plus the need for a load-distribution layer in front of them (a load-balancing concern, out of scope here, but worth naming as the piece that makes horizontal scaling actually work end to end).

Signals that vertical scaling has run out of road

Cloud-specific version of this decision. The same signals drive the same move on every major cloud, just through different primitives: on AWS you resize the EC2 instance type first, then hand scaling over to an Auto Scaling Group (ASG) that adds instances instead of resizing further; on Azure the equivalent fleet-level primitive is a VM Scale Set; on GCP it is a Managed Instance Group. All three exist because the same lesson applies everywhere: resizing is the cheap first lever, and a policy-driven fleet is the lever that removes the ceiling.

The often-missed factor: licensing. For commercial database or middleware software billed per-core or per-instance, vertical scaling can look artificially attractive on infrastructure cost while licensing cost scales the same way (or worse) as horizontal scaling would, once you account for per-node license fees across a fleet. Model total cost of ownership, not just the compute bill, before committing to either path.

Worked example

A checkout service starts on one 4 vCPU / 16 GB instance. Traffic doubles over two quarters. The team resizes to 8 vCPU / 32 GB (still vertical), which buys headroom for a while. CPU utilization is now steady at 78% during business hours and p99 latency has grown from 220 ms to 410 ms even after the resize, with no code regression identified. Disk and memory are not saturated; only CPU and tail latency are trending against the thresholds above. That combination, a saturated resource plus a latency SLO breach that resizing no longer fixes, is the signal to stop resizing and horizontally scale: put the service behind a fleet (ASG-equivalent) of smaller instances instead of chasing a bigger single one.

In practice, most teams do not choose purely one or the other. A common hybrid: keep the primary datastore vertically scaled as far as practical (since horizontally scaling stateful stores is the harder, sharding-level problem: splitting the data itself across nodes means picking a partition key, routing each query to the node that owns the relevant data, and rebalancing data when nodes are added or removed, none of which a stateless tier ever has to do), while horizontally scaling the stateless application tier in front of it, because the application tier is the cheaper piece to make replaceable first.

Trade-offs & pitfalls

• Resizing repeatedly without a plan for the ceiling is a common trap: teams keep buying the next instance size up until they hit the largest tier available, at which point the horizontal rewrite happens under emergency pressure instead of as a planned migration.
• Horizontal scaling only pays off if the service was made stateless or its state externalized first; bolting a load balancer in front of a stateful service without that groundwork just distributes the same single point of failure.
• Watch resource signals together, not in isolation: CPU can look fine while disk I/O or memory is the real ceiling, and treating the wrong resource as the bottleneck leads to buying the wrong upgrade.
• Cost is not a tie-breaker in only one direction: nonlinear pricing at the top of the vertical tier can push toward horizontal even before a technical ceiling is hit, and licensing cost can push the other way.

Answer (status codes with brief why)

1. Created new resource with valid data — 201 Created

• Indicates resource created; include Location header pointing to new resource and optionally return representation.

2. Successfully deleted and no body — 204 No Content

• Operation successful, nothing to return; avoids sending empty JSON.

3. Request accepted for async processing — 202 Accepted

• Request accepted but not completed yet; respond with info on status endpoint or Location for polling.

4. Syntactically valid JSON but fails semantic validation — 422 Unprocessable Entity

• Server understood syntax but semantic/business rules failed (e.g., invalid date range). Keeps 400 for generic bad request, but 422 is clearer for validation errors.

5. Creation conflicts with unique constraint — 409 Conflict

• Resource conflict (e.g., duplicate email). Optionally include details and link to existing resource.

6. Authentication required — 401 Unauthorized

• Client must authenticate (include WWW-Authenticate header). Use when no/invalid credentials.

7. Authenticated but not authorized — 403 Forbidden

• Credentials valid but user lacks permission to perform action.

Idempotency considerations

• GET, PUT, DELETE, HEAD, OPTIONS are idempotent: repeating them has same effect (PUT should replace resource, DELETE removes resource — repeated DELETEs can return 204 or 404 depending on design; prefer 204 to keep idempotence).
• POST is not idempotent: repeated POSTs can create duplicates; for safe retries implement idempotency keys (Idempotency-Key) or use PUT with client-generated id for create-if-not-exists.
• 202/201 interactions: for async POST, combine 202 with a status resource and support idempotency keys so retries don’t create duplicates.

Direct answer: Dijkstra's complexity depends entirely on the priority-queue implementation: $O(V^2)$ with a plain array, $O((V+E)\log V)$ with a binary heap, and $O(E + V \log V)$ with a Fibonacci heap (the theoretically best, rarely used in practice due to large constants). A* uses the same underlying machinery as Dijkstra but adds a heuristic $h(n)$ estimating remaining distance to the goal, which - if admissible (never overestimates) and consistent (satisfies a triangle-inequality-like property) - guarantees the optimal path is still found while typically exploring far fewer nodes than Dijkstra by prioritizing promising directions.

Structured elaboration

• Array-based Dijkstra: finding the minimum-distance unvisited vertex is an $O(V)$ scan, done $V$ times, giving $O(V^2)$ - reasonable for dense graphs where $E \approx V^2$ anyway.
• Binary-heap Dijkstra: each extract-min is $O(\log V)$, and each edge relaxation may trigger a decrease-key (also $O(\log V)$, or handled via re-insertion with lazy deletion in many implementations), giving $O((V+E)\log V)$ - the standard choice for sparse graphs.
• Fibonacci-heap Dijkstra: decrease-key is $O(1)$ amortized, so the bound improves to $O(E + V \log V)$ - asymptotically best, but the large constant factors and implementation complexity of Fibonacci heaps mean binary heaps usually win in practice except at very large scale.
• A*: identical algorithmic skeleton to Dijkstra, but the priority queue orders by $f(n) = g(n) + h(n)$ (cost-so-far plus heuristic estimate to goal) instead of just $g(n)$. An ADMISSIBLE heuristic (never overestimates true remaining cost) guarantees A* still finds the optimal path; a CONSISTENT heuristic (satisfies $h(n) \le \text{cost}(n, n') + h(n')$ for every edge) additionally guarantees no node needs to be re-expanded once popped, matching Dijkstra's efficiency guarantees while exploring fewer nodes in the common case, because the heuristic actively steers the search toward the goal instead of expanding uniformly outward in all directions.

Worked example

Consider road-network routing where straight-line (Euclidean) distance to the destination is used as $h(n)$: it's admissible (straight-line distance never overestimates actual road distance, which must be $\ge$ straight-line) and consistent (the triangle inequality holds for Euclidean distance). On a grid or road network, this heuristic causes A* to expand nodes roughly in an ellipse oriented toward the goal, rather than Dijkstra's expanding circle in all directions - for a goal far from the source, this concretely means A* explores a small fraction of the nodes Dijkstra would, even though both are guaranteed to find the same optimal-cost path.

Trade-offs & pitfalls

• A* is only as good as its heuristic - a poorly-chosen or non-admissible heuristic can make it explore MORE nodes than Dijkstra (if it misleads the search) or, worse, return a suboptimal path (if it's not admissible).
• When there's no useful domain-specific heuristic available (e.g. an abstract graph with no geometric embedding), A* degenerates to Dijkstra (using $h(n) = 0$ everywhere is trivially admissible and consistent).
• Fibonacci heaps are a common "textbook-optimal, practically-never-used" answer - know the asymptotic bound but be ready to say WHY binary heaps usually win in real systems (much smaller constant factors, simpler implementation, better cache behavior).

Direct answer

Don't start pulling data. Spend the first few minutes clarifying exactly what "freshest usage data" means to the requester, quickly check what's actually feasible in the time available, then offer a concrete option with an honest trade-off (what you can deliver, by when, and what limitations it has) instead of either refusing or silently guessing.

Structured elaboration

1. Clarify fast, in a few targeted questions. Which metric or entity, exactly? What time range and freshness actually matters for the demo (last five minutes, last hour, end of day)? What format and how many rows? Who's the audience? Two minutes here avoids delivering the wrong thing under time pressure.
2. Check feasibility before promising anything. Is there already a near-real-time source (a stream, a recent materialized view, meaning a pre-computed, saved query result that refreshes on a schedule so it's faster to read than running the full query live), or does this require querying the warehouse directly? A quick look at pipeline health tells you what's realistically possible in two hours.
3. Offer real alternatives with honest trade-offs, rather than a flat yes or no: a slightly-stale snapshot delivered fast, a live dashboard with a visible "data as of" timestamp, or a small representative sample if a full extract isn't feasible in time.
4. Set expectations explicitly and in writing. State exactly what you'll deliver, by when, and what its limitations are, and get an explicit "yes, that works" before you start, so the requester isn't surprised mid-demo.
5. Capture the request in a lightweight ticket or thread (what was asked, what was delivered, why) so a recurring need doesn't turn into repeated fire drills, and so the next urgent ask has a template to follow.

Worked example

A message comes in: "I need the freshest usage data for a demo in two hours." Instead of guessing, the reply is: "Which metric, exactly, active sessions or feature-level usage? And is a snapshot from an hour ago fresh enough, or does it need to be closer to real time?" The answer comes back: feature-level usage, an hour old is fine. A quick check shows the closest fast option is a query against yesterday's partition (a time-sliced chunk of the table, one day's worth of rows) plus this morning's incremental load (just the new rows added since the last full update), deliverable as a CSV in about 30 minutes, versus a true near-real-time pull that would need infrastructure support not available in two hours. The reply to the requester: "I can get you feature usage as of this morning in about 30 minutes. Sub-hour freshness isn't feasible in the time we have. Does the morning snapshot work for the demo?" Only after confirmation does the work start.

Trade-offs & pitfalls

• Pitfall: silently delivering whatever's easiest without confirming it matches what "fresh" means to the requester, then having it fail live in the demo.
• Pitfall: over-promising real-time freshness under pressure and missing the deadline entirely.
• Pitfall: treating the ask as one-off. If this is the third urgent demo-data request this month, that's a signal to build a lightweight self-serve or scheduled export, not just to keep responding faster each time.
• Senior differentiator: naming the trade-off explicitly and getting a quick confirmation before starting, instead of either refusing the ask outright or quietly doing extra unscoped work to make an unrealistic version happen.

Direct answer
When postmortem action items routinely go uncompleted, the fix is almost never 'try harder to remember them,' it's process and tooling that makes overdue items visible automatically, assigns real ownership, and periodically forces a decision (do it, reschedule it, or explicitly drop it) rather than letting items sit in limbo indefinitely.

Structured elaboration

• Every item gets a taxonomy, not just a description. Categorize each as a code change, a test, a runbook update, or a policy change; this matters because 'we fixed it' claims are easy to make vaguely but hard to fake once the category demands a specific, checkable artifact (a merged pull request, a passing test, an updated document link).
• Automated tracking, not manual follow-up. Integrate action items with the team's existing ticketing system rather than a document nobody revisits, and set up automatic escalation when an item passes its due date, for example flagging the owner's manager after a defined grace period.
• A regular review cadence. A recurring, lightweight review (monthly, say) of all open action items across recent postmortems, where each overdue item gets an explicit decision: still committed with a new date, explicitly deprioritized with a documented reason, or escalated because it's blocked.
• Tie urgency to real signal where relevant. For teams with formal reliability targets, an action item addressing a gap close to breaching its service-level objective or eating into an error budget should visibly outrank a lower-urgency item, rather than all items being treated as equally important by default.
• Verification, not just closure. An item marked 'done' should have some evidence attached (a passing test, a dashboard showing the metric improved), not just a status flip, since a false-positive 'closed' item is worse than an honestly still-open one.

Worked example
A team's postmortem tool shows 40% of action items are still open past their original due date, with no visibility into why. After the fix: items are tagged by type (12 code changes, 8 tests, 15 runbook updates, 5 policy changes), each syncs to the team's existing ticket tracker with an owner and due date, and any item 30 days overdue auto-escalates to the owner's manager with a link back to the original postmortem. A monthly 15-minute review meeting looks only at the overdue list, and each item gets one of three outcomes: recommitted with a new date, explicitly dropped with a one-line reason recorded (so it doesn't silently reappear as a mystery six months later), or flagged as blocked and escalated further. Within one quarter, the overdue rate drops from 40% to under 10%, not because engineers suddenly became more diligent, but because the system now makes an overdue item visible and forces a real decision instead of letting it fade quietly.

Trade-offs and pitfalls
The most common failure is adding tracking overhead without addressing WHY items go uncompleted in the first place, usually because they were never actually prioritized against regular roadmap work and got silently deprioritized without anyone saying so. Tracking makes that silent deprioritization visible, which is uncomfortable but necessary; the alternative is items that look committed on paper but were never really going to happen.

Direct answer

Keep a resizable array of the stored values plus a hash map from value to that value's index in the array. Insert appends to the array in O(1); getRandom picks a uniformly random array index in O(1); the trick is delete, which must not leave a gap: swap the removed value with the array's last element, update that moved element's index in the hash map, then pop the last slot off in O(1).

Structured elaboration

• values: an array of the currently stored values, with no gaps.
• index_of: hash map from value to its current position in values.

insert(val): if val is already in index_of, return false. Otherwise append it to values and record its index.

remove(val): if val is absent, return false. Otherwise look up its index, overwrite that slot with the array's last element (updating that moved element's entry in index_of to the vacated index), then pop the array's last slot and delete val from index_of. Because the moved element simply changes which index it lives at, and every array slot is always occupied by exactly one live value, no gap is ever created and no shifting of the remaining elements is needed.

getRandom(): choose a uniformly random integer index in [0, len(values)) and return values[that index]. Since each stored value occupies exactly one slot and slots are chosen uniformly, every value has equal probability of being returned.

The reason a plain hash set cannot support getRandom in O(1) is that hash tables give you no way to address "the k-th element" directly: you would need to walk buckets, which is not O(1) and not uniform once buckets have different chain lengths. The array gives you that direct O(1) addressing that a hash table structurally lacks.

Worked example

import random


class RandomizedSet:
    def __init__(self):
        self.index_of: dict[int, int] = {}
        self.values: list[int] = []

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_of:
            return False
        idx = self.index_of[val]
        last_val = self.values[-1]
        self.values[idx] = last_val
        self.index_of[last_val] = idx
        self.values.pop()
        del self.index_of[val]
        return True

    def get_random(self) -> int:
        return random.choice(self.values)


random.seed(42)
rs = RandomizedSet()
print(rs.insert(1))
print(rs.insert(2))
print(rs.insert(3))
print(rs.remove(2))     # swaps 3 into index 1
print(rs.values)
print(rs.get_random())
print(rs.get_random())

Running this (CPython's random module, seeded) prints:

True
True
True
True
[1, 3]
1
1

Key points

• The swap-with-last trick is what keeps delete O(1): it avoids shifting every element after the removed one.
• Uniformity comes from the array having no gaps: random.choice over indices is exactly a uniform choice over the stored values.

Complexity

for insert, remove, and getRandom; $O(n)$ space for the array and hash map together.

Edge cases

• Removing the last element in the array: the "swap with last" step is swapping an element with itself, which is harmless.
• getRandom on an empty structure has no valid answer; guard it explicitly (raise, or document as undefined behavior) rather than letting random.choice throw an unhandled exception on an empty list.

Trade-offs & pitfalls

The most common mistake is deleting by shifting all elements after the removed index, which is correct but O(n), defeating the point. A second common mistake is deleting by using values.remove(val) in Python, which internally does that same O(n) scan-and-shift. The design absorbs a lighter-weight sibling problem well: an insertion-order-preserving set (for example, deduplicating items in a shopping cart while keeping display order) uses the same "array plus hash map of positions" composition, but it cannot use the swap-with-last trick, because swapping would destroy the insertion order it is trying to preserve. That variant instead needs either a tombstone marker left in place (with periodic compaction) or a doubly linked list plus hash map (the same structure used for an LRU cache), trading away the O(1) swap-delete for order preservation.

Direct answer

A hash set gives O(1) average membership checks regardless of blacklist size, which is the right
choice for a high-query-rate service; a sorted array with binary search gives O(log n)
membership checks, slower per query but with better cache locality and much lower per-entry
memory overhead. The real deciding factor is usually update frequency: a hash set tolerates
frequent updates cheaply, while a sorted array's inserts require shifting elements and are
expensive at scale.

Structured elaboration

Membership test complexity. A hash set computes one hash and does O(1) average work to
confirm or deny membership, independent of how many entries are in the set. A sorted array with
binary search needs ceil(log2(n)) comparisons in the worst case; for n = 1{,}000{,}000
entries, that is 20 comparisons, small in absolute terms but structurally always growing (however
slowly) with blacklist size, unlike the hash set's flat cost.

Cache locality. Binary search on a sorted array has excellent locality in one specific sense:
the array itself is one contiguous block, so each individual access is cheap, though the ACCESS
PATTERN (jumping to the middle, then a quarter point, etc.) is not sequential and does not
prefetch as well as a straight linear scan would. A hash set's single lookup touches one (or a
handful of, under collision) location directly, without the multi-step probe pattern binary
search requires, at the cost of that location being determined by a hash rather than a
predictable arithmetic position.

Update costs, the real differentiator. Inserting a new id into a SORTED array requires
finding its position and shifting every element after that position by one slot to keep the array
sorted; for a mid-range insert into a million-element array, that means moving on the order of
half a million elements. Inserting into a hash set touches exactly one new slot (amortized,
ignoring occasional resizing) with no shifting at all. For a blacklist that is updated
frequently (new abusive users added continuously), this asymmetry usually dominates the decision
far more than the query-time gap between O(1) and O(log n).

When to prefer each, concretely for a backend service. Prefer a hash set when the blacklist
updates frequently and query volume is very high (the question's "thousands of queries per
second" scenario clearly favors this). Prefer a sorted array with binary search when the
blacklist is effectively static or updated in large infrequent batches (rebuild the sorted array
wholesale on each batch update rather than incrementally), AND you specifically need the array's
side benefits, such as efficient RANGE queries (all ids between X and Y) or a smaller, more
predictable memory footprint per entry, neither of which a hash set provides at all.

Worked example

import bisect

def counting_bisect_left(sorted_list, target, counter):
    lo, hi = 0, len(sorted_list)
    while lo < hi:
        mid = (lo + hi) // 2
        counter[0] += 1
        if sorted_list[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

n = 1_000_000
blacklist_sorted = [2 * i for i in range(n)]
blacklist_set = set(blacklist_sorted)

counter_hit = [0]
idx_hit = counting_bisect_left(blacklist_sorted, 500_000, counter_hit)
print("HIT comparisons:", counter_hit[0], "found:", blacklist_sorted[idx_hit] == 500_000)

counter_miss = [0]
idx_miss = counting_bisect_left(blacklist_sorted, 999_999_501, counter_miss)
found_miss = idx_miss < n and blacklist_sorted[idx_miss] == 999_999_501
print("MISS comparisons:", counter_miss[0], "found:", found_miss)

print("hash set: 500,000 in set ->", 500_000 in blacklist_set)
print("hash set: 999,999,501 in set ->", 999_999_501 in blacklist_set)

# Update cost: inserting a new odd id into the sorted array shifts everything after it
new_id = 1_000_001
pos = bisect.bisect_left(blacklist_sorted, new_id)
shifted = len(blacklist_sorted) - pos
blacklist_sorted.insert(pos, new_id)
print(f"inserting {new_id} into the sorted array shifts {shifted} existing elements")

before_size = len(blacklist_set)
blacklist_set.add(new_id)
print(f"hash set size before: {before_size}, after: {len(blacklist_set)} (one new entry, no shifting)")

Instrumenting binary search to count actual comparisons against a sorted array of 1,000,000 even
ids: a HIT lookup (id 500,000, present) takes 19 comparisons, and a MISS lookup (id 999,999,501,
an odd number genuinely absent from the array) also takes 19 comparisons, both within the
ceil(log2(1{,}000{,}000)) = 20 theoretical bound. A hash set confirms the same membership
answers for both queries (True and False respectively) in a single in check. For the update
cost: inserting a new odd id (1,000,001) into the middle of the sorted array requires shifting
499,999 existing elements to keep it sorted, while inserting the same id into the hash set
touches exactly 1 new entry, no shifting, directly demonstrating the update-cost asymmetry the
"structured elaboration" section describes.

Trade-offs and pitfalls

• Do not decide this purely on the O(1) vs O(log n) query gap. At realistic blacklist sizes,
  20 comparisons versus 1 hash lookup is rarely the bottleneck; update pattern is usually the
  deciding factor in practice.
• A sorted array shines for range queries ("give me every blacklisted id between X and Y"), a
  query shape a hash set cannot answer efficiently at all (it would require scanning every entry);
  if that capability is ever needed, it tips the decision toward the array (or a hybrid, keeping
  both).
• Batch-rebuilding a sorted array (collect updates, then rebuild the whole sorted array
  periodically) sidesteps the expensive per-insert shifting cost, if the update latency
  requirement tolerates a delay between when an id is added and when it takes effect.
• Per-entry memory overhead is usually lower for a plain sorted array of fixed-size values
  than for a hash set's backing table (which reserves extra capacity to keep its load factor
  low); at very large scale with a memory-constrained service, this can matter as much as the
  update-cost argument.

Direct answer

For data with a small hot subset that is written frequently (comments, upvotes), the right strategy depends on how immediately correct a read needs to be: invalidate-on-write for moderate freshness needs, write-through only where every read must reflect every write instantly, and accepting brief staleness (via a time-to-live, TTL, or lazy invalidation) wherever that is tolerable, since write-through on every single upvote would add real latency for a benefit most reads do not need.

Structured elaboration

• Invalidate-on-write: on each write, remove (or update) the cached entry; the next read repopulates it from the datastore. This keeps writes fast (no synchronous cache update required beyond the invalidation itself) while keeping reads correct after a very short window.
• Versioned keys: instead of invalidating, bump a version so the old cached entry simply becomes unreachable; useful when you want to avoid a race between a slow read repopulating the cache with a stale value right after an invalidation.
• Write-through and write-behind for hot writes: write-through keeps the cache always current but adds write latency to every single write, which is expensive when writes are frequent (like upvotes ticking constantly); write-behind trades durability for throughput, generally the wrong choice for anything users would notice being lost.
• Hybrid systems: a common pattern for a frequently-updated counter (like upvote count) is to accept brief staleness (a few seconds) via a short TTL or periodic flush of an in-memory increment buffer, rather than treating every single increment as needing to be immediately, individually visible; this dramatically reduces write amplification for high-frequency, low-individual-significance updates.
• Choosing per requirement: an "immediate consistency" requirement (the user must see their OWN comment appear instantly) can be satisfied narrowly (read-your-own-write for that specific user/action) without requiring every OTHER reader to see it with zero delay; distinguishing "the writer needs to see it now" from "everyone needs to see it now" often reveals a much cheaper design.

Worked example

An upvote counter incremented thousands of times per minute on a popular post: rather than invalidating the cached count on every single increment (which would defeat the cache's purpose under this write rate), buffer increments in a fast in-memory or Redis atomic counter and periodically (e.g., every 1 to 2 seconds) reconcile that buffered delta with the durable count, giving readers a count that is at most 1 to 2 seconds behind reality, an acceptable trade for a number nobody expects to be exactly, instantaneously precise.

Trade-offs and pitfalls

Applying write-through uniformly to a hot-write field "to be safe" can quietly become the write path's latency bottleneck as write frequency grows; revisit the choice as traffic patterns change, not just at initial design time. Buffering writes for periodic reconciliation must have a bounded, monitored flush interval; an unbounded or silently-stalled buffer turns "briefly stale" into "indefinitely wrong.