Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

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

Structured elaboration

Three structural approaches compared

Why a fixed counter's imprecision happens specifically at boundaries

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

Sharding for millions of users

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

Worked example

The two-counter sliding-window approximation, concretely:

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

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

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

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


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

Running this prints:

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

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

Complexity

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

Edge cases

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

Trade-offs & pitfalls

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

Direct answer

At millions of players with frequent score changes, you need one structure
that keeps players ordered by score (for "top K") and lets you locate any
one player's position in that order quickly (for "this player's rank").
A balanced ordered structure, a self-balancing binary search tree (BST) or
skip list augmented with subtree/level sizes, answers both queries in
$O(\log n)$ and keeps them $O(\log n)$ after every update. A plain max-heap
paired with a hashmap gives fast top-K but cannot answer "what is this
player's rank" without effectively rebuilding the ordering information the
heap does not maintain, so at scale the rank-of-player requirement is really
what decides the structure, not the update or top-K requirement alone.

Structured elaboration

Access pattern 1: top K. A max-heap answers "give me the current
maximum" in $O(1)$ and "give me the top K" in $O(K \log n)$ by popping K
times (or non-destructively in $O(K)$ if paired with a sorted auxiliary
structure). A rank-augmented balanced BST answers top K in
$O(K + \log n)$: descend to the maximum in $O(\log n)$, then walk K steps
in sorted order.

Access pattern 2: rank of a specific player. This is where the two
choices diverge sharply. A rank-augmented balanced BST, where every node
additionally stores the size of its subtree, answers "how many players
have a score greater than or equal to this player's score" in $O(\log n)$:
descend toward the player's node, and at each step where you branch toward
the smaller-score side, add the size of the larger-score subtree you did not
descend into. A plain heap stores no such ordering information between
siblings, so answering "what is player X's rank" requires either an
$O(n)$ scan, or maintaining a second, separate rank-capable structure
alongside the heap, at which point you have effectively built the augmented
BST's capability anyway, just split across two data structures instead of
one.

Update cost. Both approaches update a single player's score in
$O(\log n)$: a balanced BST re-inserts (remove old score, insert new
score, both $O(\log n)$); a heap paired with a hashmap can decrease/increase
a key via the hashmap's stored heap-index and a sift-up/sift-down, also
$O(\log n)$, provided the heap implementation supports arbitrary-key
updates (a plain textbook binary heap does not expose this directly and
needs an index-tracking layer bolted on).

