Microsoft Software Engineer (Junior Level) Interview Preparation Guide

Direct answer: BFS visits nodes level-by-level outward from the source (using a queue), while DFS plunges as deep as possible along one path before backtracking (using a stack, explicit or via recursion). Both are $O(V + E)$ time on an adjacency list; on an adjacency matrix both become $O(V^2)$ because checking each vertex's neighbors costs $O(V)$ regardless of actual edge count. Space differs: BFS's queue can hold up to $O(V)$ nodes at the widest level, while DFS's stack depth is at most $O(V)$ in the worst case (a long path) but often much less for a bushy, shallow graph.

Structured elaboration

• BFS: typically implemented with a queue and a visited-set; explores all neighbors of the current frontier before moving to the next level. Naturally finds the SHORTEST path (by edge count) in an unweighted graph, because it discovers nodes in strictly increasing distance order from the source.
• DFS: typically implemented with an explicit stack or recursion (which uses the call stack implicitly); explores one branch fully before backtracking. Naturally suited to problems about structure/connectivity - detecting cycles, topological sorting, finding connected components - because it naturally tracks the "path so far."
• On an adjacency list, both visit each vertex once ($O(V)$) and traverse each edge once (or twice for undirected graphs) ($O(E)$), giving $O(V+E)$.
• On an adjacency matrix, finding a vertex's neighbors means scanning its entire row, $O(V)$ per vertex regardless of how many edges actually exist, giving $O(V^2)$ total - the representation choice materially changes the complexity class for sparse graphs.

Worked example

For a sparse graph like a social-network friend graph (say $V = 10^6$ users, average degree $d = 100$, so $E \approx 5 \times 10^7$ for an undirected graph): adjacency-list BFS/DFS costs $O(V+E) \approx 5.1 \times 10^7$ operations. The same traversal on an adjacency matrix would cost $O(V^2) = 10^{12}$ operations - a roughly 20,000x blowup, entirely from the representation choice, not the algorithm. This is why adjacency lists are the default for real-world sparse graphs, and adjacency matrices are reserved for dense graphs or when O(1) edge-existence lookup is specifically needed.

Trade-offs & pitfalls

• BFS is the right choice for shortest-path-in-unweighted-graph and "closest/nearest" queries; DFS is the right choice for exhaustive exploration, cycle detection, and topological ordering.
• DFS's recursive implementation risks stack overflow on deep graphs (a long chain); an explicit-stack iterative version avoids this at the cost of slightly more code.
• Don't default to adjacency matrix out of habit - for any graph where $E \ll V^2$ (the common case), it wastes both time and $O(V^2)$ memory versus an adjacency list's $O(V+E)$.

Direct answer

The strongest version of this story shows you naming a specific, bounded ask, more scope, a stretch project, training time, or mentorship, at a moment when your team had competing priorities, framing it so your manager could see it didn't come at the team's expense, and following up with a lightweight recurring structure so the ask didn't have to be repeated as a one-off plea every time.

Structured elaboration

Set up the tension honestly. Say what your team was actually juggling at the time, so the ask reads as considered rather than oblivious to it.

Describe how you framed the ask to respect that priority. A bounded scope or timeframe, offering to hand off part of your current load, or tying the ask to something that also served the team's near-term goal.

Describe the actual conversation. What you opened with, how your manager responded, any negotiation that happened.

Describe the outcome honestly, including if it was partial or delayed, and what you learned about raising this kind of ask going forward.

Show the proactive companion to a one-off ask. Turning advocacy into a standing habit rather than a single event, for example proposing a recurring 30-minute check-in with your manager structured as a quarterly one-on-one (1:1) agenda, covering current strengths, a specific ask, and a follow-up on the previous one. This shows the same competency applied as a system, not just a moment.

Worked example

"My team was in the middle of a heavy delivery quarter when I recognized I hadn't had exposure to a kind of project I wanted to grow into. Instead of raising it as an open-ended I want more, I picked a specific, small piece of upcoming work that fit that growth area and proposed taking it on for that quarter only, offering to hand off one of my existing recurring responsibilities to a teammate who had capacity. My manager was hesitant given the team's workload, so we agreed to a trial, I'd take the piece of work for a few weeks and we'd check whether it was actually adding load before committing further. It worked, and by the end of the quarter I had a concrete example to point to. After that, rather than waiting for the next time I wanted something, I proposed a recurring 30-minute check-in with my manager, structured as a quarterly one-on-one agenda: what I'd learned since the last one, one specific ask for the coming quarter, and a check on the previous ask. That turned advocacy from something I had to work up the nerve for into a normal part of how we worked together."

