Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

An array gives $O(1)$ index-based random access and is cache-friendly, because its elements sit in one contiguous block of memory that the CPU can pull into cache together. A singly linked list gives $O(1)$ insertion or deletion once you already hold a reference to the splice point, at the cost of $O(n)$ traversal to reach any given position and extra per-node memory overhead. For a workload that is mostly random reads, pick an array (or dynamic array); for a workload that is mostly insertions and deletions in the middle where you already hold the relevant node reference, a linked list wins.

Structured elaboration

The contiguous-versus-non-contiguous memory allocation framing is exactly this same dimension stated differently: contiguous storage is what gives arrays both their cache locality and their index arithmetic; non-contiguous, per-node allocation is what gives linked lists their cheap local splicing at the cost of locality. In a garbage-collected (GC) language, this also affects collector pressure: many small linked-list node objects mean more individual objects for the garbage collector to track and scan, compared to one contiguous array allocation holding the same data.

Worked example

Consider inserting a new element in the middle of a ten-item collection, repeatedly, as items are typed into an editable list. With an array, each insertion must shift every element after the insertion point one slot over, an $O(n)$ cost per insertion regardless of whether you know exactly where to insert. With a singly linked list, if the editing position is tracked by an existing reference to the node just before it (as a cursor would be in a text-editing context), each insertion is a pure $O(1)$ relink; but if you only know the position as an index and must first walk from the head to reach it, the linked list gains nothing over the array for that access, since both now cost $O(n)$ overall. This is why the deciding factor is not "array versus linked list" in the abstract, but whether the workload naturally hands you a reference to the splice point or only an index.

Trade-offs & pitfalls

Assuming "$O(1)$ insertion" for a linked list means fast in absolute terms is a common mistake: reaching the splice point is usually the dominant cost unless a reference to it is already in hand from a prior traversal or an auxiliary index. Ignoring the per-element memory overhead ratio is another: a linked list of single integers can use several times the memory of the equivalent array, because the pointer overhead per node is fixed regardless of how small the stored value is. Modern hybrid structures such as a deque (double-ended queue) or a rope address parts of this trade-off by chunking data into contiguous blocks rather than choosing purely one extreme or the other.

Direct answer

Quickselect adapts quicksort's partitioning to find just the k-th largest element without fully sorting: after one partition step around a pivot, the pivot's final position tells you whether the answer lies to its left or right, so you only ever recurse into one side instead of both. That halves (in expectation) the work at each level rather than branching into two recursive calls, which is what brings the expected time down from sorting's $O(n \log n)$ to $O(n)$. A heap of size k is the better choice instead when you cannot, or do not want to, mutate the input in place, or when the data arrives as a stream and you need the running top-k as you go rather than a single final answer.

Structured elaboration

Why quickselect is expected O(n)

A single partition around a random pivot costs $O(n)$ and places the pivot at its correct sorted position, with everything smaller to its left and everything larger to its right. If that position is the one you are looking for, you are done; otherwise you recurse into only the one side that must contain the target index, discarding the other side's work entirely. With a reasonably balanced pivot (true on average for a random pivot), the total expected work follows the recurrence $T(n) = T\!\left(\frac{n}{2}\right) + O(n) = O(n)$ (expected), the same halving-geometric-series pattern that makes binary search $O(\log n)$, except here the per-level cost is $O(n)$ rather than $O(1)$, and only one recursive branch is taken rather than a binary search's implicit single branch. This is the key difference from quicksort, which must recurse into both sides to sort everything, giving $O(n \log n)$.

Why a heap of size k instead

• Streaming input: if elements arrive one at a time and you must always be able to report the current top k, quickselect does not apply directly, since it needs the whole array in hand to partition; a size-k min-heap updates in $O(\log k)$ per new element and always reflects the current top k.
• Avoiding in-place mutation: quickselect partitions the input array in place; if the caller cannot have their array reordered, a heap that only reads elements avoids that side effect (at the cost of $O(k)$ extra space).
• Worst-case guarantee: a naive quickselect has a worst case of $O(n^2)$ on an adversarial or unlucky pivot sequence (randomizing the pivot choice makes this astronomically unlikely, not impossible); a heap of size k guarantees $O(n \log k)$ in every case.
• k close to n: when k is large relative to n, a heap of size k approaches $O(k)$ extra space that is not much smaller than the array itself, and quickselect's in-place approach becomes the more memory-efficient option; when k is small, the heap's small extra space is a non-issue and its worst-case guarantee is attractive.

