Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

For the yes/no version, build a dynamic programming (DP) table dp[i] meaning "the prefix s[:i] can be segmented into dictionary words," with dp[0] = True; dp[i] is true if some earlier split point j has dp[j] true and s[j:i] is a dictionary word. For the harder variant (return every valid way to insert spaces, known as Word Break II), switch to backtracking with memoization keyed by suffix start index: each suffix's list of valid segmentations is computed once, no matter how many different prefixes lead into it, which is what avoids recomputing the same suffix's answer across all the different ways of reaching it.

Structured elaboration

Boolean version.

def word_break(s, word_dict):
    """
    True/False: can s be segmented into dictionary words?
    dp[i] = s[:i] is segmentable. O(n^2) time (n = len(s), assuming O(1)
    substring hashing), O(n) space.
    """
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

All-segmentations version (Word Break II). The naive way to extend the boolean DP to "return every segmentation" is to backtrack from index 0, trying every dictionary word at every position and recursing on the remainder. Without caching, the same suffix gets re-solved from scratch every time a different prefix reaches it (for example, both "cats" and "cat" + "s" as separate prefixes can both need the segmentations of the exact same remaining suffix). Memoizing by suffix start index fixes this: solve each suffix once, cache its list of valid word-sequences, and every caller that reaches that suffix again reuses the cached list instead of re-exploring it.

def word_break_all(s, word_dict):
    """
    Return every valid space-insertion segmentation of s into dictionary
    words. Memoizes by suffix start index so each suffix's set of valid
    segmentations is computed once no matter how many prefixes reach it.
    """
    word_set = set(word_dict)
    n = len(s)
    memo = {}

    def solve(start):
        if start == n:
            return [[]]          # one way to segment the empty suffix: no words
        if start in memo:
            return memo[start]
        results = []
        for end in range(start + 1, n + 1):
            word = s[start:end]
            if word in word_set:
                for rest in solve(end):
                    results.append([word] + rest)
        memo[start] = results
        return results

    return [' '.join(words) for words in solve(0)]

Worked example

print(word_break("leetcode", ["leet", "code"]))
print(word_break_all("catsanddog", ["cat", "cats", "and", "sand", "dog"]))

Output:

True
['cat sand dog', 'cats and dog']

"catsanddog" shows exactly why memoization by suffix matters: both the "cat" branch and the "cats" branch eventually need to segment the suffix "anddog" starting at index 4 (after "cats") or a different suffix after "cat"; more generally, once you compute the valid segmentations of a given suffix once, every prefix path that reaches that same suffix reuses the cached list instead of re-deriving it.

Trade-offs & pitfalls

Key points

• The boolean DP and the all-segmentations backtracking solve related but distinct questions; do not try to derive the full segmentation list by post-processing the boolean table alone, since the table only records reachability, not which split points were used.
• Memoization (top-down) is the natural fit for Word Break II because the set of reachable suffixes is typically much smaller than all possible substrings, and you only want to do work for suffixes actually visited during backtracking.
• Without the memo cache, the naive backtracking can be exponential in the worst case (a string that segments in many overlapping ways re-explores the same suffixes repeatedly); memoization by suffix start bounds the work by (number of suffixes) times (average word-matching cost per suffix).

Complexity

• Boolean version: time $O(n^2)$ in the worst case (n = length of s, assuming O(1) substring hashing/comparison per candidate split), space $O(n)$.
• All-segmentations version: time and space are bounded by the number of distinct suffixes ($O(n)$) times the work per suffix, but the output size itself can be exponential in the worst case (a string with many valid segmentations, such as all-identical-character strings against a permissive dictionary), so total output-copying cost is not simply $O(n)$; the memoization only prevents recomputing each suffix's segmentation list, it cannot shrink an inherently large output.

Edge cases

• Empty string: boolean version returns True (vacuously segmentable); all-segmentations version returns a single empty segmentation.
• No word in the dictionary matches any prefix: boolean version returns False for non-empty s; all-segmentations version returns an empty list.
• Dictionary words longer than the remaining suffix are simply never matched, no special-casing needed since the substring slice would not equal any dictionary word.

Direct answer

