Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

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

Structured elaboration

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

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

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

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

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

Worked example

import random


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

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

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

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


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

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

True
True
True
True
[1, 3]
1
1

Key points

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

Complexity

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

Edge cases

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

Trade-offs & pitfalls

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

Direct answer

Walk the list once, and at each node redirect its next reference back to the previous node before advancing, using three tracking references: previous, current, and a temporary save of current's original next. This is $O(n)$ time and $O(1)$ space. A recursive version expresses the identical rewiring, handling everything after the current node first and then flipping the one link back, but it pays for that with $O(n)$ call-stack space that the iterative version does not need.

Structured elaboration

The iterative three-pointer dance. Before overwriting curr.next, save it in a temporary variable, or the rest of the list is lost permanently. Then point curr.next back at prev, advance prev to curr, and advance curr to the saved temporary. Repeat until curr is empty.

The recursive version. The base case is an empty list or a single remaining node, which is already "reversed" as-is. Otherwise, recursively reverse everything after the head first; that recursive call returns the new head of the whole reversed list. Then head.next.next = head flips the one link connecting the old head back into the newly-reversed remainder, and head.next = None prevents the old head from accidentally pointing at itself in a two-node cycle.

What language a solution is written in does not change any of this. The reskin into Python, JavaScript, Swift, or Kotlin, or building the linked-list node class from scratch first, is the same pointer-rewiring skill underneath; only the syntax for holding and dereferencing a reference changes, not the three-step relinking logic itself.

Worked example

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


def reverse_iterative(head):
    prev = None
    curr = head
    while curr:
        next_tmp = curr.next  # save before overwriting
        curr.next = prev
        prev = curr
        curr = next_tmp
    return prev


def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def build_list(vals):
    dummy = Node(0)
    tail = dummy
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


if __name__ == "__main__":
    print(to_list(reverse_iterative(build_list([1, 2, 3, 4]))))
    print(to_list(reverse_recursive(build_list([1, 2, 3, 4]))))

Running this prints [4, 3, 2, 1] twice, once from each implementation.

Complexity

Time: $O(n)$ for both the iterative and recursive versions, since each one visits every node exactly once.
Space: $O(1)$ extra for the iterative version (three pointer variables regardless of list length); $O(n)$ for the recursive version, from the call stack, since the recursion descends one frame per node before any relinking happens.

Edge cases

• Empty list (head is None): both versions return None immediately without any relinking.
• Single-node list: both versions return that same node unchanged as the new head, since there is nothing to reverse.
• Very long list: the recursive version risks an actual stack overflow, since typical call-stack depth limits are far smaller than what a linked list can otherwise hold in memory.

Trade-offs & pitfalls

The recursive version risks an actual stack overflow on a very long list in production, not just an academic concern, since typical call-stack depth limits are far smaller than what a linked list or array can otherwise hold in memory. The single most common bug in the iterative version is forgetting to save curr.next before overwriting it, which permanently disconnects the rest of the list from anything still reachable.

Direct answer

Reverse the whole array, then reverse the first k elements and the remaining n-k elements separately; three linear passes compose into the fully rotated result with no auxiliary array. The same reversal trick generalizes directly: reversing a string in place is the identical two-pointer, swap-from-both-ends routine, and rotating a square matrix 90 degrees in place is a transpose followed by reversing each row, both built on the same in-place-swap primitive as the array rotation.

Structured elaboration

Why three reversals produce a rotation. Reversing the entire array puts every element in fully reversed order. Reversing the first k elements of that reversed array un-reverses exactly the block that should now sit at the front, restoring its original relative order; reversing the remaining n-k elements does the same for the remainder. Normalizing with k %= n handles k values larger than the array's length or equal to zero.