A related, absorbed framing: this is a selection-algorithm family, not a one-off trick

The same "avoid a full sort" idea generalizes. Finding the k-th smallest value in a matrix whose rows and columns are each sorted uses a min-heap over the smallest untried cell in each row (or a binary search directly over the value range, counting how many matrix entries are $\le$ a candidate value in $O(n)$ per probe) rather than flattening and sorting the whole matrix. And when memory, not just time, is the binding constraint (as in a memory-constrained k-smallest-elements variant), quickselect's in-place partitioning is preferable to a heap precisely because it needs no auxiliary structure beyond the input array itself.

Worked example

import heapq
import random


def kth_largest_quickselect(nums: list[int], k: int) -> int:
    """
    Return the k-th largest value (k=1 is the maximum).
    Expected O(n) time, O(1) extra space (in-place partition, iterative).
    Worst case O(n^2) on adversarial pivots; randomized pivot makes that
    astronomically unlikely rather than eliminating it.
    """
    if not (1 <= k <= len(nums)):
        raise ValueError("k out of range")
    target = len(nums) - k  # index of the k-th largest in sorted-ascending order
    lo, hi = 0, len(nums) - 1
    while True:
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
        pivot = nums[hi]
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        if store == target:
            return nums[store]
        elif store < target:
            lo = store + 1
        else:
            hi = store - 1


def kth_largest_heap(nums: list[int], k: int) -> int:
    """Min-heap of size k. O(n log k) time, O(k) space."""
    heap: list[int] = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap[0]


if __name__ == "__main__":
    random.seed(0)
    data = [3, 2, 1, 5, 6, 4]
    print("quickselect k=2:", kth_largest_quickselect(data.copy(), 2))
    print("heap k=2:", kth_largest_heap(data, 2))
    bigger = [7, 10, 4, 3, 20, 15]
    print("quickselect k=3:", kth_largest_quickselect(bigger.copy(), 3))
    print("heap k=3:", kth_largest_heap(bigger, 3))

Running this prints:

quickselect k=2: 5
heap k=2: 5
quickselect k=3: 10
heap k=3: 10

For [3, 2, 1, 5, 6, 4] sorted descending (6, 5, 4, 3, 2, 1), the 2nd largest is 5, and both methods agree. For [7, 10, 4, 3, 20, 15] sorted descending (20, 15, 10, 7, 4, 3), the 3rd largest is 10, and again both methods agree. The pivot choices inside quickselect are randomized but seeded (random.seed(0)), so this exact sequence of calls reproduces this exact output every time it is run.

Complexity

• Quickselect: expected time $O(n)$, worst case $O(n^2)$; space $O(1)$ extra (partitions in place, iteratively rather than recursively here).
• Heap of size k: time $O(n \log k)$ in every case; space $O(k)$ for the heap.

Edge cases

• k outside the range [1, len(nums)] is invalid input and should raise rather than silently returning a wrong value.
• Duplicate values are handled correctly by both methods, since partitioning and heap comparisons work on values, not identity.
• k equal to 1 (the maximum) or k equal to n (the minimum) are valid boundary cases worth checking by hand.
• An already-sorted or reverse-sorted array is exactly the input that most threatens a non-randomized quickselect's worst case; randomizing the pivot is what defends against it.

Trade-offs & pitfalls

