The Painting the Walls problem gives you n walls. For each wall, you can either hire a paid painter (taking time[i] hours, costing cost[i]) or use a free painter (paints 1 wall per paid hour). While the paid painter works for t hours, the free painter can paint t additional walls. Find the minimum cost to paint all n walls. This hard coding problem transforms to a 0/1 knapsack.
Media.net, Meesho, Microsoft, Meta, Amazon, and Google ask this because the problem reduces elegantly to 0/1 knapsack: selecting a subset of walls for the paid painter to handle (plus the free painter's simultaneous coverage) at minimum cost. The array and dynamic programming interview pattern is the core.
0/1 Knapsack transformation. When the paid painter paints wall i (taking time[i]), the free painter paints time[i] walls simultaneously. So painting wall i with the paid painter "covers" time[i]+1 walls total (wall i + time[i] free walls). Problem becomes: select subset of walls to assign to paid painter such that their total coverage ≥ n, minimizing total cost. dp[j] = min cost to cover j walls. For each wall i: dp[j] = min(dp[j], dp[max(0, j-(time[i]+1))] + cost[i]). Answer = dp[n].
cost=[1,2,3,2], time=[1,2,3,2]. n=4.
time[i]+1 walls, not just time[i]."Select a subset to minimize cost while satisfying a coverage constraint" is always 0/1 knapsack in disguise. The transformation: what does selecting item i "cover"? Here, it covers time[i]+1 walls. Reframing the problem explicitly as "cover n units" with knapsack is the key step. Practice identifying and applying this transformation to coverage optimization problems.