Trade-offs & pitfalls

• Raising a growth ask with no regard for team timing reads as self-interested regardless of how reasonable the ask is. The fix isn't waiting forever, it's framing the timing and scope explicitly.
• Making the ask too vague, I want to grow, gives your manager nothing concrete to say yes to. A bounded, specific ask is far easier to approve.
• Treating advocacy as a single dramatic conversation rather than a recurring habit means every ask has to relitigate the relationship from scratch.
• Be honest in the story if the outcome was a partial yes or a not now. A story where everything goes perfectly on the first try reads as less credible than one with a believable negotiation in it.

Direct answer

Tracking visited state is what turns a graph traversal from something that can loop forever on a cycle into something guaranteed to terminate; the choice of mechanism (in-memory set, color marking, parent pointers, persisted marking, bitsets, or a probabilistic structure) is really a trade between memory footprint, durability across restarts, and concurrency safety, not a correctness choice, since any of them is correct if applied consistently.

Structured elaboration

In-memory visited set (a hash set of node ids). O(1) expected membership checks, simplest to reason about. Cost: memory grows linearly with the number of visited nodes, and everything is lost if the process crashes mid-traversal.

Color marking (white, gray, black), the classic depth-first search bookkeeping. White means undiscovered, gray means discovered but its subtree is still being explored, black means fully finished. This is strictly more informative than a plain visited set: a gray node currently on the call stack signals "in progress," which is exactly what lets you detect a back edge (an edge into a gray node) and therefore a cycle. A plain boolean visited set cannot distinguish "in progress" from "finished," so it cannot support cycle detection on its own.

Parent pointers. A small map from each node to the node that discovered it. Adds only O(1) extra state per node but enables reconstructing the actual path (not just "was this reachable"), which a bare visited set cannot do.

Persisted marking (a database column or table). Trades speed for durability: a traversal can survive a process crash and resume, and multiple worker processes can share visited state. The cost is added latency per check (a round trip instead of a hash lookup) and the need for transactional or optimistic-concurrency semantics so two workers do not both claim the same unvisited node and duplicate work, or worse, disagree about which one "owns" it.

Bitsets. One bit per node id, extremely compact and cache-friendly when node ids are dense integers in a known range. Poor fit when ids are sparse, non-integer, or the range is unknown ahead of time, since you either waste space over-allocating for the theoretical max id or need an id-to-index remapping layer.

Probabilistic structures (Bloom filters). A Bloom filter answers "have I possibly seen this node" with no false negatives but a tunable false-positive rate; it uses far less memory than an exact set for large node counts. The trade is real: a false positive means the traversal SKIPS a node it has not actually visited yet, silently under-exploring the graph. This is only acceptable when occasional missed nodes are tolerable (for example, an approximate reachability estimate) or when a Bloom-filter "maybe visited" result is always followed by a cheap authoritative check before being trusted.

Worked example

Consider a backend service that persists a large dependency graph in a relational database and needs to run reachability queries against it. Three concrete options, same graph, different constraints:

• Ad hoc single request, small subgraph: in-memory hash set. The traversal starts and finishes within one request; there is nothing to persist and nothing to coordinate.
• Long-running batch traversal over millions of nodes, must survive a deploy or crash: persisted marking, a visited_at timestamp column updated via an atomic compare-and-set ("claim this node if visited_at IS NULL"), so a restarted worker picks up exactly where an earlier one stopped, and two concurrent workers cannot both claim the same node.
• Interactive approximate "is this node probably already covered" check across a huge, mostly-static graph, where an occasional false positive is acceptable and always followed by a real check before acting on it: a Bloom filter sized for the expected node count and a target false-positive rate (say 1%), rebuilt periodically as the graph changes.

Trade-offs and pitfalls