The most common wrong turn is presenting quickselect as strictly superior because of its better expected time, without naming its $O(n^2)$ worst case or its requirement to mutate the input array in place; both are real costs that the heap approach avoids. A second common gap is forgetting that quickselect only gives you the k-th value itself, not the k values above it in order: if you also need the actual top-k list, you still need one more pass (or a heap) to collect everything on the correct side of the final partition. A third pitfall, specific to this absorbed question family, is treating "kth largest in an array" and "kth smallest in a sorted matrix" as needing the same algorithm: the matrix's extra structure (both rows and columns already sorted) is exactly what makes a heap-over-candidate-cells or binary-search-over-values approach effective there, and quickselect's partitioning does not directly apply to a two-dimensional sorted structure the same way.

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

Use binary (fast) exponentiation: repeatedly square the base and, on each bit of n that is set, multiply that squared value into the running result. This computes $x^n$ in O(log|n|) multiplications instead of O(n). A negative exponent is handled by inverting the base once up front (1/x) and treating the exponent as positive from then on.

Structured elaboration

Core idea: writing n in binary decomposes the power into a product of the base raised to each power-of-two position where n has a set bit:
$x^n = \prod_{i \,:\, \text{bit}_i(n)=1} x^{2^i}$
Squaring the base once per bit position produces exactly the $x^{2^i}$ terms needed, in the same single pass that reads the bits of n.

def my_pow(x: float, n: int) -> float:
    """
    Compute x**n via binary (fast) exponentiation in O(log|n|) time, O(1) space.
    Handles negative exponents and the 32-bit min-int edge case (in fixed-width languages).
    """
    if x == 0.0:
        if n > 0:
            return 0.0
        if n == 0:
            return 1.0
        raise ZeroDivisionError("0 cannot be raised to a negative power")

    exponent = n
    base = x
    if exponent < 0:
        base = 1.0 / base
        exponent = -exponent

    result = 1.0
    while exponent:
        if exponent & 1:
            result *= base
        base *= base
        exponent >>= 1
    return result


print(my_pow(2.0, 10))
print(my_pow(2.0, -3))
print(my_pow(3.0, 0))
print(my_pow(-2.0, 5))

Output:

1024.0
0.125
1.0
-32.0

Negative-exponent handling: invert x once, negate n, and reuse the same positive-exponent loop; in Python this negation is always safe since ints are arbitrary precision, but in a fixed-width 32-bit language, the most negative representable exponent must first be widened to a 64-bit type before negating it, since negating it directly overflows.

Worked example

Tracing $x=2, n=10$ (binary 1010) bit by bit:

The two set bits (positions 1 and 3) contribute $x^{2^1} \cdot x^{2^3} = 4 \cdot 256 = 1024 = 2^{10}$, matching the printed result exactly.

Complexity

$O(\log|n|)$ time, $O(1)$ space for the iterative version above (a recursive version instead
uses $O(\log|n|)$ call-stack space).

Edge cases

• n = 0: the while exponent loop never executes (exponent starts at 0), returning
  result = 1.0, matching my_pow(3.0, 0) -> 1.0.
• x = 0, n > 0: explicitly special-cased to return 0.0 before the main loop.
• x = 0, n = 0: explicitly special-cased to return 1.0 by convention.
• x = 0, n < 0: explicitly raises ZeroDivisionError, since 0 to a negative power is
  mathematically undefined; this must be special-cased rather than silently returning infinity
  or crashing with an unclear error.
• Negative base: sign is preserved correctly through repeated squaring and multiplication,
  e.g. my_pow(-2.0, 5) = -32.0.
• Most-negative fixed-width exponent (e.g. INT32_MIN): not an issue for Python's
  arbitrary-precision ints, but in a fixed-width 32-bit language the most negative representable
  exponent must be widened to a 64-bit type before negating it, since negating it directly
  overflows.

Trade-offs & pitfalls

• Floating-point precision: repeated squaring compounds rounding error faster than repeated multiplication in some regimes; for |x| very close to 1 raised to a huge power, or extreme |n| combined with |x| far from 1, relative error can grow. Computing via exp(n * log(x)) is an alternative when raw precision matters more than speed, but that requires x > 0 (log is undefined otherwise) and introduces its own rounding from the exp/log calls.
• Modular exponentiation: if the actual need is $x^n \bmod m$ (as in cryptographic-sized exponents), the accumulation step becomes (result * base) % m at every multiply, keeping every intermediate value bounded to a fixed size instead of letting a plain big-integer power grow unboundedly large.

