Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

"In-place" and "$O(1)$ extra space" are usually used interchangeably to mean an algorithm transforms its input using only a constant amount of auxiliary memory beyond the input and output themselves. Recursion complicates that accounting: every recursive call adds a stack frame (its arguments, local variables, and a return address), so a recursive function that touches no second array or list can still use $O(n)$ extra memory through the call stack alone, memory that is easy to forget because it never shows up as an explicit variable in the code.

Structured elaboration

What counts as "extra" space

The convention is to count space beyond the input and the required output. A function that reverses an array by swapping elements in the same array is $O(1)$ extra space by this convention, even though the array itself is $O(n)$, because that space was already accounted for as the input. Auxiliary structures the algorithm allocates on top of that, a second array, a hash map, or the call stack, are what get charged against the space bound.

How recursion hides space in the call stack

Each recursive call is not free: the runtime pushes a new stack frame holding that call's parameters and local variables, and does not pop it until the call returns. A recursive function with depth d therefore uses $O(d)$ stack space regardless of what its explicit variables look like. For a tree of height h, naive recursion is $O(h)$ stack space, which is $O(\log n)$ for a balanced tree but $O(n)$ for a completely skewed one; for a straightforward recursive Fibonacci, the recursion depth (and thus stack space) is $O(n)$ even though each individual call only holds a couple of integers.

Three ways to convert hidden stack space into genuine O(1) space

1. Threading (Morris traversal): temporarily rewrite null-looking child pointers to point back up the tree, walk using those threads instead of recursing, then restore the original structure. No stack, no recursion, just pointer rewrites.
2. Iterative looping with an accumulator: replace a linear recursion (like naive Fibonacci) with a loop carrying only the last one or two values needed, discarding everything else.
3. Recurse on the smaller side, loop on the larger (tail-call style elimination): for divide-and-conquer algorithms like quicksort, always making the recursive call on the smaller partition bounds the recursion depth by $O(\log n)$ even in the worst case, because the smaller side can be at most half the remaining size at each level.

Worked example

# 1) Morris inorder traversal: O(1) extra space, no recursion, no explicit stack
def morris_inorder(root):
    out = []
    cur = root
    while cur:
        if not cur.left:
            out.append(cur.val)
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur:
                pred = pred.right
            if not pred.right:
                pred.right = cur          # thread to come back later
                cur = cur.left
            else:
                pred.right = None         # remove the thread, tree restored
                out.append(cur.val)
                cur = cur.right
    return out

# 2) Iterative Fibonacci: O(1) extra space, versus O(n) recursion-stack depth for the naive recursive version
def fib(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 3) Quicksort: recurse on the smaller partition, loop on the larger, bounding stack depth to O(log n)
def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    while lo < hi:
        p = partition(arr, lo, hi)
        if p - lo < hi - p:
            quicksort(arr, lo, p - 1)
            lo = p + 1
        else:
            quicksort(arr, p + 1, hi)
            hi = p - 1

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

n = {v: Node(v) for v in range(1, 8)}
n[4].left, n[4].right = n[2], n[6]
n[2].left, n[2].right = n[1], n[3]
n[6].left, n[6].right = n[5], n[7]

print(morris_inorder(n[4]))
print([fib(i) for i in range(10)])

import random
random.seed(5)
original = [random.randint(0, 100) for _ in range(50)]
arr = original[:]
quicksort(arr)
print("quicksort matches sorted():", arr == sorted(original))

