LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

LinkedIn SWE interview that went deep into dynamic programming, specifically the house painting / color assignment problem. They wanted both a top-down memoized solution and a space-optimized bottom-up version, plus path reconstruction. More involved than I expected for a single question.

Questions Asked (1)

Given H items arranged in a line and an H×C cost matrix where cost[i][c] is the cost of assigning color c to item i, design a solution that finds the minimum total cost to color all items such that no two adjacent items share the same color. Implement both a top-down recursive approach with memoization and a space-optimized bottom-up DP. Also reconstruct one valid optimal coloring.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is basically the paint house problem but generalized to C colors.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by defining the DP state: dp[i][c] = min cost to color items i..H-1 given item i has color c. Then present both top-down memoization and bottom-up space-optimized DP, and finally show how to reconstruct the coloring using parent pointers or by re-deriving choices.

Pro tip: Emphasize the space optimization: since dp[i] depends only on dp[i+1], you can reduce space from O(H*C) to O(C) while still reconstructing the solution by storing choices or using a backward pass.

1. Define the DP state and recurrence

Clearly state dp[i][c] as the minimum cost to color items i through H-1 with item i assigned color c. Write the recurrence: dp[i][c] = cost[i][c] + min_{c' != c} dp[i+1][c'].

2. Implement top-down with memoization

Use recursion with a memo table (H x C) to avoid recomputation. Base case: i == H returns 0. For each state, iterate over all colors except c to find the minimum.

3. Implement bottom-up space-optimized DP

Iterate i from H-1 down to 0, maintaining only the next row's dp values. For each color c, compute dp[i][c] using the minimum of the next row excluding c. Track the overall minimum at i=0.

4. Reconstruct one optimal coloring

During bottom-up, store the chosen color for each i and c (or recompute by comparing costs). Then backtrack from i=0 to H-1 to output the color sequence.

5. Analyze time and space complexity

Time: O(H * C^2) naive, but can be optimized to O(H * C) by tracking the two smallest values in the next row. Space: O(H*C) for top-down, O(C) for bottom-up with reconstruction.

Key Points to Mention

DP state definition and recurrence relation
Top-down memoization vs bottom-up DP trade-offs
Space optimization from O(H*C) to O(C)
Reconstruction of the optimal coloring using parent pointers or backward pass
Time complexity optimization to O(H*C) by tracking two smallest costs
Handling edge cases: H=0, C=1, and large inputs

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.