Generalizing to a string. The same in-place two-pointer swap from both ends is exactly what reverses a string, provided the string is held in a mutable container (a list of characters, for example, since Python's own string type is immutable and cannot be reversed truly in place without first converting it).

Generalizing to a square matrix. Transposing swaps matrix[i][j] with matrix[j][i] for every i < j, turning rows into columns. Reversing each row afterward flips left to right. Combined, what was the first column read top to bottom becomes the first row read left to right, which is exactly a 90-degree clockwise turn.

Related in-place-preprocessing techniques (with an honest space caveat). Prefix-sum preprocessing builds an auxiliary array once, in $O(n)$ time, so that any later range-sum query answers in $O(1)$; this trades $O(n)$ extra space for fast queries, so it is not itself an O(1)-extra-space technique, even though it shares this family's "one linear pass, reuse the result" character. Product-except-self, by contrast, genuinely can be done with O(1) extra space beyond the required output array: a first pass fills the output with the running product of everything to each index's left, and a second pass multiplies in the running product of everything to that index's right, needing no separate auxiliary array at all.

Worked example

def rotate_array(nums: list[int], k: int) -> None:
    n = len(nums)
    if n <= 1:
        return
    k %= n
    if k == 0:
        return

    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)


def reverse_string_inplace(chars: list[str]) -> None:
    i, j = 0, len(chars) - 1
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i += 1
        j -= 1


def rotate_matrix_90_cw_inplace(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()


if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7]
    rotate_array(arr, 3)
    print(arr)

    chars = list("hello")
    reverse_string_inplace(chars)
    print("".join(chars))

    m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    rotate_matrix_90_cw_inplace(m)
    print(m)

Running this prints [5, 6, 7, 1, 2, 3, 4], then olleh, then [[7, 4, 1], [8, 5, 2], [9, 6, 3]].

Complexity

rotate_array: time $O(n)$ for the three reversal passes, since they compose additively into a single linear scan rather than multiplying; space $O(1)$ extra, using only the two index pointers inside each reversal call.
reverse_string_inplace: time $O(n)$, one pass with two pointers closing in from both ends; space $O(1)$ extra beyond the mutable character list itself.
rotate_matrix_90_cw_inplace: time $O(n^2)$ for an n-by-n matrix, since the transpose visits each of the $n^2$ cells once; space $O(1)$ extra, since both the transpose and the row reversals swap in place with no auxiliary matrix.

Edge cases

• k = 0, or k a multiple of the array's length once normalized via k %= n: rotate_array detects this and returns immediately without performing any reversals, since the array is already in its correct rotated position.
• Empty or single-element array or string: both rotate_array (via its n <= 1 guard) and reverse_string_inplace (via while i < j never firing) return immediately with nothing to do.
• A non-square matrix passed to rotate_matrix_90_cw_inplace: this implementation assumes a square matrix, and a non-square transpose changes the matrix's dimensions, so it cannot be rotated true in place this way.

Trade-offs & pitfalls

Forgetting k %= n for a k larger than the array's length either wastes work or, in a careless implementation, indexes out of range. The transpose-then-reverse-rows trick only works for a square matrix: transposing a non-square matrix changes its dimensions, so a genuinely non-square rotation needs a separate output buffer rather than a true in-place transform. Python's string immutability means a real in-place string reversal needs a mutable container (a list of characters, or a bytearray) first; there is no way to mutate a str object's characters directly.

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

The standard ladder, from fastest to slowest growth, is constant $O(1)$, logarithmic $O(\log n)$, linear $O(n)$, linearithmic $O(n \log n)$, and quadratic $O(n^2)$, where $n$ is the size of the input. Each class matches a signature access pattern: a direct lookup, halving a search space each step, one pass over the data, one pass paired with a logarithmic step (typical of good sorting), and comparing every pair of elements. Reporting only the worst-case bound without checking best- and average-case behavior can hide an algorithm that is usually fast but degrades badly on adversarial or already-sorted input, which is exactly the kind of surprise that shows up as a production incident rather than a benchmark number.

Structured elaboration

The five classes, with a concrete example each

