Maximum Points Tourist Can Earn

Maximum Points Tourist Can Earn

1. What is this problem about?

The Maximum Points Tourist Can Earn interview question is a dynamic programming problem set in a travel context. A tourist is visiting n cities over k days. On each day, the tourist can either stay in their current city to earn points or travel to a neighboring city. Traveling might also earn points or have a cost (negative points). Given the points earned in each city on each day and the travel connections, the goal is to find the maximum total points the tourist can collect starting from any city and ending anywhere after k days.

This is essentially a path optimization problem on a graph where the rewards change over time (day by day).

2. Why is this asked in interviews?

Companies like DE Shaw ask the Maximum Points Tourist Can Earn coding problem to test a candidate's ability to model state transitions. It's a classic application of Dynamic Programming on a graph. It evaluates whether you can define a state (e.g., dp[day][city]) and correctly derive the transition formula based on the choices available (staying vs. moving). It also tests your ability to optimize for time and space, as a naive recursive solution would be exponential.

3. Algorithmic pattern used

The Array, Matrix, Dynamic Programming interview pattern is the standard way to solve this. You create a DP table where dp[i][j] represents the maximum points earned after i days ending in city j. Transition: dp[day][city] = max( dp[day-1][city] + stay_points[day-1][city], // Stayed in the same city max(dp[day-1][prev_city] + travel_points[prev_city][city]) // Traveled from prev_city ) The base case is dp[0][city] = 0 for all cities (or specific starting points if defined).

4. Example explanation

2 cities, 2 days.

• Stay points: City 0: [5, 10], City 1: [2, 3]
• Travel points: 0->1: 2, 1->0: 1 Day 1:
• End in City 0: max(stay at 0: 5, travel from 1: 0+1=1) = 5
• End in City 1: max(stay at 1: 2, travel from 0: 0+2=2) = 2 Day 2:
• End in City 0: max(stay at 0: 5+10=15, travel from 1: 2+1=3) = 15
• End in City 1: max(stay at 1: 2+3=5, travel from 0: 5+2=7) = 7 Max points after Day 2: 15.

5. Common mistakes candidates make

In the Maximum Points Tourist Can Earn coding problem, candidates often forget to consider the "travel" points correctly, sometimes only adding the "stay" points of the destination city. Another common mistake is not initializing the DP table correctly, especially if the tourist must start at a specific city. Many also struggle with the time complexity if they re-calculate the same subproblems instead of using memoization or a bottom-up DP table.

6. Interview preparation tip

For path-based DP problems, always think about the "previous state." Ask yourself: "How could I have arrived at city X on day Y?" This helps in forming the transition relation. Also, notice if the state only depends on the previous day; if so, you can often optimize space by only keeping the last two rows of your DP table.