Count frequencies first, then either maintain a min-heap of size k as you scan the counted items (evicting the smallest whenever the heap grows past k), or bucket the items by frequency and read off the top k directly. The heap approach costs $O(n \log k)$ time; the bucket approach costs $O(n)$ time but needs frequency values that are bounded by the input size. When k is very small relative to the number of distinct items, the heap wins because $\log k$ is tiny; when k is not small (approaching the number of distinct items), bucket sort's flat $O(n)$ bound stops paying a per-item $\log k$ penalty at all.

Structured elaboration

Heap of size k

Count every item's frequency (a single pass, $O(n)$). Then walk the distinct items, pushing each (frequency, value) pair onto a min-heap; once the heap holds k pairs, only push a new one if its frequency beats the current minimum, evicting that minimum first. The heap never holds more than k pairs at once, so each push or evict is $O(\log k)$, and there are at most one distinct-items-count many of them.

Bucket sort by frequency

Frequencies in a collection of n items are themselves bounded by n (an item can appear at most n times), so you can allocate n+1 buckets indexed directly by frequency and drop each distinct item into buckets[its frequency]. Reading buckets from the highest index down and collecting values until you have k of them is $O(n)$ total: no comparisons, no heap, just direct indexing.

When to prefer which

• k very small relative to distinct-item count: the heap's $O(n \log k)$ is close to $O(n)$ since $\log k$ is small, and it avoids allocating an array sized to the full item count the way the bucket approach does.
• k not small (comparable to the number of distinct items): the bucket approach's flat $O(n)$ bound no longer pays any per-item logarithmic penalty, while the heap's $\log k$ factor grows along with k; bucket sort becomes the clearly faster choice.
• Frequencies not naturally bounded by n (for example, if you were instead ranking by an unbounded external weight rather than a count derived from the input itself), bucket sort's indexing assumption breaks down and the heap approach generalizes more directly.

Worked example

import heapq
from collections import Counter


def top_k_frequent_heap(items: list[str], k: int) -> list[str]:
    """
    Min-heap of size k keyed by frequency. O(n log k) time, O(n) space
    for the frequency table plus O(k) for the heap.
    """
    if k <= 0:
        return []
    counts = Counter(items)
    heap: list[tuple[int, str]] = []
    for value, freq in counts.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, value))
        elif freq > heap[0][0]:
            heapq.heapreplace(heap, (freq, value))
    heap.sort(reverse=True)
    return [value for _, value in heap]


def top_k_frequent_bucket(items: list[str], k: int) -> list[str]:
    """
    Bucket sort by frequency. O(n) time, O(n) space.
    Bucket index = frequency (bounded by len(items)), so no comparison sort
    is needed once counts are known.
    """
    if k <= 0:
        return []
    counts = Counter(items)
    buckets: list[list[str]] = [[] for _ in range(len(items) + 1)]
    for value, freq in counts.items():
        buckets[freq].append(value)
    result: list[str] = []
    for freq in range(len(buckets) - 1, 0, -1):
        for value in buckets[freq]:
            result.append(value)
            if len(result) == k:
                return result
    return result


if __name__ == "__main__":
    data = ["a", "b", "a", "c", "b", "a", "d"]
    print("heap:", top_k_frequent_heap(data, 2))
    print("bucket:", top_k_frequent_bucket(data, 2))

Running this prints:

heap: ['a', 'b']
bucket: ['a', 'b']

For ["a","b","a","c","b","a","d"], the frequencies are a:3, b:2, c:1, d:1. Both the size-2 min-heap and the bucket-sort approach correctly identify a and b as the two most frequent items, agreeing with each other as they must, since both are computing the same top-k set from the same frequency counts.

Complexity

• Heap of size k: time $O(n \log k)$ (counting is $O(n)$, each of up to n distinct-item heap operations is $O(\log k)$); space $O(n)$ for the frequency table plus $O(k)$ for the heap.
• Bucket sort: time $O(n)$ (counting plus a single pass over buckets); space $O(n)$ for the frequency table plus the bucket array.

Edge cases

• k equal to the number of distinct items should return all of them.
• Ties in frequency mean the "top k" set is well-defined but the specific order among tied items is not, unless a tie-break rule (for example, lower value first) is specified.
• k=0 should return an empty result rather than erroring or returning one item.
• An empty input collection should return an empty result for any k.

Trade-offs & pitfalls