A real-world instance of the same trade-off: production leaderboards
(for example, Redis's sorted set) are implemented as exactly this kind of
augmented ordered structure, most commonly a skip list (a probabilistic,
linked-list-based structure with multiple "levels" that let a search skip
over many elements at once) paired with a hashmap from member to score, which
is precisely "balanced ordered structure for rank and range, hashmap for O(1)
point lookup of a player's current score," the two pieces used together
rather than as alternatives.

Recommendation. For a leaderboard with millions of players that must
answer both queries frequently, use the balanced ordered structure (skip
list or an augmented balanced BST) as the source of truth for ordering, plus
a hashmap from player id to score for O(1) "what is player X's current
score" lookups; this covers both access patterns at $O(\log n)$ without
needing a second ordering structure bolted onto a heap. A heap-only design
is the right choice only when the product genuinely never needs
rank-of-player, just periodic top-K snapshots (for example, a "top 10 today"
banner with no per-player rank display).

Worked example

A compact way to demonstrate the rank-of-player query concretely: represent
scores with a Fenwick tree (a Binary Indexed Tree, the same cumulative-count
structure used for range-sum queries) over a coordinate-compressed set of
score values, counting how many players currently hold each score, so
"rank of player X" becomes "how many players have score greater than or
equal to X's score," a suffix-count query.

import bisect

class RankLeaderboard:
    def __init__(self, score_universe):
        self.sorted_scores = sorted(set(score_universe))
        self.S = len(self.sorted_scores)
        self.bit = [0] * (self.S + 1)
        self.player_score = {}

    def _bucket(self, score):
        return bisect.bisect_left(self.sorted_scores, score) + 1

    def _add(self, i, delta):
        while i <= self.S:
            self.bit[i] += delta
            i += i & (-i)

    def _prefix(self, i):
        total = 0
        while i > 0:
            total += self.bit[i]
            i -= i & (-i)
        return total

    def set_score(self, player, score):
        if player in self.player_score:
            self._add(self._bucket(self.player_score[player]), -1)
        self._add(self._bucket(score), 1)
        self.player_score[player] = score

    def rank_of(self, player):
        bucket = self._bucket(self.player_score[player])
        return self._prefix(self.S) - self._prefix(bucket - 1)

board = RankLeaderboard(range(0, 101))
scores = {"alice": 90, "bob": 75, "carol": 90, "dave": 60, "eve": 100}
for p, s in scores.items():
    board.set_score(p, s)
for p in scores:
    print(p, board.rank_of(p))
board.set_score("dave", 95)
print("dave new rank:", board.rank_of("dave"))

Output (verified by running this exact code):

alice 3
bob 4
carol 3
dave 5
eve 1
dave new rank: 2

alice and carol tie at rank 3 (three players, eve, alice, carol,
have a score of 90 or above); after dave jumps to 95, only eve (100) and
dave (95) score 95 or above, so dave's rank becomes 2. Both results were
cross-checked against a brute-force sum(1 for s in scores.values() if s >= my_score)
recomputation with no mismatches.

Trade-offs & pitfalls

• The Fenwick-tree version above assumes a bounded, known (or periodically
  refreshed) universe of possible score values to bucket into; a truly
  unbounded, continuously-varying score range needs an augmented balanced
  BST or skip list instead, since those do not require pre-declaring the
  value universe.
• A common wrong turn is reaching for "just a heap" because top-K sounds
  heap-shaped, without checking whether the product also needs
  rank-of-player; that second requirement is usually what should decide the
  structure, since retrofitting rank support onto a heap-based design later
  is close to a rewrite.
• The same rank-plus-priority composition appears in a CI (continuous
  integration) test-scheduler: add, cancel, and promote a queued test
  along with "get the current top-K highest-priority tests," which is the
  identical requirement (ordered structure for priority/rank, hashmap for
  O(1) lookup of a specific test's current state) applied to test scheduling
  instead of player scores.
• At true internet scale, sharding by score range (so each shard owns a
  contiguous score band) reduces write contention, but complicates
  "global" top-K and rank queries, which now need to merge results across
  shards; this is a genuine added cost of horizontal scaling that a
  single-machine design does not have to pay.

Complexity

The table above already gives the general balanced-BST-vs-heap comparison. For the
RankLeaderboard Fenwick-tree worked example specifically, with $S$ the size of the
(coordinate-compressed) score universe and $P$ the number of distinct players tracked:
set_score: $O(\log S)$, two Fenwick point-updates (_add); rank_of: $O(\log S)$,
two Fenwick prefix-sum queries (_prefix); space: $O(S + P)$, the bit array is sized to
the score universe and player_score holds one entry per player.

Edge cases

• Player never scored: rank_of(player) looks up self.player_score[player] directly
  and raises a KeyError if set_score was never called for that player.
• Score above the declared universe: _bucket returns self.S + 1 for a score above every
  value in sorted_scores; _add(self.S + 1, delta)'s while i <= self.S condition is false
  on the first check, so the update is silently a no-op, meaning out-of-universe high scores
  are dropped rather than rejected with an error.
• Tied scores: players sharing a score land in the same bucket and are counted together in
  the suffix sum, so ties correctly share the same rank number, as shown for alice and
  carol both ranking 3rd in the worked example.
• Empty leaderboard: with no set_score calls made yet, rank_of on any player raises a
  KeyError immediately, since player_score is still empty.

Direct answer

Preorder visits node, then left, then right; inorder visits left, then node, then right; postorder visits left, then right, then node; all three are depth-first traversals (DFS), following one branch as deep as possible before backtracking. Level-order (breadth-first search, BFS) instead visits every node one full depth at a time using a queue. To reconstruct a tree from a serialized form, preorder combined with explicit null markers is the natural single-pass choice, because each value tells you exactly where to place it in the recursion without needing a second array to cross-reference.

Structured elaboration

Recursive versus iterative cost. A recursive traversal uses the call stack, which costs $O(h)$ space where h is the tree's height ($O(\log n)$ for a balanced tree, $O(n)$ worst case for a completely skewed one). An iterative version with an explicit stack (for the depth-first orders) or queue (for level order) has the same asymptotic space cost, but it avoids the recursion-depth limits some language runtimes impose, which matters for very deep, skewed trees.

Level order grouped by depth. Enqueue the root, then repeatedly record the queue's current size before draining exactly that many nodes: that snapshot is what lets you know where one depth level ends and the next begins, since each drained node's children get enqueued for the following level.

Choosing preorder-with-nulls for reconstruction. Preorder plus null sentinels needs only one traversal: read a value, recursively build its left child from what follows, then its right child, treating a null marker as "no subtree here." Preorder plus inorder (without nulls) also works, but only if all values are unique, and it needs an auxiliary index map over the inorder sequence to avoid an $O(n^2)$ naive search, adding bookkeeping the null-marker approach does not need. Level order with null markers is workable too (BFS serialization), but reconstructing parent-child links across levels needs more bookkeeping than the purely recursive preorder approach.

Related extensions from the same traversal family. A BST iterator (an object that exposes a paused, resumable inorder walk) keeps the explicit stack alive across calls instead of finishing the traversal eagerly, giving amortized (averaged over a sequence of operations) $O(1)$ time per next() call. Finding all node pairs at distance k from a target reuses the same level-by-level machinery as level-order traversal, just starting the breadth-first search from the target node instead of the root. The height-balance check, maximum path sum, and invert-binary-tree problems are all further applications of the postorder shape: each recursive call computes something (a height, a best path so far, a swapped subtree) from its children and returns it up to its parent, rather than printing a value as it visits.

graph TD
  A[3] --> B[9]
  A --> C[20]
  C --> D[15]
  C --> E[7]

Worked example

from collections import deque


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


def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_vals = []
        for _ in range(len(queue)):  # freeze this level's size before draining
            node = queue.popleft()
            level_vals.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_vals)
    return result


if __name__ == "__main__":
    root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(level_order(root))

Running this on the tree pictured above prints [[3], [9, 20], [15, 7]].

Complexity

Time: $O(n)$ for all four traversals (preorder, inorder, postorder, and level-order), since each one visits every node exactly once and does $O(1)$ work per visit.
Space: $O(h)$ for the three depth-first traversals, from the recursion call stack (or an explicit stack for an iterative version), where h is the tree's height, as already noted above. The level-order queue never holds more nodes than one full level of the tree, which is at most $O(n)$ in the worst case (a wide, shallow tree).

Edge cases

• Empty tree (root is None): level_order already returns [] via its explicit check; the depth-first traversals equally return immediately for a None node.
• Single-node tree: all four traversals visit just that one node and produce a single-element result.
• A skewed (essentially linear) tree: recursive depth-first traversals can hit a language's default recursion-depth limit (for example, Python's default is around 1000 frames), which is a concrete argument for the iterative forms in production code.