Direct answer

Keep a min-heap (a priority queue: a tree-shaped structure that keeps the smallest element accessible at the root in logarithmic time) holding one candidate element from each of the k sources, tagged with which source it came from. Repeatedly pop the smallest, emit it, then pull the next element from that same source and push it back in. This touches every element exactly once and never holds more than k elements in the heap at a time, unlike scanning all k sources for the minimum on every step, which redoes that comparison work from scratch each time.

Structured elaboration

Maintain, per source, an iterator (or a buffered read-ahead block if the source is a file or network stream) rather than loading the whole source into memory. The heap holds at most one (value, source_id) pair per still-active source:

1. Prime the heap: pull the first element from each source and push all k pairs in.
2. Loop while the heap is non-empty: pop the smallest pair, emit its value, then pull the next element from that same source; if one exists, push it back onto the heap.
3. Stop when the heap empties, meaning every source is exhausted.

Why the heap beats scanning all k sources for the minimum: a linear scan over k sources costs $O(k)$ per output element, for $O(N \cdot k)$ total across $N$ elements. The heap instead pays $O(\log k)$ per push and pop, for $O(N \log k)$ total. Once k grows past a small constant (which it does for genuinely large fan-in, like merging thousands of shards), $\log k$ is dramatically cheaper than $k$, and the heap only ever holds k items regardless of how large each individual source is, which is what makes this work under a fixed memory budget.

Worked example

import heapq
from typing import Iterable, Iterator


def k_way_merge(sources: list[Iterable[int]]) -> Iterator[int]:
    heap: list[tuple[int, int, Iterator[int]]] = []
    for i, source in enumerate(sources):
        it = iter(source)
        first = next(it, None)
        if first is not None:
            heap.append((first, i, it))
    heapq.heapify(heap)

    while heap:
        value, i, it = heapq.heappop(heap)
        yield value
        nxt = next(it, None)
        if nxt is not None:
            heapq.heappush(heap, (nxt, i, it))


stream_a = [1, 4, 9, 15]
stream_b = [2, 3, 8]
stream_c = [0, 5, 6, 7, 20]

merged = list(k_way_merge([stream_a, stream_b, stream_c]))
print(merged)
print(merged == sorted(stream_a + stream_b + stream_c))

Running this prints:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 20]
True

Key points

• The heap never grows past k elements no matter how large each source is, which is exactly what makes this work when sources are too large to fit in memory together.
• Each source only needs to expose "give me the current head" and "advance to the next element," which is why the same code works whether a source is a Python list, a sorted linked list, or a buffered file reader.

Complexity

where $N$ is the total number of elements across all sources. If sources are read from disk in blocks rather than streamed one element at a time, add $O(k \cdot \text{block\_size})$ for the read-ahead buffers.

Edge cases

• An empty source: simply contributes nothing to the initial heap priming, handled by the if first is not None guard.
• Duplicate values across sources: the heap comparison ties are broken by insertion order in this implementation (via the source index in the tuple), so output remains stable and well-defined.
• All sources exhausted simultaneously: the loop ends naturally when the heap empties.

Trade-offs & pitfalls

For disk-resident or over-the-network sources, reading one element at a time is usually the wrong granularity: buffering a block per source amortizes I/O overhead, at the cost of O(k * block_size) memory instead of O(k). This is the same "k-way-merge" primitive whether the k inputs are k sorted arrays, k sorted linked lists (pop the head node instead of an array iterator), or k disk-resident sorted files too large to hold together, and it generalizes further to an external top-K query across those files by simply stopping the loop after K pops instead of draining the heap. A common mistake is reaching for a full sort of the concatenated data instead of a merge: since each source is already sorted, a merge is $O(N \log k)$ while re-sorting everything from scratch is $O(N \log N)$, strictly worse whenever $k \ll N$, which is the normal case.