Why best, average, and worst case are separate questions

The same algorithm can sit in different classes depending on which case you're asking about:

• Linear search: best case $O(1)$ (the target is first), worst case $O(n)$ (the target is last or absent).
• Insertion sort: best case $O(n)$ on already-sorted input, worst case $O(n^2)$ on reverse-sorted input.
• Quicksort: average case $O(n \log n)$ with a reasonable pivot strategy, worst case $O(n^2)$ if the pivot choice is adversarial (e.g., always picking the first element on already-sorted input).

Judging whether code is "fast enough" means matching the case that actually describes your expected input, not defaulting to whichever case is easiest to state. A cache-friendly, average-case-only justification is fine for random production traffic; it is not fine if an attacker can choose the input (hash-flooding a hash table into its worst case is a real, exploitable pattern).

Ranking functions by growth

Given a set of functions, you rank them by how they behave as $n \to \infty$, not by their value at any one $n$. For example, rank $\{\log n,\ \sqrt{n},\ n,\ n \log n,\ n^2\}$: substituting $n = 16$ gives $\log_2 16 = 4$, $\sqrt{16} = 4$ (a tie at this specific $n$), $n = 16$, $n \log n = 64$, $n^2 = 256$. The tie at $n=16$ is exactly why you don't rank by a single sample point: as $n$ grows, $\sqrt{n}$ pulls permanently ahead of $\log n$, so the correct asymptotic order is $O(\log n) < O(\sqrt n) < O(n) < O(n \log n) < O(n^2)$.

Big-O versus empirical profiling

Big-O describes an asymptotic trend as input size grows without bound; it deliberately ignores constant factors, lower-order terms, and hardware effects. Profiling measures what actually happens for the input sizes you really see, including those ignored factors (memory allocation, cache behavior, branch prediction, garbage collection). Neither replaces the other: Big-O tells you how a design will scale if the input grows 10x or 100x; profiling tells you where time is actually going today. A change that looks neutral or even negative in Big-O terms (e.g., adding a small constant-time cache) can be the dominant real-world win, and Big-O analysis alone would never surface that.

Why a smaller-Big-O algorithm can still be slower in practice

Big-O hides the constant multiplier in front of the growth term. An $O(n \log n)$ algorithm with heavy per-element overhead (extra allocations, function-call indirection, poor cache locality) can lose to a simple $O(n^2)$ algorithm until $n$ passes some crossover point, because the actual operation count is closer to $c_1 \cdot n \log n$ versus $c_2 \cdot n^2$, and if $c_1 \gg c_2$ the crossover point can be far larger than the $n$ you ever encounter. This matters most on hardware with tight memory bandwidth and small caches (mobile devices, embedded targets): the "better" complexity class only pays off once you actually reach the sizes where the growth term dominates the constant.

Worked example

Comparing raw operation counts at $n = 1{,}000{,}000$: $\log_2 n \approx 19.93$, so $n \log_2 n \approx 1{,}000{,}000 \times 19.93 \approx 19{,}931{,}569$, while $n^2 = 1{,}000{,}000{,}000{,}000$. The linearithmic count is about 20x the linear count, but the quadratic count is a million times the linear count, which is the concrete reason quadratic algorithms are the ones that visibly fall over first as data grows, while linearithmic ones stay usable much further out.

Trade-offs & pitfalls

• Quoting a single Big-O figure without naming which case (best, average, worst) it describes is the most common way this topic goes shallow in an interview; always attach the case.
• Big-O comparisons are only meaningful in the limit; for small, fixed input sizes, the algorithm with the better asymptotic class is not guaranteed to be faster once constants and hardware are accounted for.
• Average-case reasoning assumes something about the input distribution (often "roughly random"); that assumption breaks down for adversarial or attacker-controlled input, where the worst case is the one you actually need to defend against.
• Treating two algorithms in the same Big-O class as interchangeable ignores the constant factor, which is often the entire practical difference between them.