A common wrong turn is defaulting to a full sort of all distinct items by frequency ($O(n \log n)$ on the number of distinct items) instead of recognizing that only the top k are needed, which is exactly what both the heap-of-size-k and bucket-sort approaches avoid paying for. A second common gap is not noticing that bucket sort's efficiency depends on frequencies being bounded by a value proportional to n; presenting it as a universal replacement for the heap approach without that caveat overstates its applicability. For the streaming follow-up this question absorbs, only the heap approach adapts directly: a size-k heap can be updated incrementally as frequencies change, while bucket sort assumes all counts are known before you build the buckets and does not update as cheaply if counts keep shifting.

Direct answer

The 0/1 knapsack DP state is dp[c] meaning "maximum total value achievable using a budget of exactly (or up to) c," updated per item by dp[c] = max(dp[c], dp[c - weight] + value), iterating capacities in descending order so each item is only used once. If the question changes from "maximize value" to "is some exact target sum achievable at all," the state becomes a boolean reachable[s] instead of a running maximum, using the identical recurrence shape (reachable[s] = reachable[s] or reachable[s - weight]) but tracking reachability instead of an optimum. This exact-sum variant is the same shape as the well-known Partition Equal Subset Sum problem, which asks whether a set of numbers can be split into two subsets with equal totals.

Structured elaboration

Value-maximization DP.

def knapsack_max_value(weights, values, capacity):
    """
    0/1 knapsack: maximum total value without exceeding capacity, each item
    at most once. dp[c] = best value achievable with budget c.
    Time O(n * capacity), Space O(capacity) (rolling 1D array).
    """
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # descending: each item used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

Feasibility (exact-sum) DP. Change the table's meaning from "best value so far" to "is this sum reachable," and change the update from a max to a boolean OR:

def subset_sum_feasible(weights, target):
    """
    Can some subset of weights sum to exactly target?
    reachable[s] = True if sum s is achievable using a subset of items seen
    so far. Same 0/1 recurrence as knapsack, but the DP value is a boolean
    "reachable" flag instead of a running maximum.
    Time O(n * target), Space O(target).
    """
    reachable = [False] * (target + 1)
    reachable[0] = True
    for w in weights:
        for s in range(target, w - 1, -1):
            if reachable[s - w]:
                reachable[s] = True
    return reachable[target]

Partition Equal Subset Sum is exactly this feasibility check with target set to half the total sum of the input numbers (if the total is odd, an equal split is impossible immediately, no DP needed). The same feasibility shape also applies to budget-constrained subset-selection outside pure combinatorics: for example, choosing dashboard KPIs or metrics under a display-cost budget, where each metric has a fixed "screen cost" and you want to know whether some subset exactly fills an allotted display budget (or, with the max-value version, which subset of metrics maximizes total business value within that budget).

Worked example

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_max_value(weights, values, 5))

Output: 7 (taking the weight-2/value-3 and weight-3/value-4 items exactly fills the capacity-5 budget for total value 7; no other combination of these items reaches higher value within capacity 5).

