Mock Week 3 — Hard Problems Under Time Pressure

Step 1 (2 min): Brute force estimate
  "I could try all subsets — that's O(2^n), too slow."

Step 2 (3 min): Pattern match
  "This looks like interval DP / sliding window / union-find..."

Step 3 (5 min): Work a small example by hand
  Draw the recursion tree or grid on paper.

Step 4 (5 min): State approach before coding
  "I'll use a monotonic stack to track..."

Step 5 (20 min): Code the solution

Step 6 (5 min): Test + trace

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0]*n for _ in range(n)]
    for length in range(2, n):
        for left in range(0, n-length):
            right = left + length
            for k in range(left+1, right):
                dp[left][right] = max(
                    dp[left][right],
                    nums[left]*nums[k]*nums[right] + dp[left][k] + dp[k][right]
                )
    return dp[0][n-1]

from collections import defaultdict, deque

def findLadders(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet: return []
    parents = defaultdict(set)
    layer = {beginWord}
    found = False
    while layer and not found:
        wordSet -= layer
        next_layer = set()
        for word in layer:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    nw = word[:i] + c + word[i+1:]
                    if nw in wordSet:
                        next_layer.add(nw)
                        parents[nw].add(word)
                        if nw == endWord: found = True
        layer = next_layer
    if not found: return []
    res = []
    def dfs(word, path):
        if word == beginWord:
            res.append(path[::-1])
            return
        for parent in parents[word]:
            dfs(parent, path + [parent])
    dfs(endWord, [endWord])
    return res