DSA interview question

Ninja's Training

Medium · Algorithms · Topics: dynamic programming, matrix

The problem

You're building a fitness-gamification app where a ninja trains for n days. Each day, the ninja can perform exactly one of three activities — running, fighting practice, or swimming — and earns a certain number of merit points based on which activity they choose that day. The catch: the ninja cannot perform the same activity on two consecutive days (to avoid overtraining one muscle group). Your task: given the merit points for each activity on each day, find the maximum total merit points the ninja can earn over all n days.

Example: for 3 days with points Day 0: [10, 40, 70] Day 1: [20, 50, 80] Day 2: [30, 60, 90] Best strategy: Day 0 → activity 2 (70), Day 1 → activity 1 (50), Day 2 → activity 2 (90) = 210.

Function signature

int ninjaTraining(int n, vector<vector<int>>& points);
// points[day][activity], activity in {0, 1, 2}

Test cases

Input `points`	n	Output	Explanation
`[[10,40,70],[20,50,80],[30,60,90]]`	3	210	Day0→2(70), Day1→1(50), Day2→2(90)... wait must alternate, verify with code
`[[1,2,5],[3,1,1],[3,3,3]]`	3	11	Day0→2(5), Day1→0(3), Day2→any except 0, best is 3
`[[10,50,1]]`	1	50	Single day, just pick the max
`[[1,1,1],[1,1,1]]`	2	2	Forced to alternate, all equal, sum = 2
`[[100,0,0],[0,100,0],[0,0,100]]`	3	300	Perfectly alternating best activities each day

(Confirm: exactly 3 activities per day; the very first day has no "previous day" restriction.)

How interviewers phrase it

"A person does one of three tasks each day and earns points based on the task. They can't repeat the same task on two consecutive days. Maximize total points over n days."
This is a well-known DP pattern problem, often introduced as "maximum merit points" or "day-wise activity selection with a no-repeat constraint".
Sometimes disguised as "house painting with 3 colors, no two adjacent houses same color, minimize/maximize cost" — same underlying structure (this is literally a variant of "Paint House").

Clarifying questions to ask

Is the constraint strictly "not the same activity as the immediately previous day," or could it be a longer no-repeat window (e.g., not in the last 2 days)? Confirm it's just the immediate previous day.
Is there always exactly 3 activities per day, or could this generalize to k activities? (Affects whether I hardcode 3 or write a generalized loop.)
On day 0, is there truly no restriction (since there's no "previous day")?
Are points guaranteed non-negative? Could n be 0 (edge case to handle)?
Do I need to return the sequence of activities chosen, or just the maximum total points?

Follow-ups to expect

"Can you generalize this to k activities instead of exactly 3?"
"Can you reduce space to O(1) beyond the input?"
"Can you reconstruct which activities were chosen each day?"
"How does this relate to 'Paint House' (LeetCode 256)?"
"What if there's also a constraint on total number of times each activity can be performed?"
"What if the same activity is disallowed for 2 consecutive days, not just 1?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview