Mock Week 2 — Medium Problems with Optimization Round

Week 2 Goals

• Solve both problems correctly
• After each solution, optimize (better time or space)
• Handle at least one interviewer follow-up
• Finish under 45 min each

Session A — Graphs + DP

Problem 1 (Medium): Number of Islands

Round 1 — DFS solution:

def numIslands(grid):
    def dfs(r, c):
        if r<0 or r>=len(grid) or c<0 or c>=len(grid[0]) 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(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                dfs(r,c)
                count += 1
    return count

Interviewer follow-up: "What if the grid is massive and doesn't fit in memory?" Your answer: "I'd use Union-Find with streaming rows — process row by row, union with adjacent cells from the previous row."

Problem 2 (Medium): Longest Increasing Subsequence

Round 1 — O(n²) DP:

def lengthOfLIS(nums):
    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)

Round 2 — Optimize to O(n log n):

import bisect
def lengthOfLIS(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)

Interviewer follow-up: "Can you reconstruct the actual subsequence?" Your answer: "Store predecessor array during the O(n²) pass. Trace back from the max dp index."

Common Follow-Up Questions & Answers

Optimization Mindset

After every solution, ask yourself:

1. Can I reduce time? (Better data structure, math insight, amortised ops)
2. Can I reduce space? (In-place, two pointers, rolling array for DP)
3. Can I simplify code? (Built-in functions, shorter loops)