Further problems

The last group on the sheet brings together four ideas that interviewers reach for once the basics are done: dynamic programming, greedy choices, searching a grid, and designing a small data structure. Interviews for SDET roles (software development engineer in test, a tester who writes code) use them to see whether you can spot a known shape in an unfamiliar problem and explain why your approach is fast enough. Each idea has a recognisable shape.

Dynamic programming: remember answers to smaller problems

Dynamic programming (DP) applies when a problem breaks into smaller versions of itself and the same smaller versions come up again and again. Climbing stairs is the first example: the ways to reach step n are the ways to reach step n - 1 plus the ways to reach step n - 2. Plain recursion on that formula recomputes the same steps over a billion times for n = 45. Storing each answer once fixes it.

There are two ways to store answers. Top down, or memoisation: keep the recursive function and cache each result. Bottom up: fill a table from the smallest case upward, so every value you need is ready. To design a DP answer, decide three things: what one entry of the table means, how an entry is built from smaller entries, and the starting values. For house robber, an entry is the best total up to a house: the better of "skip this house" and "take it plus the best total two houses back". For 2, 7, 9, 3, 1 the entries are 2, 7, 11, 11, 12, so the answer is 12 (2 + 9 + 1).

Greedy: take the best-looking step, if you can prove it is safe

A greedy algorithm makes the locally best choice at each step and never goes back. It is fast and simple, and it is correct only when you can argue that the local choice never blocks a better overall answer. The fewest jumps problem is greedy in a safe way: among the positions you can reach with k jumps, the one that reaches farthest decides the range for k + 1 jumps.

Making change shows the danger. "Largest coin first" works for most real currencies, but not for every set of coins. With coins 4, 3 and 1 and the amount 6, greedy takes 4 + 1 + 1, three coins, while 3 + 3 needs two. A DP table gets it right for any coin set:

import java.util.Arrays;

public class Main {
    // Greedy: always take the largest coin that fits. Coins sorted from large to small.
    static int greedyCoins(int[] coins, int amount) {
        int count = 0;
        for (int coin : coins) {
            count += amount / coin;
            amount %= coin;
        }
        return amount == 0 ? count : -1;
    }

    // Dynamic programming: best[a] = fewest coins for amount a, built from 0 upward.
    static int fewestCoins(int[] coins, int amount) {
        int none = Integer.MAX_VALUE;
        int[] best = new int[amount + 1];
        Arrays.fill(best, none);
        best[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a && best[a - coin] != none) {
                    best[a] = Math.min(best[a], best[a - coin] + 1);
                }
            }
        }
        return best[amount] == none ? -1 : best[amount];
    }

    public static void main(String[] args) {
        int[] coins = { 4, 3, 1 };
        System.out.println("greedy: " + greedyCoins(coins, 6));
        System.out.println("table:  " + fewestCoins(coins, 6));
    }
}

greedy: 3
table:  2

def greedy_coins(coins, amount):
    """Greedy: always take the largest coin that fits. Coins sorted from large to small."""
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1


def fewest_coins(coins, amount):
    """Dynamic programming: best[a] = fewest coins for amount a, built from 0 upward."""
    none = amount + 1
    best = [0] + [none] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                best[a] = min(best[a], best[a - coin] + 1)
    return -1 if best[amount] == none else best[amount]


coins = [4, 3, 1]
print("greedy:", greedy_coins(coins, 6))
print("table: ", fewest_coins(coins, 6))

greedy: 3
table:  2

When an interviewer asks "will greedy always work here?", try to break it with a small counterexample like this one. If you cannot find one and can explain why, greedy is probably fine; if you can, switch to DP.

Grids: flood fill and breadth-first search

A grid is a graph in disguise (a graph is a set of nodes joined by links): each cell is a node joined to its neighbours up, down, left and right. To count islands, scan the cells and start a flood fill (a search that spreads from one cell to all the cells joined to it, depth-first or breadth-first) from each unvisited land cell, marking everything it reaches. To find the fewest steps or minutes, use breadth-first search, which explores in rings of equal distance (all cells one step away, then all cells two steps away). When something spreads from several places at once, such as rot spreading from rotten oranges in the oranges problem, put all the starting cells in the queue before you begin. Mark cells as visited when you add them to the queue, so no cell is added twice, and prefer your own stack or queue over recursion for large grids.

Design problems: pick structures for each operation

Design questions (a growable list, an LRU cache, a min stack) ask for a set of operations, each with a target cost. List the operations, choose a structure that makes each one cheap, and combine structures when one is not enough. An LRU cache (a small store that keeps recent data for fast access and, when full, drops the entry that was used least recently) needs fast lookup by key (a map) and fast reordering by use (a list with links in both directions); together they make every operation constant time. A growable list doubles its storage when full, so the occasional expensive copy is spread over many cheap adds: the cost per add is constant on average, which is called amortised.

How to answer in an interview

Name the shape first: "smaller versions repeat, so DP", "spreads one step at a time, so breadth-first search", "two operations need two structures". For DP, say what one table entry means and how it is built. For greedy, say why the local choice is safe or give the counterexample. Then state the cost, for example O(amount × coins) for coin change or O(rows × cols) for a grid.

Common mistakes

• Plain recursion on a DP formula, which recomputes the same answers an exponential number of times.
• Trusting greedy without trying to break it.
• Marking grid cells as visited only when taking them out of the queue, so cells are added many times.
• Counting one minute too many in a spreading problem, or forgetting the case where nothing needs to spread.
• In design problems, forgetting that reading an entry can count as "using" it.

Recap

DP stores answers to repeated smaller problems; greedy is fine only when the local step is provably safe; grids are graphs for flood fill and breadth-first search; design problems combine structures so every operation is cheap.