• In-memory vs. persisted is fundamentally a durability and sharing trade, not a speed trade alone: in-memory is faster per check but confined to one process and ephemeral; persisted is durable and shareable across workers but every check now costs a network or disk round trip unless you layer a cache in front.
• Concurrency for persisted visited state needs an explicit protocol, not just "check then write": two workers checking the same unvisited node at nearly the same time can both decide to process it unless the claim step is atomic (compare-and-set, a lease with expiry, or a distributed lock). Idempotent processing (safe to redo a node's work if a duplicate claim slips through) is a cheaper fix than perfect locking in many systems.
• Common mistake: using a plain visited set when the actual requirement is cycle DETECTION, not just termination; a set alone tells you "seen before," not "currently on the path back to me," which is the distinction color marking exists to capture.
• Common mistake: reaching for a Bloom filter as a default memory optimization without checking whether the algorithm can tolerate its false positives; silently skipping a not-yet-visited node is a correctness bug, not a performance one, in most traversal use cases.
• Hybrid approach worth naming: keep an in-memory cache of the hot frontier (nodes actively being expanded) backed by periodic checkpoints to persisted storage; this gets most of the speed of in-memory tracking with a bounded amount of resumability if the process dies.

Direct answer
A closure is a function bundled together with references to the variables from its enclosing scope that it uses, captured by reference (not by value), so it keeps seeing the CURRENT value of those variables even after the enclosing function has returned. That captured reference can create a reference cycle, which is why a closure or callback can keep an object alive longer than you expect.

Structured elaboration

• What gets captured: a closure captures the variable itself (technically, the enclosing scope's cell), not a snapshot of its value at creation time. Two closures created from the same enclosing call share independent state; two closures created from the SAME variable in a loop share the same captured cell, which is the classic 'all my callbacks report the same, final loop value' bug.
• Why closures can leak memory: a closure keeps a live reference to everything it captures for as long as the closure itself is reachable. If you then store that closure back onto an object it captured (a callback registered on the very object it was built from), you've created object -> closure -> object, a reference cycle.
• Why reference counting alone can't free a cycle: CPython's primary memory management is reference counting, an object is freed the instant its reference count hits zero. In a cycle, each object holds a reference to the other, so neither one's count ever reaches zero on its own, even after nothing OUTSIDE the cycle references either of them. This is precisely why CPython also runs a separate cyclic garbage collector (gc module) that periodically looks for groups of objects that reference each other but are unreachable from anywhere else, and frees them as a group.
• Mitigation strategies: avoid storing a closure back onto the object it captures when you can restructure to avoid it; use weakref for a back-reference that shouldn't keep the target alive (a common pattern for observer/callback registries); or simply trust the cyclic collector for genuinely short-lived cycles and only investigate further if profiling shows real, growing retention in a long-running process.

Worked example

class Node:
    def __init__(self, name):
        self.name = name
        self.on_event = None

def wire(node):
    def handler():                 # closure: captures `node`
        return f"{node.name} handled"
    node.on_event = handler        # node -> handler -> node : a cycle
    return handler

Verified by running it with gc.disable() and a weakref to the node: after del n (dropping the only external reference), the node is STILL alive (ref() is not None is True) because the cycle keeps both objects' reference counts above zero. Re-enabling the collector and calling gc.collect() reclaims it (ref() is None becomes True immediately after), confirming the cyclic collector, not reference counting, is what actually frees this pattern.

Trade-offs & pitfalls
In a long-running service, this usually shows up as slow, steady memory growth rather than an obvious crash, because the cyclic collector DOES eventually run and free most cycles; the real danger is cycles involving objects with a __del__ method (historically these were UNCOLLECTABLE by the cyclic GC before Python 3.4, and even post-3.4 they add real collection overhead) or large cycles that make each collection pass more expensive as the live object graph grows. The fix is rarely 'stop using closures', it's to be deliberate about back-references specifically, using weakref where a callback registry would otherwise hold the only thing keeping a large object graph alive.

Direct answer

A squad-autonomy model, small, cross-functional, semi-independent teams, as popularized by Spotify's own engineering culture writeups (though by Spotify's own later account, only partially realized in practice), shifts goal-setting from top-down assigned targets toward squads proposing their own goals against a shared mission, which means tracking progress and escalating risk both depend much more on voluntary, structured transparency than on a manager simply reviewing a task list, so you'd adopt lightweight rituals that make that transparency happen by default rather than by exception.

Structured elaboration

• Goal-setting shift: instead of "here is your quarterly plan," squads typically align to a broader shared mission and then define their own concrete goals within it, which requires real upfront investment in making sure that mission is genuinely well understood, or squads quietly drift apart.
• Progress-tracking shift: without a single central plan to check against, you rely on regular, structured squad-level updates visible across the wider group rather than a manager independently knowing status, turning tracking into a broadcast problem rather than a manager-checks-in problem.
• Risk-escalation shift: since squads are meant to self-manage, honest early escalation only works if raising a risk isn't punished, otherwise autonomy quietly turns into siloed teams hiding problems until they become unavoidable.
• Cross-squad coordination: initiatives spanning multiple squads need an explicit, lightweight coordination mechanism, since no single manager owns all the relevant squads, commonly a cross-squad sync for a shared concern, or a designated point person per squad for a specific initiative.

Two concrete rituals worth adopting or adjusting:

1. A regular, short cross-squad demo where each squad shows real, working progress to the wider group rather than a status slide, making progress visible without a central tracker and surfacing overlapping or conflicting work early.
2. A lightweight risk check built into each squad's own retro or planning ritual, where the squad explicitly states anything at risk of missing its own goal as a short written note shared upward, so risk surfaces without someone above the squad having to go dig for it.

Worked example

Coordinating a cross-squad initiative like a new checkout flow that touches a Payments squad and a Fulfillment squad. Instead of a shared manager assigning tasks to both, you'd set up a short biweekly cross-squad sync focused only on the shared interface between the two squads' work, and each squad would flag in its own retro anything at risk of slipping that would affect the other squad, rather than waiting for a status meeting to surface it.

Trade-offs and pitfalls

The most common misreading of this model is that it means no accountability. In a well-functioning version, accountability shifts from "did you follow the plan I gave you" to "did you deliver on the goal you committed to, and did you raise it honestly if you couldn't," which is a real, sometimes harder form of accountability, not an absence of one. It's also worth being honest that Spotify itself has said in later retrospectives that the model as commonly described was more aspirational than a rigid blueprint fully implemented at any single point in time, so lean on the underlying principles, autonomy paired with alignment and transparency, rather than treating any one named ritual as a rulebook to copy exactly.

Direct answer

I treat learning time as scheduled, protected work rather than whatever's left over after everything else, and I lean toward topics adjacent to what I'm already delivering, so practice and delivery reinforce each other instead of competing for the same hours.

Structured elaboration

Protecting the time honestly: I keep a short, fixed block a few mornings a week, and I'm upfront, including with myself, that an incident-heavy week will eat into it; pretending the block is untouchable just sets up a plan that quietly fails the first time reality intrudes.

Choosing adjacent topics: picking something close to active work means reading directly feeds a task already on the plan, rather than living in parallel to delivery and never getting reinforced, which is usually how learning quietly evaporates.

Learning through the work, not just around it: where possible, I'd rather pick up something new by applying it to a real, if small, piece of committed work than by studying it in isolation first.

Making the trade-off visible: I state it explicitly, in planning or in a one-on-one, that a specific block of time is going toward this, rather than absorbing it as invisible unpaid effort that nobody accounted for and that quietly gets deprioritized under pressure.

A realistic weekly allocation: most weeks it's a modest, fixed slice of time split across delivery, reactive or on-call work, and study, and I say so plainly rather than implying I've found extra hours nobody else has.

Closing the loop: the test that it actually worked is a specific, nameable change in how I do the day job within a defined window afterward, not just a feeling of having learned something.

Worked example

During a stretch with unusually heavy delivery load, I kept two short mornings a week protected for structured logging and observability practices, a topic adjacent to the backend feature work I was already shipping. In an incident-heavy week, that block got sacrificed, and I said so in my next one-on-one rather than pretending it hadn't happened. Because the topic was chosen to reinforce active work, the reading fed directly into a task already on my plan, and within about a month I had changed one specific thing about how I approached that class of work: I started adding structured, searchable log fields to every new endpoint by default, instead of only adding ad hoc debug statements after something broke. The next two incidents on my services got diagnosed from those logs alone, without needing a live debugging session, which is the concrete result, not just a vague sense of having grown.

Trade-offs and pitfalls

The most common failure is scheduling learning time that never survives contact with the first busy week, because it was never actually protected or visible to anyone else who could help defend it. The other is picking topics so disconnected from current work that they never get reinforced by anything real, and quietly evaporate within a few weeks.

1. Brief explanation of why I chose the simple approach

• Reasoning: "With the time constraints and unclear edge cases early on, I implemented the straightforward O(n²) solution to produce correct, testable behavior quickly. That lets me validate assumptions and cover basic cases before optimizing."
• Sample language to interviewer: "I chose the simpler approach first so I could get a working solution and validate inputs/outputs quickly. It helps me avoid subtle bugs that can hide in a more complex algorithm."

2. Outline the optimization plan clearly

• High-level plan: "I can replace the quadratic step with an O(n log n) approach by [algorithm idea — e.g., sorting + two-pointer, using a balanced BST, or divide-and-conquer]. Steps: (1) swap the inner loop for a sort or tree structure; (2) adapt existing checks to work on sorted data; (3) run through examples and add unit tests. Estimated time: 8–12 minutes to sketch and 15–25 to fully implement depending on edge cases."
• Sample language: "Optimizing would require sorting the array O(n log n) then using two pointers to achieve the desired property in linear time post-sort. I’ll preserve current correctness checks and reuse helper functions."

3. Decide whether to attempt optimization now

• Decision criteria: remaining time, test coverage, interviewer signals, difficulty to implement bug-free.
• If >6 minutes and confident: "I have about 9 minutes left; I can implement the optimized version’s core loop and run a couple quick tests. I’ll outline edge-case handling verbally if I run out of time."
• If <6 minutes or risky: "Given ~4 minutes left, I’ll not fully re-implement. Instead I’ll explain the exact transformation I’d make, write pseudocode for the key part, and point to where tests and boundary checks fit. Would you like me to code the optimized core or walk through the plan?"
• Balance statement: "I prefer shipping correct, tested code first, but I’ll demonstrate understanding of the optimal approach by sketching implementation and trade-offs if time prevents full coding."

Time/Trade-offs to mention: correctness vs. optimality, maintainability, and testability.

Direct answer

Process the iterator in fixed-size chunks and accumulate counts into a single running hash map (a Counter) that lives for the whole run, rather than ever materializing the full token sequence as a list. Peak memory becomes proportional to the chunk size plus the number of distinct tokens (not the total number of tokens processed), which is exactly what "cannot keep all tokens in memory simultaneously" requires. For scale beyond a single machine's memory even for the running counts themselves, the same idea extends outward: spill partial counts to disk or a database and merge them, or hand the aggregation to an external tool built for exactly this.

Structured elaboration

Why a single running counter, not per-chunk lists, is the key move. The chunk size controls how many raw tokens are held at once, but the thing that actually needs to survive across chunks is the aggregate count, not the raw tokens themselves. A Counter accumulated with .update(chunk) after each chunk keeps memory bounded by the chunk size (transient) plus the number of distinct tokens seen so far (persistent, but typically far smaller than the total token count for realistic text), which is the same "count of distinct values, not count of total values" property that makes hash-map-based counting memory-efficient in general.

Code patterns for the streaming read itself. In Python, this looks like iterating the source with for chunk in iterator_of_chunks: ... rather than list(iterator) up front; if the source is a file, pandas.read_csv(path, chunksize=N) or a plain line-by-line file read serves the same purpose, only ever holding one chunk in memory. The point is structural: never call an operation that forces the entire stream to materialize (a bare list(...), a sort() over the whole thing, or a pandas.concat of every chunk) before counting.

External tools for when even the running counts don't fit, or true big-data scale is needed. A few standard building blocks, worth naming by name since the question explicitly asks for external tools:

• The classic Unix pipeline sort tokens.txt | uniq -c performs exactly this kind of streaming aggregation using external (disk-backed) sort, which is how shell tooling has solved "count occurrences in a file too big for memory" for decades.
• A disk-backed key-value store (Python's shelve or dbm modules, or a lightweight embedded database like SQLite) can hold the running counts on disk instead of in a Python dict, trading memory for disk I/O when even the distinct-token count is too large to fit in RAM.
• For a genuinely distributed, multi-machine scale, a framework like Apache Spark or Dask expresses the same map-then-reduce shape (count within each partition, then merge partition-level counts) across a cluster instead of a single process's chunks.

Scoping the "at massive scale" framing honestly. For inputs that must merely avoid holding everything in memory AT ONCE on one machine (the question's actual framing), chunked accumulation into one running Counter is sufficient and is the answer worth leading with. Approximate, sub-linear-memory structures (like a Count-Min Sketch, which trades exact counts for a small, fixed memory footprint with bounded overcounting error) exist for the harder case of needing frequency estimates over a token universe too large even to enumerate distinctly, but designing such a structure is its own topic (owned by the hashing-and-hash-tables domain, not this one); it is worth naming as the next tier of solution if pressed, without building one here.

Worked example

Full runnable code with a pinned random seed and pinned parameters, comparing the chunked streaming approach against materializing the whole stream (the latter only possible here because the demo stream is deliberately small; this is exactly the comparison the chunked approach exists to avoid needing at real scale):

import random
from collections import Counter

random.seed(42)  # pinned so a reviewer re-running this gets the same stream

VOCAB = [f"tok{i}" for i in range(20)]  # small closed vocabulary for a reproducible demo


def token_stream(n_tokens):
    """Simulates a stream too large to hold in memory as a list: a generator
    that yields one token at a time, pinned by the seed above."""
    for _ in range(n_tokens):
        yield random.choice(VOCAB)


def chunked_frequency_count(stream, chunk_size):
    """Bounded-memory frequency counting: accumulate counts in a single
    running Counter (O(vocabulary size) memory, not O(stream length)),
    processing the stream in fixed-size chunks so peak memory never holds
    more than `chunk_size` raw tokens plus the running counter at once."""
    running_counts = Counter()
    chunk = []
    chunks_processed = 0
    for tok in stream:
        chunk.append(tok)
        if len(chunk) == chunk_size:
            running_counts.update(chunk)
            chunk.clear()
            chunks_processed += 1
    if chunk:
        running_counts.update(chunk)
        chunks_processed += 1
    return running_counts, chunks_processed


if __name__ == "__main__":
    n_tokens = 10_000
    chunk_size = 500

    random.seed(42)
    ground_truth = Counter(token_stream(n_tokens))

    random.seed(42)
    chunked_result, n_chunks = chunked_frequency_count(token_stream(n_tokens), chunk_size)

    print(f"n_tokens={n_tokens} chunk_size={chunk_size} chunks_processed={n_chunks}")
    print("chunked result matches ground truth:", chunked_result == ground_truth)
    print("peak resident tokens per chunk (bounded):", chunk_size, "vs full stream:", n_tokens)
    print("top 5 by frequency (chunked):", chunked_result.most_common(5))
    print("top 5 by frequency (ground truth):", ground_truth.most_common(5))

Output (actual run):

n_tokens=10000 chunk_size=500 chunks_processed=20
chunked result matches ground truth: True
peak resident tokens per chunk (bounded): 500 vs full stream: 10000
top 5 by frequency (chunked): [('tok14', 533), ('tok2', 525), ('tok4', 523), ('tok15', 523), ('tok17', 515)]
top 5 by frequency (ground truth): [('tok14', 533), ('tok2', 525), ('tok4', 523), ('tok15', 523), ('tok17', 515)]

With n_tokens=10,000 and chunk_size=500, only 20 chunks of 500 raw tokens each were ever held at once, yet the chunked result is bit-for-bit identical to counting the entire materialized stream at once (both random-seeded identically for a fair comparison), which is exactly the property that justifies using the chunked approach instead of the simpler materialize-then-count version at real scale.

Trade-offs and pitfalls

• Materializing the full stream first (list(iterator) then Counter(...)) is simpler to write and was used above only as a ground-truth cross-check; it is precisely what the question rules out, since it requires holding every token in memory at once.
• The running Counter itself still grows with the number of DISTINCT tokens seen, not the total count; if the vocabulary itself is unbounded or extremely large (arbitrary user-generated strings rather than a fixed token vocabulary), the running counter can itself become the memory bottleneck, which is exactly where spilling partial counts to disk or reaching for an approximate structure becomes necessary rather than optional.
• Choosing a chunk size is a real tuning knob: too small and the per-chunk overhead (function calls, dict updates) dominates; too large and peak memory creeps back up toward the full-stream size. The right answer depends on available memory and token size, and naming this trade-off explicitly (rather than picking an arbitrary chunk size and moving on) is part of a complete answer.
• External sort-based tools like sort | uniq -c guarantee correctness regardless of scale but at the cost of an O(n log n) sort rather than the O(n) a hash-based running count achieves; they are the right choice specifically when memory (not time) is the binding constraint, or when the tool is already part of an existing pipeline.
• Approximate structures (Count-Min Sketch and similar) trade exact counts for fixed memory and bounded error; naming that this trade-off exists is appropriate depth for this question, but designing the structure itself belongs to a different topic.

Direct answer
Off-by-one bugs in C cluster into three recurring shapes: indexing one element past a buffer's valid range, using the wrong relational operator (<= where < is correct, or the reverse) as a loop bound, and sizing a buffer from strlen() while forgetting it excludes the terminating null byte. All three are silent right up until the wrong byte happens to matter, so catching them before release needs boundary-focused unit tests plus a memory-safety sanitizer, not code review by inspection.

Structured elaboration
For an array of n elements, the valid indices are 0 through n-1. Every pattern below is a different way of accidentally touching index n:

• Reading/writing one past the end: a helper that wants "the last element" and writes arr[n] instead of arr[n-1], or a fill loop that writes one extra element beyond the buffer it was given.
• Incorrect <= vs < boundary: a loop written as for (i = 0; i <= n; i++) instead of i < n. This is the single most common root cause of pattern 1 in practice: someone mentally reads "process n elements" as "count up to and including n" instead of "count up to but excluding n".
• Improper use of strlen(): strlen(s) returns the number of characters in a C string, NOT counting the terminating '\0' byte. Allocating exactly strlen(s) bytes and then calling strcpy() (which always writes the terminator) overflows the allocation by exactly one byte.

Worked example (executed under AddressSanitizer and UndefinedBehaviorSanitizer)

Pattern 1: reading one past the end

/* BUG: valid indices are 0..n-1, so arr[n] is one past the end */
int last_element_buggy(const int *arr, int n) {
    return arr[n];
}
/* FIX: the last valid index is n-1 */
int last_element_fixed(const int *arr, int n) {
    return arr[n - 1];
}

Compiling the buggy version with clang -g -fsanitize=address,undefined and running it against a 5-element array produced:

==...==ERROR: AddressSanitizer: stack-buffer-overflow ... READ of size 4 ...
    #0 ... in last_element_buggy bug1_write_oob_buggy.c:6
SUMMARY: AddressSanitizer: stack-buffer-overflow bug1_write_oob_buggy.c:6 in last_element_buggy

The fixed version compiled and ran identically (same sanitizer flags) and exited 0, printing last=50 with no diagnostic.

Pattern 2: incorrect <= vs < loop boundary

/* BUG: i <= n reads arr[n], one element past the valid range 0..n-1 */
int sum_array_buggy(const int *arr, int n) {
    int sum = 0;
    for (int i = 0; i <= n; i++) sum += arr[i];
    return sum;
}
/* FIX: i < n visits exactly the valid indices */
int sum_array_fixed(const int *arr, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    return sum;
}

The buggy version, run the same way, produced the same class of diagnostic (AddressSanitizer: stack-buffer-overflow ... sum_array_buggy bug2_loop_boundary_buggy.c:8); the fixed version exited 0 and printed sum=15 for {1,2,3,4,5}.

Pattern 3: improper use of strlen()

/* BUG: strlen() excludes the '\0', so this buffer is one byte too small */
char *dup_string_buggy(const char *s) {
    char *out = malloc(strlen(s));
    strcpy(out, s);
    return out;
}
/* FIX: allocate strlen(s) + 1 bytes for the terminator */
char *dup_string_fixed(const char *s) {
    char *out = malloc(strlen(s) + 1);
    strcpy(out, s);
    return out;
}

Running the buggy version against "hello" produced:

==...==ERROR: AddressSanitizer: heap-buffer-overflow ... WRITE of size 6 ...
    #0 ... in strcpy+0x...
    #1 ... in dup_string_buggy bug3_strlen_buggy.c:10
0x... is located 0 bytes after 5-byte region ...
SUMMARY: AddressSanitizer: heap-buffer-overflow bug3_strlen_buggy.c:10 in dup_string_buggy

The fixed version exited 0 and printed copy=hello.

Catching these before release

• Unit tests focused on boundary inputs, not just "typical" ones: for any function parameterized by a count n, test n = 0, n = 1, and n = the buffer's exact declared size, since a mid-range input for n frequently never exercises the off-by-one at all. Run that suite under AddressSanitizer and UndefinedBehaviorSanitizer (-fsanitize=address,undefined) so an out-of-bounds access that happens not to crash on its own still gets flagged deterministically, as shown above. When recompiling with sanitizers isn't an option (for example, testing a pre-built third-party binary), Valgrind's memcheck tool provides equivalent detection at the cost of much slower execution.
• Static analysis, which finds these patterns without ever running the code: compiler warnings (-Wall -Wextra, plus -Warray-bounds on both GCC and Clang, and GCC's -Wstringop-overflow specifically for the strlen()/strcpy() sizing pattern), and a dedicated static analyzer such as cppcheck or clang-tidy, both of which flag off-by-one loop bounds and the malloc(strlen(s))-without-+1 pattern directly in source, before compilation even needs sanitizer instrumentation.

Trade-offs & pitfalls
A sanitizer only catches a bug on the code PATH it actually executes, so a test suite with high line coverage but no boundary-focused inputs can still miss all three patterns, since a "normal" mid-range input for n will typically never touch the exact off-by-one boundary; coverage percentage and boundary coverage are different things. Static analyzers trade off false positives (flagging safe code, which trains engineers to start ignoring their output) against false negatives on pointer arithmetic that crosses function boundaries, so neither tool alone is sufficient; the combination (static analysis pre-commit, sanitizer-instrumented tests in the pipeline) covers more than either does alone. A common wrong turn after finding one of these bugs is fixing it locally without adding a regression test pinned to the exact boundary that triggered it, so a later refactor can silently reintroduce the same off-by-one with nothing to catch it.

Direct answer
Put the ask, the essential context, and the next step in the first two sentences, so a busy reader can act on the email even if they only read the opening before deciding whether to reply now or later.

Structured elaboration

1. State the ask as the first sentence, not buried after several paragraphs of context: "I'd like to request temporary access to X" or "Could you approve Y by Thursday?"
2. Give only the essential context, one or two sentences of why this ask exists, not the full backstory. Include it because it makes the ask easier to say yes to quickly, not because it's interesting.
3. State the next step explicitly: what you need them to do, and by when, so they don't have to infer the deadline or the required action.
4. Use the subject line to state the ask, not just the topic: "Approval needed by Thursday: Q3 budget line" tells the reader more than "Budget question."
5. Keep the whole email short. If the request genuinely needs more context, put the essential ask up top and the detail below it, rather than making the reader wade through detail to find the ask.

Worked example
Subject: "Access request: prod DB read access, needed by Wednesday"

Body: "Could you grant me temporary read access to the orders table in prod? I'm investigating a customer-reported data discrepancy (ticket #4821) and need to check actual row values, which I can't do in staging since the issue only reproduces with real production data. Happy to have this access time-boxed to a few days and revoked afterward if that's easier to approve."

The ask (temporary read access) and the deadline context (needed by Wednesday) are in the subject line alone; the body confirms the specific ask, gives the minimum context needed to approve it, and proactively offers a constraint (time-boxed) that makes approval easier.

Trade-offs and pitfalls

• Leading with a long justification before the ask is the single most common failure; a reader has to hold the whole paragraph in their head waiting to find out what you actually want.
• Too little context can also fail: an ask with zero justification can force the reader to ask a clarifying question back, which is slower than including the one sentence of context that would have let them approve it immediately.
• For sensitive or high-stakes asks (a large budget approval, access to something risky), a slightly longer, more carefully justified email is worth the extra length; the "front-load the ask" principle still applies, it just means front-loading a well-justified ask rather than skipping justification entirely.