Time and Space Complexity Analysis Questions

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: Count-Min Sketch (CMS) maintains a small 2D array of counters, updating $d$ counters per item in O(d) time and answering frequency-estimate queries in O(d) time with a one-sided error (estimates are always >= true frequency, never under-count) bounded by the sketch's width; Misra-Gries maintains at most $k$ candidate (item, counter) pairs directly, guaranteeing it finds every item whose true frequency exceeds $N/(k+1)$ (where N is stream length) with no false positives among items reported, at the cost of a coarser, more discrete accuracy profile than CMS's tunable probabilistic guarantee.

Structured elaboration

• Count-Min Sketch: a $d \times w$ array of counters, plus $d$ independent hash functions (one per row). On update, increment the counter at position (row, hash_row(item) mod w) for each of the $d$ rows. On query, return the MINIMUM of the $d$ counters the item hashes to (taking the min mitigates the effect of any single row's hash collisions inflating the count). Update and query are both $O(d)$. Space is $O(d \times w)$, independent of the number of distinct items - a genuinely sublinear structure.
• Misra-Gries: maintain up to $k$ (item, count) slots. On a new item: if it's already tracked, increment its counter; if there's a free slot, add it with counter 1; if all $k$ slots are full and the item isn't tracked, DECREMENT every tracked counter by 1, removing any that hit zero. This "decrement all" step is what bounds memory to $O(k)$ regardless of stream length, while guaranteeing any item with TRUE frequency above $N/(k+1)$ survives to the end (since it can be decremented at most $N/(k+1)$ times before appearing again, by pigeonhole).
• The key qualitative difference: CMS gives a frequency ESTIMATE for any item you query (with bounded overestimate error), useful when you want approximate counts for arbitrary items; Misra-Gries gives a CANDIDATE SET of "possibly heavy" items with a hard combinatorial guarantee about which heavy items it cannot miss, but items below the $N/(k+1)$ threshold get no guarantee at all (they may or may not survive).

Worked example

For a stream of $N = 10^8$ events with $k=1000$ Misra-Gries slots: any item whose true frequency exceeds $N/(k+1) \approx 99{,}900$ (about 0.0999% of the stream) is GUARANTEED to be among the surviving tracked items at the end - a hard combinatorial guarantee, not probabilistic. A Count-Min Sketch sized with $d=5$ hash rows and $w=2000$ columns (10,000 total counters, comparable memory to Misra-Gries's 1000 slots but organized differently) instead gives, for ANY queried item, an estimate guaranteed to overestimate the true count by at most $\epsilon N$ with probability $1-\delta$, where $\epsilon$ and $\delta$ are functions of $w$ and $d$ respectively - a tunable PROBABILISTIC bound applicable to every item, not just a guaranteed-surviving heavy-hitter set.

Trade-offs & pitfalls

• Misra-Gries's guarantee is combinatorial and exact (about WHICH heavy items survive), which some engineers find easier to reason about than CMS's probabilistic error bound - but Misra-Gries gives you no frequency estimate at all for items outside its surviving set, while CMS can answer a frequency query for literally any item, heavy or not.
• CMS's one-sided error (always overestimates, never underestimates) is a deliberate, useful property for some applications (e.g. rate-limiting decisions where erring toward "this looks like more traffic than it is" is the safe direction) - know that the error is one-directional, not symmetric.
• Both structures' accuracy depends on the chosen size parameters ($k$ for Misra-Gries; $d, w$ for CMS) relative to your actual traffic skew - a highly skewed distribution (a few items dominating) is handled comfortably by modest sizes in both structures; a near-uniform distribution with no true "heavy hitters" makes both structures' outputs less useful (there's nothing skewed to detect).

Direct answer: Materializing (precomputing and storing) aggregated results trades ongoing memory footprint and update-maintenance cost for consistently low read latency; computing on demand trades away that low, predictable read latency for zero memory overhead and always-fresh results. The crossover depends on read frequency versus update frequency: high read-to-write ratios favor materialization, high write-to-read ratios (or a hard freshness requirement) favor on-demand computation.

Structured elaboration

A cost/benefit model for materializing a per-customer aggregate to serve a <100ms dashboard requirement:

• Memory cost: O(number of distinct customers x aggregate size) held continuously, whether or not any given customer's dashboard is currently being viewed.
• Update cost: every time a raw event arrives that affects an aggregate, the materialized value must be updated (incrementally, ideally O(1) per event rather than recomputing the whole aggregate from scratch) - this is ongoing background work proportional to write volume, not read volume.
• Read cost saved: instead of scanning potentially large volumes of raw events on every dashboard load (which could easily exceed the 100ms budget as event volume grows), a materialized read is O(1) - a direct lookup.

On-demand computation instead pays the full aggregation cost on every read (proportional to however much raw data underlies that customer's metrics), which is fine if reads are rare, but becomes the bottleneck if reads are frequent or the raw-data volume per customer is large.

Worked example

Suppose a customer generates 10,000 raw events per day, and their dashboard is viewed 3 times per day. On-demand computation processing 10,000 events per read x 3 reads = 30,000 units of read-time work per day, and zero standing memory. Materializing costs 10,000 units of incremental-update work per day (one O(1)-ish update per event as it arrives) PLUS the standing memory to hold the aggregate, but reads become essentially free (O(1) x 3 = negligible). Here, materializing wins on total work (10,000 vs 30,000 "units") AND on read latency - but if the dashboard were viewed only once a MONTH instead of 3 times a day, on-demand computation's total work would be far lower (10,000 x 30 days = 300,000 raw events accumulated, computed once, versus materializing paying the 10,000-events-per-day update cost regardless of whether anyone ever looks at the dashboard) - the crossover is a straightforward function of the read-to-write ratio.

Trade-offs & pitfalls

• The <100ms latency REQUIREMENT itself is often the deciding factor independent of the read/write ratio calculus above - if on-demand computation simply cannot hit the latency budget once raw-data volume grows past a certain point, materialization becomes mandatory regardless of how the cost math otherwise nets out.
• Materialization needs a concrete UPDATE strategy (incremental update on each event vs periodic batch recomputation) - incremental is cheaper per-event but harder to get exactly right (must handle out-of-order events, corrections/retractions); periodic batch is simpler but introduces a staleness window bounded by the batch interval.
• A hybrid approach (materialize a coarse, cheap-to-update aggregate, and only compute the expensive precise version on-demand for the rare case that needs exact freshness) is a common real-world compromise worth naming when neither pure approach cleanly wins.

Approach: For an in-memory buffer holding the last N items with fast append and eviction, compare three choices: a plain Python list used with append/pop(0), a collections.deque, and a fixed-size ring buffer (circular array). list.pop(0) is O(n) (must shift every remaining element), making a plain list the wrong choice for this use case; deque gives O(1) append/pop from both ends via a doubly-linked block structure; a hand-rolled ring buffer gives O(1) append/overwrite using a single fixed-size array and a wrapping index, with the tightest memory footprint of the three (no per-node overhead, unlike a linked structure).

class RingBuffer:
    def __init__(self, capacity):
        self.capacity = capacity
        self.buf = [None] * capacity
        self.start = 0   # index of oldest element
        self.count = 0

    def append(self, item):
        idx = (self.start + self.count) % self.capacity
        if self.count < self.capacity:
            self.buf[idx] = item
            self.count += 1
        else:
            self.buf[idx] = item
            self.start = (self.start + 1) % self.capacity  # overwrite oldest, advance start

    def to_list(self):
        return [self.buf[(self.start + i) % self.capacity] for i in range(self.count)]

Key points: list.append is O(1) amortized (as established in the dynamic-array survivors), but list.pop(0) (removing the oldest element to enforce a max size) is O(n), since every remaining element must shift down one index - this makes a plain list a poor fit despite append being cheap. deque (a doubly-linked list of fixed-size blocks internally) gives O(1) on both append and popleft, making deque(maxlen=N) a simple, correct, O(1)-per-operation solution with minimal code. A hand-rolled ring buffer matches deque's O(1) per-operation cost but avoids per-node/per-block overhead entirely, using one contiguous fixed-size array - the tightest memory footprint, at the cost of writing (and correctly reasoning about) the wraparound index arithmetic yourself.

Complexity: All three: O(1) time for the "cheap" operations they're each designed for (list: append only; deque and ring buffer: both append and evict). Space: list and deque are O(N) with some per-element/per-node overhead; ring buffer is O(N) with the tightest possible constant (one fixed-size array, no growth/shrink logic once created).

Edge cases: buffer not yet full (ring buffer's count < capacity branch correctly avoids advancing start prematurely); capacity 1 (degenerates correctly to always overwriting the single slot); requesting the buffer's contents in insertion order (the to_list method above correctly unwraps starting from start, not from index 0).

Worked example / execution verification

rb = RingBuffer(3)
for x in [1, 2, 3, 4, 5]:
    rb.append(x)
    print(x, "->", rb.to_list())

Executed: output is 1 -> [1], 2 -> [1, 2], 3 -> [1, 2, 3], 4 -> [2, 3, 4], 5 -> [3, 4, 5] - confirming the buffer correctly holds only the most recent 3 items at all times, evicting the oldest on each overflow, exactly matching deque(maxlen=3)'s behavior (verified separately: deque([1,2,3,4,5], maxlen=3) produces deque([3, 4, 5]), the identical final state).

Trade-offs & pitfalls

• For nearly all practical purposes, collections.deque(maxlen=N) is the right default choice - it's a well-tested standard-library structure with the correct O(1) guarantees, and hand-rolling a ring buffer is rarely worth the added code and bug surface unless you have a specific, measured reason (extremely tight memory constraints, or needing direct array-like indexing that deque doesn't efficiently support).
• A ring buffer does give O(1) RANDOM-ACCESS indexing (via the wraparound arithmetic) more cheaply than a deque's internal block structure in some implementations - if you need frequent indexed access INTO the buffer (not just append/evict at the ends), that's a genuine reason to prefer the array-backed ring buffer.
• Never use list.pop(0) in a hot path for this use case - it's a common, easy-to-miss performance bug, since list.append alone looks fine in isolation but pairing it with pop(0) for eviction silently reintroduces O(n) cost per operation.

Direct answer: Cache locality means accessing memory in a pattern that keeps the CPU's cache lines full of USEFUL data, rather than repeatedly evicting and re-fetching from slower main memory. Two algorithms with identical Big-O complexity can differ by an order of magnitude or more in real performance purely based on whether their memory access pattern is sequential (cache-friendly) or scattered (cache-hostile) - array-of-structures (AoS) versus structure-of-arrays (SoA) is the canonical example.

Structured elaboration

• Array-of-structures (AoS): each record is stored as one contiguous struct ({id, name, score}), and an array of records places these structs one after another. Iterating over ALL records to read every field is cache-friendly (sequential access), but iterating to read just ONE field (say, score) across millions of records means the CPU loads an entire cache line's worth of struct data (including id and name, which you don't need right now) for every few records - wasting cache bandwidth on unused fields.
• Structure-of-arrays (SoA): each FIELD gets its own contiguous array (ids[], names[], scores[]). Iterating over just scores[] for a computation touches only relevant, densely-packed data - every byte loaded into cache is useful, and the CPU's hardware prefetcher can predict the purely-sequential access pattern far more effectively.
• The underlying mechanism: modern CPUs fetch memory in cache-line-sized chunks (commonly 64 bytes) and a cache miss (data not already in a fast cache) costs roughly 100-200x more cycles than a cache hit - so an access pattern that wastes cache-line capacity on unneeded data multiplies your effective memory traffic without changing the algorithm's Big-O class at all.

Worked example

Consider iterating over 10 million records, each with 4 fields (16 bytes total per struct: an 8-byte double score plus 8 bytes of other fields), summing only the score field:

• AoS: each cache line (64 bytes) holds 4 full structs, but only 8 of every 16 bytes per struct (the score) is useful - roughly 50% of loaded cache-line bytes are wasted on this specific access pattern (worse if there are more unrelated fields per struct).
• SoA: the scores array alone is fully packed doubles - every byte loaded into a cache line is a score value actually being summed, 100% cache-line utilization for this access pattern.

Both approaches are $\Theta(n)$ time to sum n scores - identical Big-O - but the SoA layout does meaningfully less total memory traffic for this specific operation (bounded above by the wasted-byte fraction in the AoS case), which running an actual benchmark on representative hardware would show as a real, reproducible, and often substantial (multi-x) wall-clock difference, growing with how many "irrelevant" fields sit alongside the one you're actually scanning.

Trade-offs & pitfalls

• SoA is not universally better - if your access pattern typically touches MULTIPLE fields of the SAME record together (e.g. "for this specific user, get id, name, and score all at once"), AoS's locality-per-record wins instead, since SoA would scatter that lookup across three separate arrays.
• The right layout is a function of your DOMINANT access pattern, not a universal rule - profile the actual query/iteration shape before choosing, and be aware that a system serving mixed access patterns may need both layouts (or a hybrid) for different code paths.
• This is exactly the kind of gap that "Big-O is not the whole performance story" is pointing at - a correct complexity analysis (both are Theta(n)) is necessary but not sufficient for predicting real-world performance; memory-layout awareness is the complementary skill.