Trade-offs & pitfalls

The most common bug in the level-order implementation is not snapshotting len(queue) before the inner loop starts; without that snapshot, nodes from the next level get enqueued and then immediately drained in the same pass, smearing two levels together.

Direct answer

A disjoint-set (union-find) structure represents each group as a tree, where every element points to a parent and the root is the group's representative; "same group" is answered by walking both elements up to their roots and comparing, and "merge" is answered by pointing one root at the other. Union by rank keeps those trees shallow in the first place, and path compression flattens a tree every time you walk it, so together the trees stay so flat that both operations run in what is, for any practical input size, effectively constant time.

Structured elaboration

Each element starts as its own group (its own root). Two operations:

• find(x): follow x's parent pointers up to the root of its tree; that root identifies the group.
• union(a, b): find both roots; if they differ, attach one root under the other, merging the two trees into one.

What union by rank contributes on its own: always attach the shorter tree under the taller one's root (tracked by a rank estimate, not the exact height). This alone caps every tree's height at $O(\log n)$, because a tree can only grow taller by merging with another tree of at least equal height, which at minimum doubles its size, so height can double only $\log n$ times. Without path compression, find on such a tree costs $O(\log n)$.

What path compression contributes on its own: every time find(x) walks up to the root, repoint every node on that path directly to the root. This flattens the tree along exactly the paths that get queried. Used alone (without union by rank), the classical result (Tarjan and van Leeuwen) is that a sequence of operations still costs only $O(\log n)$ amortized per operation, because repeated queries on the same region keep flattening it further.

