Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Advance one pointer (slow) one step at a time and another (fast) two steps at a time. If the list has no cycle, fast reaches the end first and you can report there is none. If it does have a cycle, fast eventually laps slow and the two meet somewhere inside it. Once they meet, restarting one pointer at the head and advancing both pointers one step at a time makes them meet again exactly at the cycle's start. All of this uses $O(1)$ extra space, no visited set required.

Structured elaboration

Why meeting implies a cycle, and why no meeting implies no cycle. With no cycle, fast strictly gains ground toward a null terminator every step and reaches it in at most n/2 steps; it can never occupy the same node as slow without a cycle to loop back through. Once both pointers are inside a cycle, fast closes the gap to slow by exactly one node per step, because fast gains two steps of distance while slow gains one, a net closing rate of one per step. Since the gap can never exceed the cycle's length, they are guaranteed to meet within one full lap of the cycle.

Why the meeting point locates the cycle's start. Let a be the distance from the head to the cycle's start, c be the cycle's length, and b be the distance from the cycle's start to the meeting point, with $0 \le b < c$. By the time they meet, slow has traveled a + b steps and fast has traveled exactly twice that, but fast has also gone around the cycle some whole number of extra laps $n \ge 1$:

So a and (c - b) differ by a whole number of cycle lengths, meaning a pointer walking one step at a time from the head, and a pointer walking one step at a time from the meeting point, land on the same node after exactly a steps: the cycle's start.

Related applications of the same fast/slow pattern. Removing the n-th node from the end of a list uses the same shape without any cycle involved: advance one pointer n steps first, then move both pointers together; when the front pointer reaches the end, the trailing pointer sits exactly at the node to remove. Finding a duplicate number hidden in an array reframes the array itself as an implicit linked list, where the value stored at each index tells you which index to visit next; a repeated value forces two different positions to point at the same next index, creating a cycle in that implicit list, which Floyd's tortoise-and-hare detects exactly the way it detects a cycle here.

Worked example

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


def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            ptr = head
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None


if __name__ == "__main__":
    nodes = [Node(i) for i in range(5)]  # values 0,1,2,3,4
    for i in range(4):
        nodes[i].next = nodes[i + 1]
    nodes[4].next = nodes[2]  # cycle back into node with value 2
    start = detect_cycle_start(nodes[0])
    print(start.val)

