Mock Week 2 — Medium Problems with an Optimization Round

Overview#

Real FAANG interviews almost always include a follow-up: "Great — can you make it faster?" or "What if the grid does not fit in memory?" Candidates who only practice the optimal solution freeze when asked to optimize live because they never built the habit of upgrading code under fresh constraints. Week 2 trains exactly that skill.

Why This Matters#

Number of Islands is among the most-asked problems globally at Meta and Amazon. Longest Increasing Subsequence appears at Google, Microsoft, Bloomberg, and ByteDance. Both have a clear brute force, an obvious optimal solution, and a meaningful third optimization — making them ideal week 2 problems.

The coding interview preparation pattern that separates "passes" from "strong hire" is: brute force, then optimal, then a volunteer optimization, then graceful follow-up handling. Candidates who only reach the first working solution miss the signal that distinguishes senior candidates from everyone else.

The week 2 target is solve 2 of 2 and deliver at least one optimization round plus handle one live follow-up per problem. This trains the conversation pattern interviewers use to rate candidates as "hire" rather than just "acceptable."

Session Structure#

Core Framework — Week 2 Problem Pairs#

# Problem 1 (Medium): Number of Islands — DFS
def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
 
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '#'
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
 
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count
 
 
# Problem 2 (Medium): LIS — O(n squared) DP
def length_of_lis_dp(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
 
 
# Optimization: O(n log n) patience sort
import bisect
 
def length_of_lis_optimal(nums):
    tails = []
    for n in nums:
        i = bisect.bisect_left(tails, n)
        if i == len(tails):
            tails.append(n)
        else:
            tails[i] = n
    return len(tails)

// Number of Islands — DFS
function numIslands(grid) {
  if (!grid || !grid.length) return 0;
  const rows = grid.length, cols = grid[0].length;
 
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '#';
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  }
 
  let count = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { dfs(r, c); count++; }
  return count;
}
 
// LIS — O(n log n) patience sort
function lengthOfLIS(nums) {
  const tails = [];
  for (const n of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < n) lo = mid + 1; else hi = mid;
    }
    tails[lo] = n;
  }
  return tails.length;
}

Time: O(R * C) for islands DFS, O(n log n) for LIS optimal Space: O(R * C) recursion stack for islands, O(n) for LIS tails array

Common Follow-Ups and Strong Answers#

Common Mistakes#

• Stopping after the first working solution without volunteering an optimization
• Memorizing the patience sort without understanding why it maintains a tails array
• Mutating the input grid in DFS without warning the interviewer first
• Forgetting to ask "may I mutate the grid?" before starting Number of Islands
• Skipping parent pointer reconstruction for the LIS follow-up

Interview Tips#

• After solving, say: "I have a working solution at O(...). Want me to try to optimize further?"
• Always volunteer the optimization even when the interviewer does not ask for it
• For Number of Islands, explicitly say "I will mark visited cells with a hash symbol — is mutating the grid acceptable?"
• For LIS, name patience sort by name to signal pattern fluency
• Treat follow-up questions as anticipated bonuses, not surprises — prepare one follow-up per problem before the session

Key Takeaways#

• Week 2 trains the brute force, then optimal, then volunteer optimization pattern
• Always offer an optimization upgrade even when the interviewer does not push for one
• Number of Islands DFS runs in O(R times C) time; Union-Find is better for streaming inputs
• LIS has two canonical solutions: O(n squared) DP and O(n log n) patience sort
• Anticipate follow-ups about memory constraints, streaming inputs, duplicates, and very large n
• Strong candidates handle one follow-up gracefully; "strong hire" candidates handle two
• Ask "may I mutate the input?" before modifying any grid problem in-place
• The optimization volunteer habit is what distinguishes "hire" from "strong hire" in interviewer feedback