Mock Week 3 — Hard Problems Under Time Pressure

Overview#

Hard problems do appear in FAANG loops, especially at senior and staff levels. Even at entry-level L4 and E4, one of the four coding rounds may include a hard problem. The difference between candidates who pass and candidates who fail is not raw intelligence — it is the protocol they follow when blocked.

Why This Matters#

Burst Balloons and Word Ladder II are canonical hard problems used by Google, Meta, Amazon, and Bloomberg. Burst Balloons trains the "think in reverse" interval DP insight. Word Ladder II trains BFS layered traversal combined with path reconstruction — two skills that compose into a hard solution neither can achieve alone.

The week 3 target is to solve 1.5 of 2: one full solution plus one partial with a clear discussion. Candidates who can talk through being stuck and produce partial code outperform 80 percent of candidates who freeze silently when they hit a wall.

In 2026, FAANG coding interviews are reasoning tests as much as algorithm tests. Showing structured thinking on a problem you cannot fully solve scores better than correctly solving a problem you never explain.

Session Structure#

Core Framework — Week 3 Hard Problem Pairs#

# Burst Balloons — Interval DP O(n cubed)
def max_coins(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]
 
 
# Word Ladder II — BFS + parent map + DFS reconstruction
from collections import defaultdict
 
def find_ladders(begin_word, end_word, word_list):
    word_set = set(word_list)
    if end_word not in word_set:
        return []
    parents = defaultdict(set)
    layer = {begin_word}
    found = False
    while layer and not found:
        word_set -= 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 word_set:
                        next_layer.add(nw)
                        parents[nw].add(word)
                        if nw == end_word:
                            found = True
        layer = next_layer
    if not found:
        return []
    res = []
 
    def dfs(word, path):
        if word == begin_word:
            res.append(path[::-1])
            return
        for parent in parents[word]:
            dfs(parent, path + [parent])
 
    dfs(end_word, [end_word])
    return res

// Burst Balloons
function maxCoins(nums) {
  const arr = [1, ...nums, 1];
  const n = arr.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let length = 2; length < n; length++) {
    for (let left = 0; left + length < n; left++) {
      const right = left + length;
      for (let k = left + 1; k < right; k++) {
        dp[left][right] = Math.max(
          dp[left][right],
          arr[left] * arr[k] * arr[right] + dp[left][k] + dp[k][right]
        );
      }
    }
  }
  return dp[0][n - 1];
}
 
// Word Ladder II
function findLadders(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return [];
  const parents = new Map();
  let layer = new Set([beginWord]);
  let found = false;
  while (layer.size && !found) {
    for (const w of layer) wordSet.delete(w);
    const nextLayer = new Set();
    for (const word of layer) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const nw = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (wordSet.has(nw)) {
            nextLayer.add(nw);
            if (!parents.has(nw)) parents.set(nw, new Set());
            parents.get(nw).add(word);
            if (nw === endWord) found = true;
          }
        }
      }
    }
    layer = nextLayer;
  }
  if (!found) return [];
  const res = [];
  function dfs(word, path) {
    if (word === beginWord) { res.push([...path].reverse()); return; }
    for (const p of parents.get(word) || []) dfs(p, [...path, p]);
  }
  dfs(endWord, [endWord]);
  return res;
}

Time: O(n cubed) for Burst Balloons, O(N * L squared * 26) for Word Ladder II Space: O(n squared) for DP table, O(N * L) for parent map

The Stuck-Recovery Protocol#

If blocked after 10 minutes, follow this sequence:

1. Say it aloud: "I am thinking interval DP, but I am not certain about the state definition."
2. Ask for a hint direction: "Would it help to think about which balloon bursts last rather than first?"
3. Reduce the problem: "Let me work through what the answer would be with only 3 elements."
4. Code the brute force: O(2 to the n) backtracking earns partial credit and often reveals the DP structure.

Hard Problem Pattern Cheatsheet#

Common Mistakes#

• Trying to solve hard problems entirely in your head without a worked example on paper
• Coding a brute force hastily without thinking through the recursion — leads to structural bugs
• For Burst Balloons: picking k as the first balloon burst (lacks optimal substructure)
• For Word Ladder II: building full paths inside BFS instead of recording parents (memory explosion)
• Going silent for more than 60 seconds when stuck rather than narrating the stuck state

Interview Tips#

• Always work a small concrete example on paper or whiteboard before typing any code
• Verbalize when you are stuck — "I am thinking X but I am not sure if it has optimal substructure" scores better than silence
• Offer the brute force first if the optimal approach does not come within 10 minutes
• Hard problems reward partial credit — finish what you can and describe the rest
• Practice one hard problem per week between mock sessions to build intuition across pattern types

Key Takeaways#

• Hard problems reward inversion: Burst Balloons key insight is choosing k as the last balloon, not the first
• Word Ladder II key insight is BFS with a parent map, then DFS to reconstruct paths only at the end
• The stuck-recovery protocol is: say it, ask hint direction, reduce to smaller input, code brute force
• Partial credit is real — a narrated brute force with clear intent outscores a silent optimal attempt
• The pattern cheatsheet maps problem signals to algorithm families — memorize the 8 key mappings
• Week 3 target is solve 1.5 of 2 with continuous communication throughout
• In 2026, FAANG interviews are reasoning tests — structured thinking on hard problems scores higher than silent code
• Preparing one hard problem per week between sessions builds the intuition necessary for week 4 company simulations