Combined: the two heuristics interact so that the amortized cost per operation in a sequence of $m$ operations on $n$ elements is:

where $\alpha(n)$ is the inverse Ackermann function: it grows so slowly that $\alpha(n) \le 4$ for any $n$ up to sizes far beyond anything a real system would hold, so the bound is, for practical purposes, constant time per operation. This tighter bound (Tarjan's result) is strictly better than either heuristic's individual $O(\log n)$ bound, which is why interviewers ask for both.

Worked example

class DisjointSet:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra              # union by rank
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True


ds = DisjointSet(6)  # elements 0..5
for a, b in [(0, 1), (1, 2), (3, 4)]:
    ds.union(a, b)
print([ds.find(x) for x in range(6)])
print(ds.find(2) == ds.find(0))
print(ds.find(3) == ds.find(5))
ds.union(2, 3)
print(ds.find(5) == ds.find(0))
print(ds.find(4) == ds.find(0))

Running this prints:

[0, 0, 0, 3, 3, 5]
True
False
False
True

After the first three unions, elements 0, 1, 2 share root 0 and elements 3, 4 share root 3 (5 stands alone), matching the printed parent list. After union(2, 3), groups {0,1,2} and {3,4} merge, so 0 and 4 report the same root while 5 remains separate.

Trade-offs & pitfalls

A disjoint-set structure only answers connectivity, not path reconstruction: it cannot tell you the sequence of edges between two elements the way a breadth-first search (BFS, a graph traversal that explores nodes level by level) tree can, so if a caller needs the actual path, this is the wrong structure. It also has no built-in support for splitting a group back apart (undoing a union); if you need rollback, either use union by rank without path compression (so you can reverse exactly the pointer changes you made) or keep an explicit undo log of the parent and rank values you overwrote. Real systems reach for union-find well beyond one domain: cycle detection while building an undirected graph (an edge closes a cycle exactly when its two endpoints already share a root), counting connected components (the number of distinct roots after all unions), Kruskal's minimum-spanning-tree algorithm, and dynamic connectivity checks in build or dependency graphs, wherever "are these already linked" needs to be asked repeatedly as links are added.

Edge cases

• Out-of-range index: find and union do not validate their input; calling either with an index outside [0, n) indexes past the end of self.parent/self.rank and raises an IndexError rather than failing gracefully.
• Self-union (union(a, a)): find(a) == find(a) always holds, so ra == rb is true and union returns False immediately with no parent-pointer changes; unioning an element with itself is always a safe no-op.
• n=0: DisjointSet(0) builds empty parent/rank lists, so any subsequent find or union call has no valid index to operate on and raises an IndexError, the same as any other out-of-range call.

Direct answer

Before writing any code, look for two structural signals: does the problem have overlapping subproblems and optimal substructure (an optimal solution is built from optimal solutions to smaller versions of itself)? If yes, it is a dynamic programming (DP) problem, not a greedy one. Within DP, whether you reach for memoization (caching recursive-call results, computed top-down) or tabulation (filling a table iteratively, bottom-up) is a secondary implementation choice, not a correctness question: both compute the same recurrence.

Structured elaboration

Signal 1: does a locally optimal choice guarantee a globally optimal one? Greedy algorithms make one irrevocable choice at each step and never reconsider it. That is only correct when the problem has the "greedy-choice property": committing to the best-looking option right now cannot make the final answer worse. You test this by trying to construct a counterexample where the locally-best choice forecloses a better global outcome (an exchange argument): if you can build one, greedy is wrong and you need DP; if every attempt to build a counterexample fails and you can sketch why (an exchange argument that any optimal solution can be rearranged to match the greedy choice without loss), greedy is likely correct.

Signal 2: overlapping subproblems and optimal substructure. If solving the problem for a larger input naturally requires solving the same smaller subproblem many times (for example, "the best way to reach state k" depends on "the best way to reach state k-1", but state k-1 also gets asked about from other paths), you have overlapping subproblems. If, in addition, an optimal solution to the whole problem is composed of optimal solutions to its subproblems (no locally-suboptimal subproblem answer can still lead to a globally optimal whole), you have optimal substructure. Both together mean DP applies: cache each subproblem's answer once, reuse it everywhere it recurs.

Signal 3: what does the recurrence look like? Write the recurrence in terms of "the answer for state X depends on the answer for smaller states Y, Z, ...", before touching code. If you can write this recurrence but it does not have an ordering where "smaller" always resolves before "larger" (a genuine dependency cycle), you likely need a different technique entirely (graph shortest-path with cycles, for instance).

Once you know it's DP: memoization vs tabulation. These are the same recurrence expressed two ways, not two different algorithms:

Worked example

Take "minimum coins to make amount 6 from denominations {1, 3, 4}" (the coin change problem). The recurrence is: minCoins(a) = 1 + min(minCoins(a - c) for c in coins if c <= a), with minCoins(0) = 0. Overlapping subproblems are visible immediately: computing minCoins(6) needs minCoins(5), minCoins(3), minCoins(2); computing minCoins(5) also needs minCoins(2). minCoins(2) gets requested from two different callers, so caching it once and reusing it is exactly what turns an exponential naive recursion into a linear-in-target one. That overlap is the tell that this is DP, not greedy: a greedy "always take the largest coin" would take 4 then 1 then 1 (3 coins), while the true optimum is 3 + 3 (2 coins), because taking the largest coin first forecloses the better pairing, a real exchange-argument counterexample, confirming greedy is unsafe here and DP (with either memoization or tabulation) is required.

Trade-offs & pitfalls

Key points

• The most common mistake is reaching for greedy because a locally-best choice feels right; the discipline is to actively try to break it with a counterexample before trusting it, not to trust it by default.
• A DP recurrence existing does not by itself tell you whether to memoize or tabulate; that choice depends on whether the reachable state space is sparse (favors memoization) or dense with a clean iteration order (favors tabulation), and on language-specific recursion-depth limits.
• Some problems only look like DP: if there is no genuine overlap (each subproblem is only ever needed once), plain recursion or divide-and-conquer is simpler and DP's caching buys you nothing.

Complexity

• These are meta-level signals, not a specific algorithm, so there is no single complexity here; once you commit to DP, complexity is (number of distinct states) times (work per state), whether computed top-down with a cache or bottom-up with a table.

Edge cases

• A problem with optimal substructure but no overlapping subproblems (each subproblem solved once) does not need DP's memoization; plain recursion or divide-and-conquer suffices and adding a cache only adds overhead.
• A problem where you cannot write a clean dependency order for tabulation (irregular, data-dependent state transitions) may force memoization even in a dense-looking state space, since an explicit iteration order is hard to construct correctly.