Running this prints 2. In the derivation's terms: a = 2 (two steps from the head, value 0, to the cycle's start, value 2), c = 3 (the cycle 2 to 3 to 4 back to 2 has three edges), and the two pointers first meet at the node with value 3, so b = 1 (one step from the cycle's start to that meeting point). Checking the identity: c - b = 3 - 1 = 2, which equals a, confirming the derivation against this concrete run.

Complexity

Time: $O(n)$. The pointers meet within one full lap of the cycle once both are inside it, and finding the cycle's start afterward takes at most another full lap; both phases are bounded by a constant multiple of the list's length n.
Space: $O(1)$, since only the slow and fast pointers (and later ptr) are held, with no visited set.

Edge cases

• Empty list (head is None): fast is None immediately, so the loop never runs and the function correctly returns no cycle.
• Single node with no self-link: fast.next is None on the first check, so the loop exits immediately with no cycle detected.
• Single node that cycles to itself: slow and fast both land back on that same node on the first iteration, correctly reporting it as the cycle's start.

Trade-offs & pitfalls

A common bug is comparing pointer values instead of pointer identity; when list values can repeat, slow.val == fast.val can be true without slow and fast being the same node, so the check must be slow is fast.

Direct answer

Struct-of-arrays (SoA) wins whenever a hot loop updates or reads ONE field across millions of elements every frame or batch, because that access pattern is fully contiguous and lets the CPU prefetch and vectorize; array-of-structs (AoS) wins when you typically touch ALL of an element's fields together, since then each element's fields already sit next to each other in memory. Layering a typed, fixed-width numeric array (a JavaScript Float32Array, a NumPy array of a fixed dtype) underneath that SoA layout compounds the benefit, since it guarantees the backing memory is one flat buffer of raw numbers with no per-element pointer indirection, whereas a general-purpose array can silently degrade into a collection of individually heap-allocated boxed values.

Structured elaboration

• Cache locality: CPUs pull memory in cache-line-sized chunks. SoA's per-field contiguity means a loop over positions.x touches only x values back-to-back, so nearly every value in a fetched cache line gets used. AoS interleaves x, y, vx, vy, ... together, so the same loop skips over unrelated fields and wastes most of each fetched cache line.
• Vectorization: SIMD instructions operate on several contiguous same-type values at once, which is exactly the shape SoA's per-field arrays already have. AoS forces strided or gathered loads that most compilers and runtimes cannot auto-vectorize as effectively.
• Typed vs. general-purpose arrays: a plain JavaScript Array (or a Python list) stores references or boxed numbers by default, and a JavaScript engine can further "de-optimize" such an array the moment it holds mixed types or develops holes, turning even a nominally numeric array into a slower, pointer-chasing structure. A Float32Array/Int32Array (or a NumPy ndarray of a fixed dtype) is backed by one contiguous raw buffer from the start, with no per-element object header and no boxing, which is what lets SoA's cache and vectorization benefits actually materialize in a managed-language runtime instead of remaining a theoretical property of the layout on paper.

from dataclasses import dataclass

# --- AoS: array of structs ---
@dataclass
class ParticleAoS:
    x: float
    y: float
    vx: float
    vy: float

def step_aos(particles, dt):
    for p in particles:
        p.x += p.vx * dt
        p.y += p.vy * dt

# --- SoA: struct of (parallel) arrays ---
class ParticlesSoA:
    def __init__(self, n):
        self.x = [0.0] * n
        self.y = [0.0] * n
        self.vx = [1.0] * n
        self.vy = [2.0] * n

def step_soa(particles: ParticlesSoA, dt):
    x, vx = particles.x, particles.vx
    for i in range(len(x)):
        x[i] += vx[i] * dt
    y, vy = particles.y, particles.vy
    for i in range(len(y)):
        y[i] += vy[i] * dt


aos = [ParticleAoS(0.0, 0.0, 1.0, 2.0) for _ in range(3)]
step_aos(aos, dt=0.5)
print([(p.x, p.y) for p in aos])

soa = ParticlesSoA(3)
step_soa(soa, dt=0.5)
print(list(zip(soa.x, soa.y)))

Output:

[(0.5, 1.0), (0.5, 1.0), (0.5, 1.0)]
[(0.5, 1.0), (0.5, 1.0), (0.5, 1.0)]

Both layouts are correct and produce the same numeric result: the difference is entirely about how the same computation touches memory, not what it computes. The typed-array-vs-general-array distinction itself is a runtime/engine property rather than something Python's own list meaningfully demonstrates the same way, so that specific claim is stated here rather than fabricated as a measured number.

Worked example

Both step_aos and step_soa update the same three particles (initial position (0,0), velocity (1,2)) by dt=0.5 and produce the identical result (0.5, 1.0) per particle, confirmed by the run above.

Trade-offs & pitfalls

• Read-modify-write of one whole entity is awkward under SoA: "give me object 47's full state" requires touching N separate arrays at the same index instead of one struct, and a bug that updates x[] without updating y[] leaves the arrays desynchronized in a way that's easy to introduce and hard to spot.
• Serialization: AoS is simpler to reason about and serialize one whole record at a time. SoA often needs reassembly into per-record form for row-oriented transport or storage, though it enables much stronger columnar compression, since values of one field usually compress far better together than mixed-field bytes, which is why analytics/columnar storage formats default to SoA-shaped layouts.
• A common half-measure that gets the worst of both: an array-per-field layout where each element is still a heap-allocated, individually-boxed number, rather than a raw contiguous value, LOOKS like SoA but doesn't deliver its benefit; it is really AoS's overhead relabeled. The fix is a genuinely typed, fixed-width backing store per field (a typed array, a NumPy array, a primitive array in a systems language), not merely "one array per attribute name."
• Don't over-apply SoA: for a small, heterogeneous collection (dozens of objects, not millions) accessed in varied, whole-object ways, the cache and vectorization win doesn't materialize, and AoS's simplicity usually wins in practice.

Direct answer

Slide a window over the string with two pointers, and keep a hash map from character to the index right after its most recent occurrence. When the character at the right pointer has been seen before at or after the current window's left edge, jump the left pointer forward to just past that previous occurrence, but never backward, and track the widest window seen along the way. Because the left pointer only ever advances and the right pointer sweeps the string once, the whole scan is $O(n)$ time using $O(\min(n, \text{alphabet size}))$ space for the map.

Approach

• Maintain last_seen, mapping each character to one past the index of its most recent occurrence (storing index + 1 lets an unseen character default cleanly to 0).
• Maintain left, the window's start, and best, the longest valid window length so far.
• For each right, if the current character was seen before, set left = max(left, last_seen[char]); the max is essential, not optional.
• Update best with the current window length right - left + 1, then record last_seen[char] = right + 1.

def length_of_longest_substring(s: str) -> int:
    """O(n) time, O(min(n, alphabet size)) space sliding window."""
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen:
            left = max(left, last_seen[ch])
        best = max(best, right - left + 1)
        last_seen[ch] = right + 1
    return best


if __name__ == "__main__":
    print(length_of_longest_substring("abcabcbb"))  # 3
    print(length_of_longest_substring("bbbbb"))      # 1
    print(length_of_longest_substring("pwwkew"))     # 3
    print(length_of_longest_substring(""))           # 0

Running this prints 3, 1, 3, 0, matching the well-known cases for this problem.

Key points

• Why max, not a direct jump, is required: dropping the max and always jumping left = last_seen[ch] breaks correctness whenever a repeated character's earlier occurrence already fell outside the current window, because that would move left backward, re-including characters that had already been correctly excluded. Concretely, on "abba" a buggy version without max reports length 3, while the correct version reports 2 (the true answer, since "ab" and "ba" are the longest repeat-free substrings, both length 2). Verifying this directly:

def buggy_longest(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen:
            left = last_seen[ch]  # missing max(): can move left backward
        best = max(best, right - left + 1)
        last_seen[ch] = right + 1
    return best


def correct_longest(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen:
            left = max(left, last_seen[ch])
        best = max(best, right - left + 1)
        last_seen[ch] = right + 1
    return best


if __name__ == "__main__":
    print("abba ->", buggy_longest("abba"), "vs correct", correct_longest("abba"))

Running this prints abba -> 3 vs correct 2: the buggy version claims a length-3 window exists in "abba", but no 3-character substring of "abba" is actually repeat-free, so 3 is wrong.

• An alternative that uses a set instead of a map (shrinking left one character at a time until the repeat is gone, rather than jumping straight to the right position) is also correct and still $O(n)$ overall, since each character enters and leaves the set at most once, but it does more per-step work whenever the repeat is far behind the current position.

Complexity

Time: $O(n)$, since right advances once per character and left never moves backward, so together they make at most $O(n)$ total steps. Space: $O(\min(n, \text{alphabet size}))$ for the map.

Edge cases

• Empty string: returns 0.
• All identical characters (e.g., "bbbbb"): returns 1.
• All unique characters: returns the full length of the string.
• A single character: returns 1.

Direct answer

A stack is last-in-first-out (LIFO): the most recently added item comes out first. A queue is first-in-first-out (FIFO): items come out in the order they arrived. Use a stack when you need to undo or backtrack in reverse arrival order, such as a browser's back button or a function call stack; use a queue when arrival order must be preserved, such as a task scheduler or a print spooler. You can build a queue out of two stacks: push is $O(1)$ worst case, and pop is amortized (averaged over a sequence of operations) $O(1)$ because each element only ever moves between the two stacks once over its lifetime.

Structured elaboration

Queue from two stacks. Keep an in_stack that absorbs pushes and an out_stack that serves pops. Pushing always goes to in_stack in $O(1)$. When a pop or peek is requested and out_stack is empty, drain all of in_stack into out_stack; this reverses the order, so the oldest element (which was at the bottom of in_stack) ends up on top of out_stack, ready to be returned first.

Why the amortized argument holds. Use the aggregate method: over any sequence of n operations, each element is pushed onto in_stack exactly once (cost 1), moved from in_stack to out_stack at most once in its lifetime (cost 1), and popped from out_stack exactly once (cost 1). No element is ever moved more than that, so the total work across the whole sequence is bounded by a constant multiple of n, which is what "amortized $O(1)$ per operation" means, even though any single pop that triggers the drain costs $O(n)$ by itself.

Worked example

class QueueFromStacks:
    def __init__(self):
        self.in_stack: list[int] = []
        self.out_stack: list[int] = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def _transfer(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]


if __name__ == "__main__":
    q = QueueFromStacks()
    q.push(1)
    q.push(2)
    q.push(3)
    seq = [q.pop(), q.peek()]
    q.push(4)
    seq += [q.pop(), q.pop(), q.pop()]
    print(seq)

Running this prints [1, 2, 2, 3, 4]. The first pop() triggers a drain (in_stack [1,2,3] becomes out_stack [3,2,1], top popped is 1); peek() then reads 2 for free from the already-drained out_stack; pushing 4 goes straight to in_stack without disturbing out_stack; the remaining pops (2, 3) come from out_stack, and the last pop (4) triggers a second drain since out_stack had emptied.

Complexity

Space: $O(n)$ total across the two internal stacks, since every pushed element lives in exactly one of them at any time (no extra space is used beyond storing the n elements themselves).

Edge cases

• Calling pop() or peek() on an empty two-stack queue: in the reference implementation, _transfer() leaves out_stack empty when both stacks are empty, so pop()'s self.out_stack.pop() and peek()'s self.out_stack[-1] both raise an unhandled IndexError instead of failing cleanly. Guard this explicitly, for example if not self.in_stack and not self.out_stack: raise IndexError("pop from empty queue") before touching out_stack, so the caller gets a clear, intentional signal rather than an incidental one.
• A single push followed immediately by a pop: the drain moves that one element from in_stack to out_stack and it is returned, leaving both stacks empty again, which is the state the empty-queue guard above must handle correctly on the next call.

Trade-offs & pitfalls

The most common confusion is treating "amortized" as "always fast": a single pop can still cost $O(n)$ when it triggers the drain. Note the asymmetry with building a stack out of a single queue by rotating on every push (dequeue-then-requeue the previous elements so the newest sits at the front): that rotation happens on every single push, not just occasionally, so it is genuinely $O(n)$ per push with no amortization to appeal to, unlike the two-stack construction above where the expensive transfer is rare and each element only ever pays for it once.

Direct answer

A plain binary search that stops as soon as it finds any matching element can land on any of several equal occurrences, not necessarily the first one. To find the boundary instead, keep searching left even after finding a match: record the match as a candidate answer, then continue narrowing into the left half, so the search only stops once the range has collapsed and the leftmost qualifying index is guaranteed to be the last one recorded.

Structured elaboration

Approach

• Define the search as finding the first index i such that arr[i] >= target (a "lower bound"), over a half-open range [lo, hi) where hi starts at len(arr).
• At each step, compute mid. If arr[mid] >= target, mid could be the answer, but there might be an earlier index just as good, so shrink hi to mid (keep looking left) rather than stopping. If arr[mid] < target, the answer must be strictly to the right, so move lo to mid + 1.
• The loop invariant: every index below lo is known to be < target, and every index at or above hi is not yet ruled out only because it isn't needed anymore. When lo == hi, that boundary is exactly the first index >= target.
• To get the first and last index a value actually occupies, call this lower-bound search twice: once for target, and once for target + 1 (whose result, minus one, gives the last index of target). This is exactly the "first event at or after a given time" query run against a timestamp-ordered log or time series: the same lower-bound primitive, just with timestamps standing in for the sorted values.

def lower_bound(arr, target):
    """
    First index i such that arr[i] >= target, or len(arr) if none exists.
    arr is sorted ascending and may contain duplicates.
    """
    lo, hi = 0, len(arr)  # half-open search space [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            hi = mid       # mid could be the answer; keep looking left
        else:
            lo = mid + 1   # mid is too small; answer must be to the right
    return lo


def first_and_last(arr, target):
    first = lower_bound(arr, target)
    if first == len(arr) or arr[first] != target:
        return (-1, -1)
    last = lower_bound(arr, target + 1) - 1
    return (first, last)

Key points

• The invariant "never stop early on a match, keep narrowing left" is what prevents landing on an arbitrary occurrence of a duplicated value.
• A half-open range [lo, hi) with hi = mid on a match (not mid - 1) avoids the classic off-by-one that causes an infinite loop when lo and hi become adjacent.

Worked example

log = [1, 3, 3, 3, 5, 8, 8, 10]. lower_bound(log, 3) returns 1 (the first of the three 3s). lower_bound(log, 4) returns 4 (no 4 exists, but index 4 holds 5, the first value >= 4, sitting between the run of 3s and the 5). lower_bound(log, 11) returns 8 (one past the end, since nothing is >= 11). first_and_last(log, 8) returns (5, 6) (the two 8s). first_and_last(log, 6) returns (-1, -1) (6 is not present at all).

Trade-offs & pitfalls

Complexity

Time: $O(\log n)$ per lower-bound search; finding both the first and last index of a value costs two searches, still $O(\log n)$ overall.
Space: $O(1)$.

Edge cases

• Empty array: lo starts equal to hi (both 0), the loop never runs, returns 0, meaning "insert here" or "not found."
• Target smaller than every element: returns 0.
• Target larger than every element: returns len(arr).
• Target absent but between two existing values: returns the index of the next-larger value, the correct insertion point even though the value itself isn't present.

Writing the comparison as arr[mid] == target and stopping immediately is what causes an ordinary binary search to return an arbitrary occurrence, since equal-valued matches don't distinguish which one was found. For very large or on-disk sorted data, such as a timestamp-indexed log too big to hold in memory, the same lower-bound logic still applies as long as an element can be fetched by index in roughly constant time (a memory-mapped file, fixed-width records, or a block index all work); if only sequential reads are available, an exponential-search-style probe would be needed first to find a bounding block before binary searching within it.