nums = [1, 5, 11, 5]
total = sum(nums)
print(total, total % 2 == 0, subset_sum_feasible(nums, total // 2) if total % 2 == 0 else None)

Output: 22 True True. The total is 22 (even), so an equal split needs a subset summing to 11; subset_sum_feasible confirms 11 is reachable (via 5 + 5 + 1), so [1, 5, 11, 5] can be partitioned into two equal-sum halves.

Trade-offs & pitfalls

Key points

• Greedy selection by value-to-weight ratio is optimal for the fractional knapsack (where you can take a fraction of an item) but is not guaranteed optimal for 0/1 knapsack, since taking a high-ratio item can leave awkward leftover capacity that a different combination would have used better.
• The feasibility DP is strictly cheaper to reason about than the value-maximization DP (booleans instead of running maxima), but it answers a narrower question: it tells you whether a target is reachable, not which subset achieves it, unless you also track parent pointers or reconstruct the choice by scanning backward through the table.
• Both DP variants are pseudo-polynomial: their cost scales with the numeric capacity or target value, not just the number of items, so a very large capacity or target (in the millions) can make the DP impractical even though the item count is small; that is where a greedy approximation or a meet-in-the-middle exact method becomes attractive.

Complexity

• Value-maximization: time $O(n \cdot W)$, space $O(W)$, where n is the item count and W is the capacity.
• Feasibility: time $O(n \cdot T)$, space $O(T)$, where T is the target sum.

Edge cases

• Target or capacity of 0: dp[0]/reachable[0] are the trivial base cases (empty selection), both handled directly.
• An item heavier than the remaining capacity: naturally excluded by the descending-range guard (w - 1 lower bound), never considered for smaller capacities.
• Odd total sum in the partition-equal-subset-sum framing: no DP needed at all, an equal-value split is impossible by simple arithmetic before touching the table.

Direct answer

For the simple validity check, two pointers close in from both ends, skipping non-alphanumeric characters and comparing case-insensitively. For the harder longest-palindromic-substring problem, expand outward from every possible center, treating both single characters and the gaps between characters as centers, and keep the widest match found; this costs $O(n^2)$ in the worst case. Manacher's true $O(n)$ algorithm is worth reaching for only when that quadratic bound is actually unacceptable, such as very long strings with heavily overlapping palindromic structure, not as a default choice.

Structured elaboration

The two-pointer validity check. Move a left pointer forward and a right pointer backward, skipping past any character that is not alphanumeric on either side, then compare the two remaining characters case-insensitively; if they ever differ, the string is not a palindrome. Continue until the pointers meet or cross.

Expand-around-center for the longest substring. For every index i, expand outward twice: once treating i alone as an odd-length center, and once treating the gap between i and i+1 as an even-length center. Each expansion grows the candidate palindrome as long as its two ends keep matching, and the widest one found across all $2n$ centers is the answer. A single expansion can cost up to $O(n)$ in the worst case, for example a string of all the same character, giving $O(n^2)$ overall despite being simple to implement correctly.

When Manacher's algorithm earns its complexity. Manacher's algorithm reuses previously computed palindrome radii to avoid re-expanding centers from scratch, achieving a genuine $O(n)$ worst case, at the cost of noticeably trickier bookkeeping (a transformed string with separator characters, and mirrored-position radius reuse that is easy to get subtly wrong). It is the right choice specifically when the workload cannot tolerate the expand-around-center approach's quadratic worst case, for example, very long strings, or many repeated queries against text with heavy repeated-character structure; it is not the default first answer in an interview, where expand-around-center's simplicity and typical-case speed usually win.

Worked example

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True


def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    start, end = 0, 0

    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1

    for i in range(len(s)):
        l1, r1 = expand(i, i)
        if r1 - l1 > end - start:
            start, end = l1, r1
        l2, r2 = expand(i, i + 1)
        if r2 - l2 > end - start:
            start, end = l2, r2
    return s[start:end + 1]


if __name__ == "__main__":
    print(is_palindrome("A man, a plan, a canal: Panama"), is_palindrome("race a car"))
    print(longest_palindrome("babad"))

Running this prints True False, then bab. Note that "aba" is also a valid longest palindrome of the same length in "babad"; this particular left-to-right expand-around-center implementation returns "bab" because it is the first widest match it encounters while scanning centers left to right, not because it is the unique correct answer.

Complexity

is_palindrome (two-pointer check): time $O(n)$, one pass with two pointers closing in from both ends; space $O(1)$ extra beyond the input string itself.
longest_palindrome (expand-around-center): time $O(n^2)$ worst case, as already discussed above (up to $O(n)$ per expansion across $2n$ centers); space $O(1)$ extra, since it only tracks the best start/end indices and returns a slice, with Manacher's algorithm reaching genuine $O(n)$ time at the cost of more bookkeeping, as already discussed above.

Edge cases

• Empty string (s == ""): is_palindrome returns True immediately since left < right is never true; longest_palindrome returns "" immediately via its explicit if not s check.
• Single-character string: is_palindrome returns True immediately for the same reason (left == right already); longest_palindrome returns that single character, since a length-1 expansion around its own center is the trivial widest match.
• A string containing only non-alphanumeric characters (for is_palindrome): both pointers skip past every character without ever comparing one, and cross without finding a mismatch, so the function returns True.

Trade-offs & pitfalls

Checking only odd-length centers and skipping the even-length ones is the most common bug, and it silently misses palindromes like "abba" entirely. str.isalnum() in many languages is Unicode-aware, not limited to plain ASCII, so accented letters or other scripts may count as alphanumeric in ways that differ from what a purely ASCII-minded implementation would assume, which matters for internationalized input. Manacher's algorithm is meaningfully harder to get right than expand-around-center (the transformed-string indexing and mirror-position bookkeeping are easy to subtly break), so it should be reached for deliberately, not reflexively.

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.