Running this prints the Morris traversal [1, 2, 3, 4, 5, 6, 7] (the tree's inorder sequence, confirming the temporary threads were fully removed and the structure is intact), the Fibonacci sequence [0, 1, 1, 2, 3, 5, 8, 13, 21, 34], and quicksort matches sorted(): True, confirming the in-place quicksort produces the same order as Python's own sorted() on the same seeded input.

Key points

• Morris traversal never recurses and never allocates an explicit stack, it reuses the tree's own null pointers as temporary bookkeeping, then undoes that bookkeeping before moving on.
• The iterative Fibonacci keeps exactly two rolling values (a, b) instead of a call stack that grows with n.
• "Recurse smaller, loop larger" is not just a performance tweak, it is what guarantees the quicksort recursion depth is $O(\log n)$ even on adversarial input, since the recursive branch always operates on a piece at most half the current size.

Complexity notes

Morris traversal: $O(n)$ time (each edge is traversed a bounded number of times to set up and tear down threads), $O(1)$ extra space. Naive recursive Fibonacci: $O(2^n)$ time and $O(n)$ stack space (depth n); the iterative version is $O(n)$ time and $O(1)$ space. Naive quicksort recursion: $O(n)$ worst-case stack depth (already-sorted input recursing on the full remaining range each time); recursing on the smaller side bounds it to $O(\log n)$ worst case.

Trade-offs & pitfalls

A recursive solution that "looks" $O(1)$ space because it declares no arrays is a common trap, always ask separately what the maximum recursion depth is and whether the language or runtime performs tail-call optimization (most mainstream production runtimes, including CPython, do not, so a "tail recursive" Python function still accumulates real stack frames). Morris traversal trades a temporary, carefully-undone mutation of the tree's own pointers for the stack savings, which is a real complexity cost in the code even though the asymptotic space bound improves, and it is unsafe on a tree that might be read concurrently while being traversed, since the tree is briefly in a modified state.

Direct answer

Reach for a hash map whenever you need the fastest average lookup, insert, and delete and do not care about the order keys come out in. Reach for an ordered structure (a balanced binary search tree, BST for short, meaning a tree kept balanced so its height stays logarithmic; or a skip list, a linked structure with multiple randomly-built "express lane" levels that gives logarithmic search without needing tree rebalancing) whenever you need range queries, sorted iteration, or predecessor/successor lookups, since a hash map fundamentally cannot answer those without scanning every entry.

Structured elaboration

Concrete case where a hash map wins: an in-memory cache keyed by an exact request signature, for example caching a computed response by its full input hash, where every lookup is "does this exact key exist" and there is no notion of "keys near this one" that would ever be queried. The $O(1)$ average lookup directly minimizes latency, and there is nothing to give up, since ordering was never needed.

Concrete case where giving up hash-map speed pays off: a scheduler that needs "the next event after this timestamp." That is a successor query, unsupported by a hash map without scanning every key, but native to an ordered structure in $O(\log n)$. Trading average-case $O(1)$ for guaranteed $O(\log n)$ is a clear win here because the operation the hash map cannot do at all is the operation the system needs on every scheduling step.

Trade-offs & pitfalls

A hash map's worst-case degrades to $O(n)$ under pathological collisions, though modern implementations mitigate this with randomized hash seeding; an ordered structure's $O(\log n)$ is a hard guarantee regardless of key distribution, which matters if an adversary can influence which keys get inserted (for example, in a public-facing API). A common mistake is reaching for an ordered structure "just in case sorted output is needed later," which pays the $O(\log n)$ tax on every single operation for a benefit that may never be used; the right trigger is a concrete, recurring range or predecessor/successor query in the actual access pattern, not a hypothetical one. It is also common to forget that some hash map implementations preserve insertion order as an incidental property (not a sorted, comparison-based order), which is a much weaker guarantee than a true ordered structure's ability to iterate or range-query by key value.

Direct answer

For a boolean flag (or a small set of category memberships) tracked across millions of entities, a bitset (one bit per entity per flag, packed into a flat array of machine words) beats a hash set of member IDs on both memory and multi-flag query cost whenever a meaningful fraction of entities actually carry the flag. A hash set only wins when the flag is genuinely sparse, since its memory scales with the number of members, not the population size.

Structured elaboration

Bitset representation: N entities need $N/8$ bytes flat (1 bit per entity), addressed directly by entity index. "Has flag A and flag B" becomes a single bitwise AND across the two byte arrays, one machine word at a time (e.g. 64 bits = 64 entities per instruction) - the work is O(N) bits total, but with a tiny constant factor, since it's pure word-parallel ALU work with no hashing and no pointer chasing.

Hash set representation: only the entities WITH the flag are stored, each as (say) an 8-byte id plus hashing/bucket overhead; a reasonably tuned open-addressing set needs load-factor slack and per-slot metadata on top of the raw id, so assume roughly 24 bytes per entry all-in as an illustrative estimate. Total memory is then $k \cdot b$ where k is the member count and b the per-entry byte cost, independent of N. "A and B" becomes an intersection of two hash sets: O(min(|A|, |B|)) hash lookups into the larger set - cheap when both sets are small, but each lookup costs a hash computation and a probe, not a single ALU instruction.

Break-even point:

Sparse middle ground: compressed bitmap formats (such as Roaring bitmaps) adaptively switch between array, bitmap, and run-length containers per chunk of the index range, approaching hash-set-sized memory when a flag is sparse and raw-bitset speed when it's dense, at the cost of extra implementation complexity and a small per-operation overhead versus a flat bitset.

The same idea, one level down (folding the game-engine collision-layer case): a per-entity collision-layer bitmask (up to 64 layers) is the identical idea with the axes swapped. Instead of one bitmap spanning the whole population for each flag, each individual entity carries its own fixed-width integer, where a single 64-bit word covers up to 64 category bits, and two entities' membership overlap becomes one AND across those two words, rather than a hash lookup on either side.

Worked example

Plugging concrete numbers into the break-even formula above:

N = 100_000_000       # total entities
b = 24                 # assumed bytes per hash-set entry (8-byte id + ~16 bytes overhead)

bitset_bytes = N / 8
breakeven_k = bitset_bytes / b
breakeven_fraction = breakeven_k / N

print(f"bitset size: {bitset_bytes:,.0f} bytes")
print(f"breakeven k (members): {breakeven_k:,.0f}")
print(f"breakeven fraction of N: {breakeven_fraction:.6f} ({breakeven_fraction*100:.4f}%)")

Output:

bitset size: 12,500,000 bytes
breakeven k (members): 520,833
breakeven fraction of N: 0.005208 (0.5208%)

So with these assumptions, a hash set is smaller only while fewer than about 0.52% of the 100 million entities carry the flag; past that density, the flat bitset is both smaller AND cheaper to query.

The per-entity collision-mask version of the same idea:

LAYER_PLAYER = 1 << 0
LAYER_ENEMY = 1 << 1
LAYER_TERRAIN = 1 << 2

entity_mask = LAYER_PLAYER | LAYER_TERRAIN
other_mask = LAYER_ENEMY | LAYER_TERRAIN

collides = (entity_mask & other_mask) != 0  # shares the "terrain" layer bit
print("collision check (shared layer bit set):", collides)

Output:

collision check (shared layer bit set): True

Whether the "many entities x few flags" bitset lives on the population axis (feature flags) or the "one entity x many categories" bitmask lives on the per-object axis (collision layers), the payoff is the same O(1) word-parallel membership or overlap test instead of a hash lookup.

Trade-offs & pitfalls

• A bitset needs entities to have small, dense, stable integer indices; if entity IDs are sparse (e.g. UUIDs), you need an id-to-dense-index table regardless, which itself costs memory a hash set skips.
• Bitset updates (flip a flag) are O(1) but require already knowing the entity's index; hash set add/remove is also O(1) average, with a higher constant cost from hashing and resize amortization.
• Iterating "give me every entity with flag A" requires a bit-scan over the bitset (fast, but not free); a hash set hands you the member list directly at no extra cost.
• Reaching for a hash set out of habit on a flag that is actually dense (say 40% of entities) wastes memory relative to a bitset AND makes multi-flag boolean queries meaningfully slower.
• Compressed bitmaps trade a little per-operation overhead for adapting automatically across the sparse/dense spectrum, which pays off once you have many flags of very different densities rather than hand-picking bitset vs. hash set per flag.

Direct answer

Store only the timestamps that currently fall inside the window in a deque (a double-ended queue supporting O(1) push and pop from both ends), rather than recomputing a count from the full event history. Each new event is appended to the back; each query pops expired timestamps off the front until only in-window events remain, then reports the deque's length.

Structured elaboration

Approach

• A plain running total can be incremented on arrival, but it has no way to know which additions have aged out of the last W seconds, so it can only grow, never correctly shrink.
• Keeping only the timestamps inside the window, instead of a total, turns "is this event still relevant" and "how many are relevant" into deque operations: pop from the front while the oldest entries are older than the window allows, then read the length.
• Because timestamps only ever arrive in non-decreasing order, once an entry is popped off the front for being too old, it never needs to be looked at again. Each entry is pushed exactly once and popped at most once over its whole lifetime in the structure.

from collections import deque


class WindowCounter:
    def __init__(self, window_seconds):
        self.window = window_seconds
        self.q = deque()  # event timestamps currently inside the window, oldest first

    def record(self, t):
        """Record an event at time t. Timestamps must arrive non-decreasing."""
        self.q.append(t)

    def count(self, now):
        """Return how many recorded events fall in (now - window, now]."""
        cutoff = now - self.window
        while self.q and self.q[0] <= cutoff:
            self.q.popleft()
        return len(self.q)

Key points

• deque gives O(1) append and popleft, unlike a plain list where popping the front is O(n).
• The "pop expired from the front" step, run on every record or query, is what keeps memory bounded to just the events inside the window.
• This only works because input timestamps are non-decreasing; out-of-order arrivals would need a different structure.

Worked example

window_seconds = 10, recording and querying at the same moment as each event arrives, in order [0, 3, 5, 9, 12, 15]:

wc = WindowCounter(window_seconds=10)
for t in [0, 3, 5, 9, 12, 15]:
    wc.record(t)
    print(f"t={t}: count={wc.count(t)}")

prints:

t=0: count=1
t=3: count=2
t=5: count=3
t=9: count=4
t=12: count=4
t=15: count=3

At t = 12, the cutoff is 12 - 10 = 2, so the timestamp 0 (which is <= 2) is popped, leaving {3, 5, 9, 12}, a count of 4. At t = 15, the cutoff is 5, so timestamps 3 and 5 (both <= 5) are popped, leaving {9, 12, 15}, a count of 3.

Trade-offs & pitfalls

Complexity

Time: amortized $O(1)$ per record or count call. "Amortized" here means that although a single count call could in principle pop many expired entries at once, each timestamp is pushed once and popped at most once over the structure's whole lifetime, so total work across n calls is $O(n)$, averaging to $O(1)$ per call even though any single call's worst case is $O(n)$.
Space: $O(k)$, where k is the number of events currently inside the window, bounded by the arrival rate times the window length rather than by total history.

Edge cases

• No events yet: the deque is empty, count returns 0.
• Window smaller than the gap between consecutive events: the deque may hold 0 or 1 entries at a time.
• A burst of many events at the same instant: all are held until they age out together.

This only works if timestamps are guaranteed non-decreasing, as from a single writer or a single ordered stream. If events can arrive out of order (merged from multiple producers, or delayed in transit), the front-popping logic breaks, since an old event could arrive after entries that looked older have already been discarded. That calls for a different structure: a min-heap keyed on timestamp, or a fixed-size time-bucketed histogram (a small array of counters, one per sub-interval, rotated as time advances) for approximate counting in bounded memory regardless of burst size.

Direct answer

Enforcing "at most R requests per rolling T-second window" per user, at millions-of-users scale, comes down to picking how much state you keep per user and how precisely that state approximates a true rolling window. A fixed counter per window is cheapest ($O(1)$ per user) but allows up to 2R requests to slip through right across a window boundary; a rolling log of exact timestamps is perfectly precise but costs $O(R)$ per user; a token-refill (token-bucket) scheme and a two-counter sliding-window approximation both give $O(1)$ per-user memory with only small, bounded imprecision near boundaries, which is why they are the usual production choice at this scale.

Structured elaboration

Three structural approaches compared

Why a fixed counter's imprecision happens specifically at boundaries

If the window resets every T seconds, a user can send R requests in the last instant of one window and another R in the first instant of the next: both windows individually respect the R-per-window limit, but a true rolling T-second view sees up to 2R requests in a span far shorter than T. The rolling log fixes this by definition (it only ever counts requests actually within the trailing T seconds), at the cost of storing up to R timestamps per user. The two-counter and token-bucket schemes recover most of the precision of the rolling log at the memory cost of the fixed counter, by using the previous window's count as a fading estimate of "how many of those requests are still within the trailing T seconds," rather than discarding it entirely at the reset boundary.

Sharding for millions of users

Regardless of which per-user scheme is chosen, per-user state should be sharded by a hash of the user ID across many limiter nodes or partitions, so no single node holds all users and no single lock serializes all traffic. Route each user consistently to the same shard (consistent hashing keeps this stable as shards are added or removed) so all requests for one user hit the same counter state, and evict counters for inactive users on a time-to-live (TTL, an expiration timer after which an idle entry is dropped) so memory tracks active users rather than the full lifetime user base.

Worked example

The two-counter sliding-window approximation, concretely:

class SlidingWindowCounter:
    """
    Approximate sliding-window limiter: O(1) memory per user (two counters),
    O(1) time per check. Weights the previous fixed window by how much of it
    still overlaps the current rolling window.
    """

    def __init__(self, limit: int, window_seconds: float):
        self.limit = limit
        self.window = window_seconds
        self.curr_window_start = 0.0
        self.curr_count = 0
        self.prev_count = 0

    def _roll_window(self, now: float) -> None:
        elapsed = now - self.curr_window_start
        if elapsed >= 2 * self.window:
            self.prev_count = 0
            self.curr_count = 0
            self.curr_window_start = now
        elif elapsed >= self.window:
            self.prev_count = self.curr_count
            self.curr_count = 0
            self.curr_window_start += self.window

    def allow(self, now: float) -> bool:
        self._roll_window(now)
        elapsed_in_curr = now - self.curr_window_start
        overlap = max(0.0, (self.window - elapsed_in_curr) / self.window)
        estimated = self.prev_count * overlap + self.curr_count
        if estimated + 1 > self.limit:
            return False
        self.curr_count += 1
        return True


if __name__ == "__main__":
    limiter = SlidingWindowCounter(limit=5, window_seconds=1.0)
    # 5 requests at t=0.0 fill the first window
    results_first = [limiter.allow(0.0) for _ in range(5)]
    # a 6th request in the same window must be rejected
    sixth = limiter.allow(0.05)
    # at t=1.5 we are 50% into the new window; the estimate blends 50% of the
    # old window's 5 requests (2.5) with 0 new ones, so 2.5 + 1 <= 5 fits
    seventh = limiter.allow(1.5)
    print(results_first, sixth, seventh)

Running this prints:

[True, True, True, True, True] False True

Five requests at t=0.0 fill the first one-second window exactly to the limit of 5. A sixth request at t=0.05 (still inside that same window) is rejected, since the count is already at 5. At t=1.5, half a second into the next window, the estimate blends 50% of the previous window's 5 requests ($5 \times 0.5 = 2.5$) with the 0 requests so far in the current window: $2.5 + 1 \le 5$, so the seventh request is allowed. This is the boundary smoothing a fixed counter does not give you: a fixed counter would have simply reset to 0 at t=1.0 and allowed 5 fresh requests immediately, permitting the same 2x-at-the-boundary burst described above.

Complexity

Per-user check and update: $O(1)$ time for the fixed counter, token bucket, and two-counter sliding window; $O(\log R)$ or $O(1)$ amortized (averaged over a sequence of operations) for the rolling log depending on whether old timestamps are pruned lazily or with a deque. Per-user memory: $O(1)$ for the first three approaches, $O(R)$ for the rolling log.

Edge cases

• A burst exactly at a window boundary is the scenario every design above is explicitly trying to bound; state which imprecision (if any) your chosen scheme accepts.
• Clock skew between distributed limiter nodes can make the "current time" disagree slightly across shards; keep window arithmetic tolerant of small skew rather than assuming a perfectly synchronized clock.
• A user with no prior activity needs a cold-start default (empty counters, full token bucket) rather than an error.
• Inactive users must be evicted (TTL-based) so memory does not grow without bound across millions of distinct users who each showed up once.

Trade-offs & pitfalls

The common wrong turn is presenting the rolling log as strictly "the correct one" without acknowledging its $O(R)$-per-user memory cost: at millions of users and even a modest R, that can dwarf the memory of the $O(1)$ approaches by orders of magnitude, which is exactly why production rate limiters favor the token-bucket or sliding-window-counter approximation instead. A second common gap is proposing a single global lock or single-node counter for correctness: that eliminates any cross-shard race but reintroduces the exact contention problem millions of distinct users at high volume were meant to avoid; sharding by user ID sidesteps this because a fully correct answer only needs to be correct per user, not globally serialized. A third pitfall is conflating the token bucket's smoothing behavior with the sliding window's counting behavior: a token bucket happily allows a burst up to its full capacity the instant it has accumulated enough tokens, which is a different guarantee from "at most R in any rolling T-second window," and the two should not be presented as interchangeable without naming that difference.