DSA Patterns Made Simple · Heaps, Backtracking and Dynamic Programming

Capstone: A Mock Coding Round

Three unseen problems in interview conditions. For each one, name the pattern, explain your plan out loud, code it, and test edge cases, then compare with the model answers and rubric.

Create a free account to save this page, take notes and track your progress. Sign in

How this round works

Set a timer for 45 minutes for all three problems, as in a real interview loop. For each problem:

Say (or write) the pattern you'd use and why in one or two sentences.
Write the brute force idea in one line, then your faster plan and its Big O.
Code it in the playground in Python or JavaScript.
Test it with a normal case and two edge cases.

Then open each question below to compare with the model answer, and check yourself against the rubric.

Problem 1: Ransom note (easy)

Given note and magazine strings, can the note be built by cutting letters out of the magazine (each letter used once)? ("aa", "aab") → true, ("aa", "ab") → false.

Problem 2: Maximum average of k consecutive days (easy–medium)

Given daily sales and k, return the highest average over any k consecutive days. ([1, 12, -5, -6, 50, 3], 4) → 12.75.

Problem 3: Rotting oranges (medium)

In a grid, 2 is a rotten orange, 1 a fresh one, 0 empty. Every minute, fresh oranges next to rotten ones (up/down/left/right) become rotten. How many minutes until none are fresh, or −1 if some never rot?

2 1 1
1 1 0
0 1 1      -> 4 minutes

Check your solutions

Model answers to test againstTry it yourself

from collections import Counter, deque


def can_construct(note, magazine):
    need = Counter(note)            # counting pattern
    have = Counter(magazine)
    return all(have[ch] >= n for ch, n in need.items())


def max_average(sales, k):
    window = sum(sales[:k])         # fixed-size sliding window
    best = window
    for i in range(k, len(sales)):
        window += sales[i] - sales[i - k]
        best = max(best, window)
    return best / k


def minutes_to_rot(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))    # multi-source BFS: start from every rotten orange
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1


print(can_construct("aa", "aab"), can_construct("aa", "ab"))
print(max_average([1, 12, -5, -6, 50, 3], 4))
print(minutes_to_rot([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
print(minutes_to_rot([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))

from collections import Counter, deque

def can_construct(note, magazine):
    need = Counter(note)            # counting pattern
    have = Counter(magazine)
    return all(have[ch] >= n for ch, n in need.items())

def max_average(sales, k):
    window = sum(sales[:k])         # fixed-size sliding window
    best = window
    for i in range(k, len(sales)):
        window += sales[i] - sales[i - k]
        best = max(best, window)
    return best / k

def minutes_to_rot(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))    # multi-source BFS: start from every rotten orange
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

print(can_construct("aa", "aab"), can_construct("aa", "ab"))
print(max_average([1, 12, -5, -6, 50, 3], 4))
print(minutes_to_rot([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
print(minutes_to_rot([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))

Output

True False
12.75
4
-1

Model answers to test againstTry it yourself

function canConstruct(note, magazine) {
  const have = new Map();               // counting pattern
  for (const ch of magazine) have.set(ch, (have.get(ch) ?? 0) + 1);
  for (const ch of note) {
    if (!have.get(ch)) return false;
    have.set(ch, have.get(ch) - 1);
  }
  return true;
}

function maxAverage(sales, k) {
  let window = sales.slice(0, k).reduce((a, b) => a + b, 0);   // fixed-size sliding window
  let best = window;
  for (let i = k; i < sales.length; i++) {
    window += sales[i] - sales[i - k];
    best = Math.max(best, window);
  }
  return best / k;
}

function minutesToRot(grid) {
  const rows = grid.length, cols = grid[0].length;
  let frontier = [], fresh = 0, minutes = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) frontier.push([r, c]);   // multi-source BFS: start from every rotten orange
      else if (grid[r][c] === 1) fresh++;
    }
  }
  while (frontier.length && fresh) {
    const next = [];
    for (const [r, c] of frontier) {
      for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          next.push([nr, nc]);
        }
      }
    }
    frontier = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

const py = (b) => (b ? "True" : "False");
console.log(py(canConstruct("aa", "aab")), py(canConstruct("aa", "ab")));
console.log(maxAverage([1, 12, -5, -6, 50, 3], 4));
console.log(minutesToRot([[2, 1, 1], [1, 1, 0], [0, 1, 1]]));
console.log(minutesToRot([[2, 1, 1], [0, 1, 1], [1, 0, 1]]));

function canConstruct(note, magazine) {
  const have = new Map();               // counting pattern
  for (const ch of magazine) have.set(ch, (have.get(ch) ?? 0) + 1);
  for (const ch of note) {
    if (!have.get(ch)) return false;
    have.set(ch, have.get(ch) - 1);
  }
  return true;
}

function maxAverage(sales, k) {
  let window = sales.slice(0, k).reduce((a, b) => a + b, 0);   // fixed-size sliding window
  let best = window;
  for (let i = k; i < sales.length; i++) {
    window += sales[i] - sales[i - k];
    best = Math.max(best, window);
  }
  return best / k;
}

const py = (b) => (b ? "True" : "False");
console.log(py(canConstruct("aa", "aab")), py(canConstruct("aa", "ab")));
console.log(maxAverage([1, 12, -5, -6, 50, 3], 4));
console.log(minutesToRot([[2, 1, 1], [1, 1, 0], [0, 1, 1]]));
console.log(minutesToRot([[2, 1, 1], [0, 1, 1], [1, 0, 1]]));

Output

True False
12.75
4
-1

What's next

Do one problem a day with Problem of the day.
Work through the Coding Interview lists by pattern.
Test the theory with the Data Structures & Algorithms quiz.

Deliverables

Problem 1, Ransom note: what's your pattern, plan and complexity?

Model answer

Counting: count the magazine's letters, then for each letter of the note decrement its count, failing if it's missing or zero (or compare two Counters). O(n + m) time, O(k) space for k distinct letters.

Rubric

Strong answer: names the counting pattern, mentions each letter can be used once (so counts, not a set), handles an empty note (true) and a longer note than magazine (fast false), and gives O(n + m). Weak answer: sorts both strings or uses nested loops without discussing complexity.

Problem 2, Maximum average of k consecutive days: what's your pattern, plan and complexity?

Model answer

Fixed-size sliding window: sum the first k days, then slide one day at a time, adding the new day and subtracting the day that falls out, tracking the best sum. Divide by k at the end. O(n) time, O(1) space.

Rubric

Strong answer: recognises 'consecutive' as a window, avoids re-summing each window (which is O(n·k)), handles negative numbers correctly (fine for a fixed window), divides once at the end, and asks about k > n. Weak answer: nested loops summing every window.

Problem 3, Rotting oranges: what's your pattern, plan and complexity?

Model answer

Multi-source BFS: put every rotten orange in the queue at minute 0 and count fresh oranges. Process the queue level by level (one level = one minute), rotting fresh neighbours and decrementing the fresh count. When the queue empties, return the minutes if no fresh oranges remain, else −1. O(rows × cols).

Rubric

Strong answer: explains why BFS (spreading in rounds = levels), starts from all rotten oranges at once, counts fresh oranges to detect the −1 case, and handles 'no fresh oranges at the start' (0 minutes). Weak answer: runs a separate BFS from each rotten orange, or uses DFS, which doesn't model time correctly.

Open in the app to mark lessons complete, take notes and track your progress.